Quantum Oracles in Constant Depth with Measurement-Based Quantum Computation
arXiv:1406.4361
Abstract
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 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.
4 pages, 4 figures