Cryptographic Characterization of Quantum Advantage

Quantum computational advantage refers to an existence of computational tasks that are easy for quantum computing but hard for classical one. Unconditionally showing quantum advantage is beyond our current understanding of complexity theory, and therefore some computational assumptions are needed. Which complexity assumption is necessary and sufficient for quantum advantage? In this paper, we show that inefficient-verifier proofs of quantumness (IV-PoQ) exist if and only if classicallysecure one-way puzzles (OWPuzzs) exist. As far as we know, this is the first time that a complete cryptographic characterization of quantum advantage is obtained. IV-PoQ are a generalization of proofs of quantumness (PoQ) where the verifier is efficient during the interaction but may use unbounded time afterward. IV-PoQ capture various types of quantum advantage previously studied, such as samplingbased quantum advantage and searching-based one. Previous work [Morimae and Yamakawa, Crypto 2024] showed that IV-PoQ can be constructed from OWFs, but a construction of IV-PoQ from weaker assumptions was left open. Our result solves the open problem, because OWPuzzs are believed to be weaker than OWFs. OWPuzzs are one of the most fundamental quantum cryptographic primitives implied by many quantum cryptographic primitives weaker than one-way functions (OWFs), such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs), and one-way state generators (OWSGs). The equivalence between IV-PoQ and classically-secure OWPuzzs therefore highlights that if there is no quantum advantage, then these fundamental cryptographic primitives do not exist. The equivalence also means that quantum advantage is an example of the applications of OWPuzzs. Except for commitments, no application of OWPuzzs was known before. Our result shows that quantum advantage is another application of OWPuzzs, which solves the open question of [Chung, Goldin, and Gray, Crypto 2024]. Moreover, it is the first quantum-computation-classical-communication (QCCC) application of OWPuzzs. To show the main result, we introduce several new concepts and show some results that will be of independent interest. In particular, we introduce an interactive (and average-case) version of sampling problems where the task is to sample the transcript obtained by a classical interaction between two quantum polynomial-time algorithms. We show that quantum advantage in interactive sampling problems is equivalent to the existence of IV-PoQ, which is considered as an interactive (and average-case) version of Aaronson's result [Aaronson, TCS 2014], SampBQP = SampBPP ⇔ FBQP = FBPP. Finally, we also introduce zero-knowledge IV-PoQ and study sufficient and necessary conditions for their existence.