Quantum Advantage has Few Complexity Implications

Introduction

Quantum advantage, the ability of a quantum computer to perform a task that no efficient classical computer can, is the defining promise of quantum computation. For this promise to be checkable, the task should admit efficient classical verification. Sampling output distributions of quantum computers is believed to be classically hard [1, 14], but it is not efficiently verifiable. In contrast, a proof of quantumness (PoQ) [12] is an interactive protocol between a probabilistic polynomial-time (PPT) verifier and a prover such that an honest quantum polynomial-time (QPT) prover makes the verifier accept with high probability, while no PPT prover can.

In this paper, we study PoQ as well as both stronger and weaker forms of quantum advantage. On the stronger side, we consider the notion of oblivious state preparation (OSP) [15]. OSP is a two-party protocol with classical communication in which a classical verifier can remotely generate a quantum state in the prover’s register in such a way that only the verifier knows its classical description. This can be seen as a very strong form of quantum advantage: a prover who can obliviously prepare arbitrary states can demonstrate quantum advantage by giving the result of a related quantum measurement. In particular, this is a form of advantage which retains some notion of hardness even against quantum adversaries.

Beyond the fact that OSP can be used to construct PoQ [15], it has a number of other powerful applications. For example, OSP can be used to construct (single-qubit) proofs of quantum memory (PoQM) [15, 33]. A proof of quantum memory is a proof of quantumness where not only is a classical prover unable to make the verifier accept, but even a quantum prover with insufficient quantum memory cannot succeed. This means that an honest prover demonstrates the ability to maintain quantum memory of a specified size for a specified period during the protocol. In addition, OSP can be used to construct a powerful quantum cryptographic object known as search-secure quantum-computation-classical-communication (QCCC) oblivious transfer [15].

On the weaker side, we consider quantum-verifier proofs of quantumness (qv-PoQ) and quantum-verifier oblivious state preparation (qv-OSP), where the honest verifier in the protocol also has quantum capabilities. Note that these are particularly interesting in the latter setting, where the adversaries are also allowed to be quantum. In particular, as the corresponding protocols allow for quantum verification, qv-OSP is sufficient to instantiate the constructions of (quantumly verifiable) PoQM as well as search-secure QCCC oblivious transfer.

Constructions of PoQ and OSP. Since unconditionally sound proofs of quantumness are not known to exist (indeed, there is a complexity theoretic barrier, see below), PoQ are constructed and proved sound under computational hardness assumptions; this means that the quantum advantage is “lost” if the assumptions turn out to be false. The simplest PoQs arise from problems in $\mathrm{NP} \cap\mathrm{BQP}$ that are believed to be classically hard on average. The verifier samples an instance of the problem and the prover produces a witness. Examples of this formula include factoring and discrete log [51]. Proofs of quantumness can also be built from cryptographic assumptions such as the learning with errors (LWE) assumption [12], quantum fully homomorphic encryption [37], and indistinguishability obfuscation (iO) plus one-way functions (OWFs) [45, 54]. Post-quantum versions of the above listed assumptions can all also be used to achieve OSP through similar constructions [15, 54, 45, 23]. Unlike the $\mathrm{NP} \cap\mathrm{BQP}$ style of construction, these protocols are inherently interactive.

As far as the authors are aware, all known candidate constructions of PoQ rely on assumptions which themselves imply that classically-secure one-way functions exist, and so $\mathrm{NP} \not\subset\mathrm{BPP}$. OSP itself directly implies that $\mathrm{BQP} \ne\mathrm{QCMA}$ (see Appendix § 8) in the classical verifier setting. This implication is not known to hold for qv-OSP.

Known complexity-theoretic/cryptographic lower bounds Despite the fact that all constructions of PoQ imply $\mathrm{NP} \not\subset\mathrm{BPP}$, it is open whether such an implication holds for PoQ generically. Likewise, it is not known whether the existence of qv-OSP implies $\mathrm{BQP} \ne\mathrm{QCMA}$. Nevertheless, complexity theoretic lower bounds are known for both primitives. It is known that if $\mathrm{BPP} = \mathrm{PP}$, then PoQ cannot exist [44, 28]. Intuitively, this is because a classical prover with access to a PP oracle can simulate arbitrary quantum computation, even conditioned on partial outputs. Thus, a PPT algorithm can simulate the honest quantum prover. Similarly, if $\mathrm{BQP} = \mathrm{PP}$, then qv-OSP cannot exist [15, 33, 28].

