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 polynomial-time 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 \(\textbf{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 \(\textbf{SZK}\) exist), then constant-round IV-PoQ exist.

We also demonstrate quantum advantage based on worst-case-hard assumptions. We define auxiliary-input 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 \(\textbf{CZK}\not \subseteq \textbf{BPP}\)), then AI-IV-PoQ exist.

• If auxiliary-input collision-resistant hash functions exist (which is equivalent to \(\textbf{PWPP}\nsubseteq \textbf{FBPP}\)) or \(\textbf{SZK}\nsubseteq \textbf{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.

1. 1.

   Another important goal of quantum computational advantage is experimental implementation. In such a scenario, priority would be given to the experimental feasibility (such as simplicity of quantum circuits, etc.) rather than the reliability of underlying complexity assumptions. Our interest in this paper is purely theoretical one, and our objective is to identify the weakest complexity assumption for quantum advantage assuming any polynomial-time quantum computing is possible.

2. 2.

   The Boson Sampling model is a quantum computing model that uses non-interacting bosons, such as photons. The IQP (Instantaneous Quantum Polytime) model is a quantum computing model where only commuting quantum gates are used. The random circuit model is a quantum computing model where each gate is randomly chosen. The one-clean-qubit model is a quantum computing model where the input is \(|0\rangle \langle 0|\otimes \frac{I^{\otimes m}}{2^m}\).

3. 3.

   We say that the output probability distribution of a quantum algorithm is sampled by a classical algorithm within a constant multiplicative error \(\epsilon \) if \(|q_z-p_z|\le \epsilon p_z\) is satisfied for all z, where \(q_z\) is the probability that the quantum algorithm outputs the bit string z, and \(p_z\) is the probability that the classical algorithm outputs the bit string z.

4. 4.

   [55] previously showed that output probability distributions of constant-depth quantum circuits cannot be sampled classically unless \(\textbf{BQP}\subseteq \textbf{AM}\). Their assumption can be easily improved to the assumption that the polynomial-time hierarchy does not collapse to the second level.

5. 5.

   We say that the output probability distribution of a quantum algorithm is sampled by a classical algorithm within a constant additive error \(\epsilon \) if \(\sum _z|q_z-p_z|\le \epsilon \) is satisfied, where \(q_z\) is the probability that the quantum algorithm outputs the bit string z, and \(p_z\) is the probability that the classical algorithm outputs the bit string z.

6. 6.

   [3, Theorem 21] showed that if there exists an additive-error sampling problem that is quantumly easy but classically hard, then there exists a search problem that is quantumly easy but classically hard. The relation of the search problem is verified inefficiently. Note that the search problem depends on the time-complexity of the classical adversary, and therefore it is incomparable to our (AI-)IV-PoQ.

7. 7.

   The adaptive-hardcore-bit property very roughly means that it is hard to find \(x_b\) (\(b\in \{0,1\}\)) and \(d\ne \textbf{0}\) such that \(f_0(x_0)=f_1(x_1)\) and \(d\cdot (x_0\oplus x_1)=0\), given a claw-free pair \((f_0,f_1)\).

8. 8.

   The inefficient verifier could also take the efficient verifier’s secret information as input in addition to the transcript. However, without loss of generality, we can assume that the inefficient verifier takes only the transcript as input, because we can always modify the protocol of the first phase in such a way that the efficient verifier sends its secret information to the prover at the end of the first phase.

9. 9.

   A distributional collision-resistant hash function [27] is a weaker variant of a collision-resistant hash function that requires the hardness of sampling a collision (x, y) where x is uniformly random and y is uniformly random conditioned on colliding with x.

10. 10.

    It is also known that constant-round statistically-hiding and computationally-binding commitments can be constructed from multi-collision resistant hash functions [14, 40], and therefore we have constant-round IV-PoQ from multi-collision resistant hash functions as well.

11. 11.

    Roughly speaking, auxiliary-input OWFs are keyed functions such that for each adversary there exist infinitely many keys on which the adversary fails to invert the function.

12. 12.

    \(\textbf{CZK}\) is the class of promise problems that have computational zero-knowledge proofs. By abuse of notation, we write \(\textbf{BPP}\) to mean the class of promise problems (instead of languages) that are decidable in PPT.

13. 13.

    See the full version for the definitions of \(\textbf{PWPP}\) and \(\textbf{FBPP}\).

14. 14.

    \(\textbf{SRE}\) is the class of problems that admit statistically-private randomized encoding with polynomial-time client and computationally-unbounded server.

15. 15.

    If we assume soundness against non-uniform PPT adversaries, then it is easy to show that sequential repetition generically amplifies the gap. However, we consider the uniform model of adversaries in this paper since otherwise we would need non-uniform assumptions like one-way functions against non-uniform adversaries which is stronger than the mere existence of one-way functions against uniform adversaries.

16. 16.

    This is similar to falsifiable assumptions [29, 50] but there is an important difference that we do not restrict the challenger to be efficient.

17. 17.

    They use one-round PoQ to mean what we call two-round PoQ by counting interaction from the verifier to prover and from the prover to verifier as a single round.

18. 18.

    This observation is due to Mark Zhandry.

19. 19.

    Note that reductions that work relative to deterministic classical oracles do not necessarily work relative to randomized classical oracles [1, Section 5].

20. 20.

    For example, in the prover’s jth round, if the prover possesses a state \(\sum _{b\in \{0,1\}}\sum _{x\in X_b}|b\rangle |x\rangle \), where \(X_b\) is a certain set, it changes the state into \(\sum _{b\in \{0,1\}}\sum _{x\in X_b}|b\rangle |x\rangle |f_j(b,x,t_j)\rangle \), and measures the third register to obtain the measurement result \(\alpha _j\), where \(f_j\) is the function that computes sender’s jth message, and \(t_j\) is the transcript obtained before the jth round. The prover sends \(\alpha _j\) to the verifier as the sender’s jth message.

21. 21.

    Strictly speaking, \(|0\rangle |x_0\rangle +|1\rangle |x_1\rangle \) is not equal to \(|x_0\rangle +|x_1\rangle \), but the protocol can be easily modified. Given \(\xi \), the prover has only to change \(|0\rangle |x_0\rangle +|1\rangle |x_1\rangle \) to \(|\xi \cdot x_0\rangle |x_0\rangle +|1\oplus (\xi \cdot x_1)\rangle |x_1\rangle \).

22. 22.

    In [49], they resolve the first problem by using a specific commitment scheme of [51] and resolve the second problem by simply assuming the existence of a trapdoor. However, since the commitment scheme of [51] relies on one-way permutations, their idea does not work based on OWFs even if we give up efficient verification.

We thank Kai-Min Chung for pointing out the relationship between Lemma 2.1 and Valiant-Vazirani theorem. TM is supported by JST CREST JPMJCR23I3, JST Moonshot R&D JPMJMS2061-5-1-1, JST FOREST, MEXT QLEAP, the Grant-in-Aid for Scientific Research (B) No. JP19H04066, the Grant-in Aid for Transformative Research Areas (A) 21H05183, and the Grant-in-Aid for Scientific Research (A) No. 22H00522.

Authors and Affiliations

1. Yukawa Institute for Theoretical Physics, Kyoto University, Kyoto, Japan

   Tomoyuki Morimae & Takashi Yamakawa

2. NTT Social Informatics Laboratories, Tokyo, Japan

   Takashi Yamakawa

3. NTT Research Center for Theoretical Quantum Information, Atsugi, Japan

   Takashi Yamakawa

Corresponding author

Correspondence to Tomoyuki Morimae .

Editors and Affiliations

1. Boston University, Boston, MA, USA

   Leonid Reyzin

2. University of Waterloo, Waterloo, ON, Canada

   Douglas Stebila

Reprints and permissions

© 2024 International Association for Cryptologic Research

Policies and ethics