02089nas a2200229 4500008004100000245004500041210004500086260001500131520136900146653003701515653003801552653004301590653002701633653003101660100002301691700002401714700002101738700002501759700001701784700002101801856003701822 2022 eng d00aQuantum Depth in the Random Oracle Model0 aQuantum Depth in the Random Oracle Model c10/12/20223 a

We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle:
(a) BPPQNCBPP≠BQP. This refutes Jozsa's conjecture [QIP 05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing.
(b) BPPQNC⊈QNCBPP and QNCBPP⊈BPPQNC. This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [STOC 22].

10aComputational Complexity (cs.CC)10aCryptography and Security (cs.CR)10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aArora, Atul, Singh1 aColadangelo, Andrea1 aCoudron, Matthew1 aGheorghiu, Alexandru1 aSingh, Uttam1 aWaldner, Hendrik uhttps://arxiv.org/abs/2210.06454