We remark that for PoQ, stronger complexity lower bounds are known in restricted settings. If $\mathrm{BPP} = \mathrm{NP}$, then constant-round PoQ cannot exist¹. Furthermore, if one assumes a particular structure on the proof of security of the PoQ (namely that it is a black-box reduction to a quantumly-secure falsifiable assumption), then it is necessary that $\mathrm{BQP} \ne\mathrm{PP}$ [56, 28].

Conjectural lower bounds In this work, we investigate the following conjectural lower bounds on PoQ and qv-OSP.

In particular, we will give oracle evidence that neither of these conjectures hold. This opens up the door to constructing PoQ and qv-OSP from much weaker assumptions than previously expected.

Our oracle separations are significantly stronger than simply resolving the above conjectures, and thus imply a series of independently interesting related separations.

Our Results and Corollaries

PoQ can exist even if $\mathrm{BPP} = \mathrm{NP}$. We construct a classical oracle relative to which proofs of quantumness exist, but $\mathrm{BPP} = \mathrm{NP}$. Relative to our oracle, it will also be the case that $\mathrm{BQP} = \mathrm{PSPACE}$. In particular, we show

Note that nearly all forms of classical cryptography (in particular, everything implying one-way functions) cannot exist if $P = NP$. Similarly, nearly all forms of quantum cryptography (in particular, everything implying quantum commitments) cannot exist if $BQP = PSPACE$.²

Notably, there is no relativizing construction of OSP or PoQM from PoQ, even in the setting of inefficient verification.

As $P = NP$, constant-round proofs of quantumness similarly do not exist. This gives a barrier towards round reduction for PoQ as well as a partial barrier for constructing classically verifiable PoQ from qv-PoQ.

We remark that for fully black-box constructions, a negative answer for round-reduction is implicit in prior work. By combining two papers [45, 54] one can construct polynomial-round PoQ from indistinguishability obfuscation and one-way functions. On the other hand, Tomer and Zhandry [56] rule out fully black-box constructions of constant-round PoQ from these same primitives.

We also get a partial negative answer to the important open question of whether PoQ implies classical verification of quantum computation (CVQC) [40]. In particular, if a constant-round CVQC protocol existed relative to our oracle, then applying the CVQC to the hard problem for $P/poly$ gives a constant-round PoQ, which does not exist relative to our oracle.

We remark that the way we prove that PoQ exists relative to our oracle is by demonstrating a hard problem in $BQP^O$ which has an interactive proof whose prover is implementable in $BQP^O$. Extracting this fact from our proof gives the following independently interesting corollary.

In particular, since $PH^O \subseteq P^O/poly$ this gives an oracle relative to which there is a problem outside of PH which can be decided with classical verification of quantum computation.

qv-OSP can exist even if BQP = QCMA. We construct a quantum oracle relative to which qv-OSP exists, but BQP = QCMA.

2. a four message qv-OSP exists

The question of $\mathrm{BQP} = \mathrm{QCMA}$ is also closely tied to a quantum cryptographic primitive known as efficiently-verifiable one-way puzzles (EV-OWPuzz) [21]. The existence of EV-OWPuzzs implies $\mathrm{BQP} \ne\mathrm{QCMA}$. Furthermore, EV-OWPuzzs are implied by a wide variety of quantum cryptographic primitives, including all of post-quantum cryptography.

Goldin, Morimae, Mutreja, and Yamakawa [28] previously showed that there is no relativizing construction of EV-OWPuzzs from either QCCC commitments or QCCC key exchange. Since qv-OSP implies both of these primitives, Corollary 1.9 strengthens these separations by showing that even qv-OSP does not suffice for a relativizing construction of EV-OWPuzzs.

Note that many quantum cryptographic primitives are known to imply EV-OWPuzzs [21]. Selecting interesting examples from this set, we get the following corollary.

Note that the fact that classically verifiable OSP implies EV-OWPuzzs is new. For details, see Appendix § 8.

Related Works

[44] showed that PoQ imply either $\mathrm{NP} \not\subseteq\mathrm{BQP}$ or $\mathrm{SampBQP} \ne\mathrm{SampBPP}$. A natural question is whether the first alternative alone is necessary: does PoQ imply $\mathrm{NP} \not\subseteq\mathrm{BQP}$? Our first result provides an oracle counterexample to this stronger implication, because relative to our oracle, PoQ exist but $\mathrm{NP} = \mathrm{P} \subseteq\mathrm{BQP}$. Thus, the disjunctive necessary condition of [44] cannot be strengthened to $\mathrm{NP} \not\subseteq\mathrm{BQP}$ by a relativizing argument.

