Quantum Advantage from One-Way Functions

Is quantum computing truly faster than classical computing? Demonstrating unconditional quantum computational advantage lies beyond the reach of the current complexity theory, and therefore we have to rely on some complexity assumptions. While various results on quantum advantage have been obtained, all necessitate relatively stronger or less standard assumptions in complexity theory or classical cryptography. In this paper, we show quantum advantage based on several fundamental assumptions, specifically relying solely on the existence of classically-secure one-way functions. Given the fact that one-way functions are necessary for almost all classical cryptographic primitives, our findings yield a surprising implication: if there is no quantum advantage, then there is no classical cryptography! More precisely, we introduce inefficient-verifier proofs of quantumness (IV-PoQ), and construct it from statistically-hiding and computationally-binding classical bit commitments. IV-PoQ is an interactive protocol between a verifier and a quantum polynomial-time prover consisting of two phases. In the first phase, the verifier is classical probabilistic polynomial-time, and it interacts with the quantum polynomialtime prover over a classical channel. In the second phase, the verifier becomes inefficient, and makes its decision based on the transcript of the first phase. If the quantum prover is honest, the inefficient verifier accepts with high probability, but any classical probabilistic polynomial-time malicious prover only has a small probability of being accepted by the inefficient verifier. In our construction, the inefficient verifier can be a classical deterministic polynomial-time algorithm that queries an NP oracle. Our construction demonstrates the following results based on the known constructions of statistically-hiding and computationally-binding commitments from one-way functions or distributional collision-resistant hash functions:

• If one-way functions exist, then IV-PoQ exist.

• If distributional collision-resistant hash functions exist (which exist if hard-on-average problems in SZK exist), then constant-round IV-PoQ exist.

We also demonstrate quantum advantage based on worst-case-hard assumptions. We define auxiliaryinput IV-PoQ (AI-IV-PoQ) that only require that for any malicious prover, there exist infinitely many auxiliary inputs under which the prover cannot cheat. We construct AI-IV-PoQ from an auxiliary-input version of commitments in a similar way, showing that

• If auxiliary-input one-way functions exist (which exist if CZK ⊆ BPP), then AI-IV-PoQ exist.

• If auxiliary-input collision-resistant hash functions exist (which is equivalent to PWPP FBPP) or SZK BPP, then constant-round AI-IV-PoQ exist.

Finally, we also show that some variants of PoQ can be constructed from quantum-evaluation one-way functions (QE-OWFs), which are similar to classically-secure classical one-way functions except that the evaluation algorithm is not classical but quantum. QE-OWFs appear to be weaker than classically-secure classical one-way functions, and therefore it demonstrates quantum advantage based on assumptions even weaker than one-way functions.

Approach 2: Search problems. Some inefficiently-verifiable search problems that exhibit quantum advantage have been introduced. For example, for the random circuit model, [AC17, AG19] introduced so-called Heavy Output Generation (HOG) and Linear Cross-Entropy Heavy Output Generation (XHOG) where given a quantum circuit C it is required to output bit strings that satisfy certain relations about C. The relations can be verified inefficiently. The classical hardnesses of these problems are, however, based on new assumptions introduced by the authors.

[Aar10] constructed an inefficiently-verifiable search problem (Fourier Fishing), but its quantum advantage is relative to random oracles. [ACC + 22] constructed another inefficiently-verifiable search problem (Collision Hashing), but its quantum advantage is also relative to random oracles.

There is another approach of demonstrating quantum advantage where the verification is efficient, namely, proofs of quantumness (PoQ) [BCM + 21]. In PoQ, we have a QPT prover and a PPT verifier. They interact over a classical channel, and the verifier finally makes the decision.

If the QPT prover behaves honestly, the verifier accepts with high probability, but for any malicious PPT prover, the verifier accepts with only small probability. The simplest way of realizing PoQ is to let the prover solve an NP problem that is quantumly easy but classically hard, such as factoring [Sho94]. Such a simplest way is, however, based on specific assumptions that certain specific problems are hard for PPT algorithms.

The first construction of PoQ based on a general assumption was given in [BCM + 21] where (noisy) trapdoor claw-free functions with the adaptive-hardcore-bit property is assumed. Such functions can be instantiated with the