Temporally Flat One-Way Quantum Computing

Question

I am a physicist at heart, and so I think One-Way Quantum Computing is brilliant. In particular, Graph State Measurement-based Quantum Computing (MBQC) has been a really nice development in Quantum Computing research as originated by Raussendorf & Briegel. One just needs to prepare a multi-partite entangled state as described by a graph, and then perform sequential measurements on each node or qubit (adaptive measurements for deterministic computations).

Another excellent aspect of this approach is that Clifford circuits can be implemented in a single-round of measurements as shown by Raussendorf, Browne and Briegel. These circuits can be classically simulated (efficiently) as shown by Gottesman and Knill so it is an interesting connection between classical simulation and temporal resources.

However, not all temporally flat Graph State MBQC circuits (consisting of one round of measurements) are believed to be simulatable classically. For example, families of circuits in the quantum circuit model consisting of commuting gates called IQP circuits as introduced by Shepherd and Bremner can be implemented in single time-step in MBQC. These IQP circuits are believed not to be classically simulatable (in computational complexity terms, it would lead to a collapse of the polynomial hierarchy).

See also a nice description of a class of circuits implemented in one time-step here. Given that commuting/diagonal unitaries can have some interesting behaviour but non-commuting circuits be classically simulatable. It would be interesting if there were non-commuting circuits that can be implemented but not yet shown to be classically simulatable.

Anyway, my question is:

Are there other interesting circuits that can be implemented in a single time-step in MBQC?

Though I would prefer relations to computational complexity or classical simulation, I would find anything interesting.

Edit: After Joe's excellent answer below, I should clarify a couple of things. As Joe said (and somewhat embarrassingly I have said in one of my own papers), single measurement-round MBQC circuits are in IQP. To be more precise, I am interested in interesting circuits in the problems in IQP that can be implemented in one round of measurements in MBQC. Clifford circuits are an interesting example. If there any other examples which are classically simulatable that would be extremely interesting. Since simulating IQP circuits is believed to be unlikely classically, it would be interesting to find instances of circuits that are.

Answer 1

Given the update on the question, I thought it best to post this as a new answer, as it is totally different from my previous answer, and hopefully is interesting.

It seems by the new phrasing of the question that there is a hidden assumption that the MBQC resource state has a number of qubits polynomial in the number of logical qubits. This doesn't necessarily have to be the case, which leads to a potentially interesting situation. It is possible to construct single layer measurement based computations for which the resource state is necessarily exponential in the number of logical qubits, $n$.

To see this, just note that any qubit $j$ in a graph state which is measured in the $X$-$Z$ plane has the same effect as applying the operator $\exp{\big(i \theta \prod_i Z_i \big)}$ where $i$ ranges over all the neighboring qubits of $j$. To see this, note that the entanglement operator applied to $j$ is $|0\rangle\langle 0|\otimes I + |1\rangle\langle 1|\otimes \prod_i Z_i$. As the qubit is initially prepared in state $|+\rangle$ the net result is that the following operator is applied over the neighbouring qubits: $\frac{1}{\sqrt{2}}\left(|0\rangle \otimes I + |1\rangle\otimes \prod_i Z_i\right)$. If the qubit is then rotated by $\exp(i\theta X)$ the result is $\frac{1}{\sqrt{2}}\left(|0\rangle \otimes (\cos \theta I + i \sin \prod_i Z_i) + |1\rangle\otimes (\prod_i Z_i\right)(\cos \theta I + i \sin \prod_i Z_i)$. Thus up to a Pauli correction of $\prod_i Z_i$ we deterministically implement the operator $\cos \theta I + i \sin \prod_i Z_i$ which is just an alternate form of $\exp{\big(i \theta \prod_i Z_i \big)}$.

Note that such operators are the Hadamard transform of the basic building blocks of X-programs, and that all such operators commute independent of which qubits they operate on. IQP is defined in terms of X-programs which are restricted to having a number of terms at most polynomial in the number of qubits. However, there are an exponential number of independent such terms, and so it is possible to specify temporally flat computations which have exponential sized X-programs. Indeed the $n$-input phase Toffoli gate (i.e. the $C....CZ$ gate) is an example of such an operation that requires an exponential number of commuting gates, though it can be achieved with a linear number of non-commuting gates. Thus it is possible to construct single layer measurement based computations which implement X-programs which are exponential in the number of logical qubits, and hence outside of IQP for the logical qubits (though inside IQP for the physical qubits).

Potentially there is a problem here, in that they require an exponential number of parameters to uniquely specify all of the pairs in the X-program. However, if you consider such angles to be generated algorithmically (say with the restriction that each angle can be computed in polynomial time) then it is not even clear whether simulating such a computation can be done in BQP.

Answer 2

It doesn't make sense to me to ask about non-commuting operators being implemented in a single time step (though constant depth certainly makes sense). However, you can implement non-commuting gates on the logical subspace of an MBQC which are implemented using commuting measurements on the resource state, though the implemented gates are not deterministic.

Actually, I believe you are viewing IQP more narrowly than you probably should. The answer to your question is that any MBQC which can be implemented in a single measurement layer in MBQC is contained in IQP. This is simply because rather than expressing the result in terms of the logical Hilbert space, you can express it as a series of commuting operations on the physical qubits. Shepherd and Bremner actually deal with this in their paper (in section 5.2 where such operations are called graph-programs).