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.
This post has been migrated from (A51.SE)
Q&A (4871)
