Sökning: onr:"swepub:oai:research.chalmers.se:2e126d8d-faab-45d8-803c-0a61b8606948" >
Quantum Depth in th...
Quantum Depth in the Random Oracle Model
-
- Arora, Atul Singh (författare)
- California Institute of Technology (Caltech)
-
- Coladangelo, Andrea (författare)
- University of Washington
-
- Coudron, Matthew (författare)
- National Institute of Standards and Technology (NIST)
-
visa fler...
-
- Gheorghiu, Alexandru, 1990 (författare)
- Eidgenössische Technische Hochschule Zürich (ETH),Swiss Federal Institute of Technology in Zürich (ETH),Chalmers tekniska högskola,Chalmers University of Technology
-
- Singh, Uttam (författare)
- International Institute of Information Technology,Polish Academy of Sciences
-
- Waldner, Hendrik (författare)
- University of Maryland
-
visa färre...
-
(creator_code:org_t)
- 2023
- 2023
- Engelska.
-
Ingår i: Proceedings of the Annual ACM Symposium on Theory of Computing. - 0737-8017. ; , s. 1111-1124
- Relaterad länk:
-
https://research.cha... (primary) (free)
-
visa fler...
-
https://research.cha...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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) BPPQNCBPP BQP. This refutes Jozsa's conjecture 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. We also show that BPPQNC and BPPQNC are both strictly contained in BPPQNCBPP. (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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- proof of quantum depth
- random oracle model
- Hybrid classical-quantum models of computation
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas