IQP computations with intermediate measurements

Abstract

We consider the computational model of IQP circuits (in which all computational steps are $X$ basis diagonal gates), supplemented by intermediate $X$ or $Z$ basis measurements. We show that if we allow non-adaptive or adaptive $X$ basis measurements, or allow non-adaptive $Z$ basis measurements, then the computational power remains the same as that of the original IQP model; and with adaptive $Z$ basis measurements the model becomes quantum universal. Furthermore we show that the computational model having circuits of only $CZ$ gates and adaptive $X$ basis measurements, with input states that are tensor products of 1-qubit states from the set $\{|+⟩,|1⟩,\frac{1}{\sqrt{2}}(|0⟩+i|1⟩),\frac{1}{\sqrt{2}}(|0⟩+e^{i\pi /4}|1⟩)\}$, is quantum universal. In contrast to the relation of IQP to PH collapse, all our results here are manifestly stable under small additive implementational errors.