Hendrik Waldner

We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, we show that the following statements hold relative to a random oracle: (a) latex mathsfBPP^QNC^BPP neq mathsfBQP. This refutes Jozsa's conjecture [Joz05] 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) latex mathsfQNC^BPP notsubseteq mathsfBPP^QNC and latex mathsfBPP^QNC notsubseteq mathsfQNC^BPP 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 [YZ22]. [Joz05] - Richard Jozsa. ""An introduction to measurement based quantum computation."" In: Quantum Information Processing 199 (Sept. 2005). [YZ22] - Takashi Yamakawa and Mark Zhandry. ""Verifiable quantum advantage without structure."" In: 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.