[56] showed that constant-round PoQ imply either two-message PoQ, quantumly-secure OWFs, or (weak) signature token schemes. They also show that if polynomial-round PoQ can be constructed from a quantumly-secure falsifiable assumption in a black-box way then quantumly-secure OWPuzz exist. Although these results are the first derivations of quantum cryptographic primitives from PoQ, the former is disjunctive and the latter is the derivation from the way of constructing PoQ, not PoQ itself.

The concurrent work [41] showed that relative to a classical oracle there is a language $L$ such that $L \in\mathrm{EQP} \setminus\mathrm{PH}$ and $L$ has an interactive proof system with a PPT verifier and an honest QPT prover. Our results yield an analogous phenomenon for BQP, while additionally providing a PoQ secure against nonuniform classical provers in a world where P = NP and BQP = PSPACE. [13] showed a classical oracle relative to which $\mathrm{BQP} \not\subseteq\mathrm{IP}$, establishing a relativization barrier to information-theoretically sound, single-prover classical verification of quantum computation. Our result is complementary: we construct a classical oracle relative to which P = NP and BQP = PSPACE, yet polynomial-round proofs of quantumness with efficient classical verification exist.

Technical Overview

A classical oracle relative to which P = NP but proofs of quantumness exist

We begin with an overview of Theorem 1.3. Prior work on quantum advantage relative to oracles [52, 11, 17, 3, 2, 49, 9, 57, 13] typically proceeds in two steps:

• Identify an oracle $\mathcal{A}$ relative to which a non-trivial quantum algorithm solves an apparently challenging computational problem.

• Prove (or conjecture) that classical algorithms relative to that oracle – potentially augmented by a more powerful oracle such as $\mathrm{PH}^{\mathcal{A}}$ – cannot solve the task.

