Abstract
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) $\mathsf{BPP}^{\mathsf{QNC}^{\mathsf{BPP}}} \neq \mathsf{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) $\mathsf{BPP}^{\mathsf{QNC}} \nsubseteq \mathsf{QNC}^{\mathsf{BPP}}$ and $\mathsf{QNC}^{\mathsf{BPP}} \nsubseteq \mathsf{BPP}^{\mathsf{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 [STOC 22]. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000584642Publication status
publishedExternal links
Journal / series
arXivPages / Article No.
Publisher
Cornell UniversitySubject
Quantum Physics (quant-ph); Computational Complexity (cs.CC); Cryptography and Security (cs.CR); FOS: Physical sciences; FOS: Computer and information sciencesOrganisational unit
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies03781 - Renner, Renato / Renner, Renato
Related publications and datasets
Is previous version of: http://hdl.handle.net/20.500.11850/620423
More
Show all metadata
ETH Bibliography
yes
Altmetrics