Quantum Oracles in Constant Depth with Measurement-Based Quantum Computation
Benoît Valiron · arXiv (Cornell University) · 2014
This paper shows that, in measurement-based quantum computation, it is possible to write any quantum oracle implementing a classical function in constant depth. The result is shown through the equivalence between MBQC and the circuit model where arbitrary rotations along $Z$ axis and unbounded fan-outs are elementary operations. A corollary of this result is that disjunction can be implemented exactly in constant-depth, answering an open question of Høyer and Špalek.