One notable extension of this methodology is an approach of Aaronson, Ingram, and Kretschmer [9], who use a so-called Forrelation encoding to embed the answers to powerful (in their case, #P) computations into an oracle in a form that quantum algorithms can efficiently decode, while the encoding looks random to algorithms in the polynomial hierarchy.

Our methodology: prover-efficient interactive proofs. Our proof relies on this idea from [9] but diverges from the above high-level template. We construct a proof of quantumness by giving an efficient prover interactive proof for a decision problem that is hard for BPP relative to our oracle. That is, the honest prover in our interactive proof can be implemented with a QPT algorithm, and soundness of the interactive proof is information-theoretic.

Let us see under what precise conditions this suffices to get a proof of quantumness. As a warm-up, first suppose that we only want a protocol with soundness error of $1/2 + \epsilon$ against uniform i.o.BPP adversaries. Then, it suffices to work with a unary language $L \subseteq\{1\}^{*}$ outside $\mathrm{BPP}^{\mathcal{O}}$. To see this, suppose that we have such a language where for each bit $b$, the claim $b = 1_L(1^n)$ has an interactive proof with a QPT honest prover. Then, one gets a proof of quantumness in which the honest quantum prover (on input $1^n$) send the bit $b$ declaring whether $1^n \in L$ and then gives an interactive proof for this fact. The protocol is complete by construction, and satisfies soundness (against classical randomized adversaries) because, by the information theoretical soundness of the interactive proof, any adversary passing the PoQ is deciding membership in $L$.

To achieve a full-fledged protocol with (standard) soundness against P/poly, we instead work with a (binary) language $L$ that is non-uniformly hard on average for a uniformly sampled input $x$. In this case, the proof of quantumness is as follows:

• The verifier samples a uniformly random input $x$.

• The prover decides whether $x \in L$, sending the corresponding bit $b$ to the verifier.

• The prover and verifier execute the interactive proof for $x \in L_b$ (either $L$ or $\overline{L}$).

Again, soundness follows because a prover passing the PoQ is correctly deciding whether a random $x \in L$ by the soundness of the interactive proof.

Constructing an appropriate oracle with a hard unary language. Next, we describe a full solution to the warm-up problem. As mentioned earlier, we deviate from the template of most quantum advantage oracle separations. Why? Because relative to most of the oracles considered in prior work, it is not clear that the problems separating BQP from classical computation admit efficient-prover interactive proofs. It is actually not clear that they admit interactive proofs of any kind!³ Indeed, relative to a random oracle it is known that even simple classes like coNP do not have interactive proofs [26, 18], while a recent work [13] proves the same for a variant of the Forrelation problem.

In other words, natural choices of oracle such as a random oracle or an oracle for the Forrelation problem do not seem “IP-friendly.” On the other hand, we know that in the unrelativized setting, IP = PSPACE, so this problem arises because this result (famously) does not relativize.

Our solution is to use Algebrization [10] and build our oracle by the following process

• First, construct an oracle $\mathcal{A}$ relative to which IP = PSPACE $\supsetneq$ PH, so that there are problems outside of the polynomial hierarchy with interactive proofs.

• Then, introduce an oracle $\mathcal{B}$ so that $\mathrm{PSPACE}^{\mathcal{A}} \subset\mathrm{BQP}^{\mathcal{B}}$. This means that every problem in $\mathrm{PSPACE}^{\mathcal{A}}$ has an interactive proof with a $\mathrm{BQP}^{\mathcal{B}}$-efficient prover!

• Finally, prove that there are still problems in $\mathrm{PSPACE}^{\mathcal{A}}$ that are hard relative to $\mathrm{PH}^{\mathcal{A},\mathcal{B}}$.

Then, by appending an appropriately defined “$\mathrm{PH}^{\mathcal{A},\mathcal{B}}$ oracle,” we obtain an oracle $\mathcal{O} = (\mathcal{A},\mathcal{B},\mathcal{C})$ relative to which P = NP but a BQP prover-efficient interactive proof for a classically hard language exists.⁴

This is an outline of our approach. To complete the warm-up, the final question is how to instantiate $\mathcal{A}$ and $\mathcal{B}$. First, we take $\mathcal{A} = (f, \oplus\mathrm{P})$, where $f$ is a random function. It follows that

using the Goldwasser-Kalai-Rothblum variant of the IP = PSPACE theorem [50, 27, 10 AB17], which builds an IP for PSPACE using only low-degree extensions of Boolean functions over characteristic 2 fields. This is extremely convenient because we know (see, e.g., [25], § 3) that

This gives a hard unary language in $\mathrm{PSPACE}^{A}$ that is hard for $\mathrm{PH}^{A}$ using the majority of the function $f$ over all of its $n$-length inputs. This language is hard for $\mathrm{PH}^{A}$ by the $\mathrm{AC}^{0}[\oplus]$ lower bound for majority [48].

However, at this point we have an IP for a language outside PH, but it does not have an efficient quantum prover. To do this, we employ an [9] Forrelation encoding of $\mathrm{PSPACE}^{A}$, and call this oracle $\mathcal{B}$. Then, we have that $\mathrm{PSPACE}^{A}$ is contained in $\mathrm{IP}^{A}$ with a $\mathrm{BQP}^{\mathcal{B}}$-efficient prover. On the other hand, by the security of the Forrelation encoding, we have that $\mathrm{PH}^{A,\mathcal{B}}$ algorithms cannot solve majority on $f$ with probability much better than a PH algorithm relative to $A$ along with an independent random oracle. This completes the warm-up.

Extending to non-uniform hardness. Of course, the unary language used in our warm-up PoQ is not hard for non-uniform classical adversaries, which can have memorized the language in their advice strings. To get around this, we naturally turn to salting: for a function $f:\{0,1\}^{n}\times\{0,1\}^{n}\to\{0,1\}$, we define the language

For a random function $f$, this gives $2^{n}$ independent majority instances at each input length, indexed by a uniformly sampled $x$. Then, by constructing the same oracle $\mathcal{O}=(A,\mathcal{B},C)$ we get our candidate oracle relative to which $\mathrm{P}=\mathrm{NP}$ and there is an efficient-prover interactive proof for the language $L^{f}$.

The remaining question is how to show that deciding $L^{f}$ is almost everywhere hard-on-average for $(\mathrm{PH}/\mathrm{poly})^{A,\mathcal{B}}$. Fix a universal oracle Turing machine $M$ and an advice length $s(n)=\operatorname{poly}(n)$. We want to upper bound the quantity

Our argument proceeds as follows. Suppose instead that this quantity is large.

1. Carefully invoke security of the Forrelation encoding. As a first step (which turns out to be the hardest part of the proof), we would like to convert this attack into one where the Forrelated PSPACE oracle $\mathcal{B}$ has been replaced by a random oracle, invoking the classical (PH) hardness of Forrelation. Compared to before, the challenge is handling advice strings $z$ that can depend on the oracles $A,\mathcal{B}$; since these can reveal individual bits of the Forrelation encoding, it’s not immediately clear how to invoke the hardness of Forrelation.

In other words, we would like to argue that the quantity $\rho(A,\mathcal{B})$ does not change by much when we replace $\mathcal{B}$ by a random oracle. If $\rho(A,\mathcal{B})$ were computable by a $\mathrm{PH}^{A,\mathcal{B}}$ machine, then we would be done. Unfortunately, this doesn’t seem to be the case:

• The verification itself involves the quantity $\operatorname{maj}(f_x)$, which is hard to compute, and

• The expectation over $x$ is also not naturally a PH computation.

To fix this, we introduce a proxy