Title: Quantum Depth in the Random Oracle Model
Abstract: We give a comprehensive characterisation 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) BPP^QNC^BPP ≠ 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) BPP^QNC ⊈ QNC^BPP and QNC^BPP ⊈ BPP^QNC.
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 [FOCS 22].
