Researchers at Princeton University and Kyoto University have demonstrated a scenario where evidence of quantum advantage can coexist with the theoretical equivalence of P and NP. The work details a classical oracle, a hypothetical computational tool, relative to which both proofs of quantumness and the equality of P^O and NP^O hold true, challenging a common assumption that quantum advantage necessarily implies P ≠ NP.

The researchers also constructed an oracle where $B Q P^{O}$ equals $P S P A C E^{O}$ , indicating a significant leap in classical computational power. These oracle separations have direct implications for cryptography; the findings suggest proofs of quantumness cannot reliably construct classical or quantum cryptography, and quantum oblivious transfer cannot build post-quantum one-way functions, under specific conditions.

Proofs of Quantumness Coexist with P = NP

A newly constructed classical oracle demonstrates a scenario where proofs of quantumness can exist even if P equals NP, a result challenging conventional assumptions about the relationship between quantum advantage and computational complexity. The finding suggests that demonstrating quantum capabilities does not automatically preclude the possibility of efficient classical computation for all problems. The researchers further established that relative to this oracle, quantum computation, specifically BQP, is equivalent to PSPACE, a classical complexity class representing problems solvable by a polynomial-space Turing machine.

This equivalence is notable because it positions quantum computation at a higher level of classical computational power than typically assumed in a relativized setting, where oracle machines are used to compare complexity classes. The construction of this oracle provides concrete evidence that quantum speedups do not necessarily translate into an overall advantage across all computational tasks, even when proofs of quantumness are present.

The implications extend to cryptography; the team’s work demonstrates that if P equals NP, then nearly all forms of classical cryptography, including those relying on one-way functions, cannot exist. The researchers also note that constant-round proofs of quantumness are not possible in this scenario, presenting a further obstacle to simplifying the verification process.

This work builds on previous research by showing that a polynomial-round proof of quantumness with efficient classical verification can exist even when P equals NP and BQP equals PSPACE, offering a detailed perspective on the interplay between quantum and classical computational power. The team’s construction provides a specific instance where quantum advantages, as evidenced by proofs of quantumness, do not automatically invalidate the possibility of efficient classical computation, and highlights the limitations of using such proofs to construct certain cryptographic systems.

Oblivious State Preparation and Quantum Advantage

The construction of an oracle where quantum verifier oblivious state preparation exists alongside an equivalence between BQP and QCMA challenges established assumptions about translating quantum advantages into practical security applications. This specific oracle, sampled from a distribution denoted ‘D’, demonstrates a scenario where a quantum computation advantage does not automatically yield improvements in cryptographic primitives. The distribution itself comprises random oracles and unitaries, carefully constructed to exhibit these properties with high probability.

This work establishes that oblivious state preparation, a strong quantum primitive, can coexist with a specific relationship between BQP and QCMA, even when classical verification is possible. This means that while quantum computation and classical communication can achieve certain tasks efficiently, this efficiency cannot be directly used to build one-way functions with a relativizing proof.

The oracle, denoted $R O_{t}$ , operates on inputs of size t, mapping bit strings to other bit strings, and uses random states and unitaries to achieve its properties. This finding highlights a fundamental limitation in translating theoretical quantum advantages into concrete cryptographic gains, even under specific computational conditions.

Classical Oracle Separating P^O and NP^O

The construction of a classical oracle where $P^{O}$ equals $N P^{O}$ , while simultaneously allowing for the existence of proofs of quantumness, challenges a long-held assumption about the relationship between computational complexity and quantum advantage. This specific oracle, built to demonstrate this coexistence, relies on a hard unary language to establish its properties, moving away from typical oracle separation techniques. Conversely, for inputs not in L, the verifier must reject all witnesses with a probability less than or equal to one-third.

This framework helps them understand the limitations of translating theoretical quantum advantages into practical cryptographic applications, as demonstrated by the oracle’s design. The team’s approach diverges from previous work by acknowledging that problems separating BQP from classical computation may not always admit efficient-prover interactive proofs.

BQP^O = PSPACE^O with Oracle Construction

The construction of a specific oracle demonstrates that, relative to it, computational complexity classes BQP and PSPACE become equivalent. This result establishes a scenario where quantum computation, represented by BQP, exhibits the same power as PSPACE, a class encompassing problems solvable by classical computers using polynomial space. This equivalence is notable because PSPACE is known to be significantly more powerful than many other classical complexity classes, such as NP.

The researchers’ approach hinges on defining languages within these complexity classes using oracle Turing machines, hypothetical machines augmented with the ability to query an oracle. Borel-Cantelli’s lemma then confirms that these errors become negligible as input size increases. This finding is important because it shows that even with the added power of an oracle, the verification process remains computationally feasible. The researchers also proved that the probability of this event occurring infinitely often is zero, solidifying the robustness of their construction.

This work has implications beyond theoretical computer science, as it clarifies the limits of translating quantum advantages into practical security measures. They give evidence that proofs of quantumness can exist when P = NP and that (quantum verifier) oblivious state preparation can exist when BQP = QCMA.

Implications for Classical Cryptography

This specific oracle demonstrates a scenario where a language exists within $I P^{O}$ , a subset of $B Q P^{O}$ , that proves difficult for polynomial-time algorithms augmented with limited computational assistance, a finding that has direct implications for the foundations of secure communication. The researchers’ work establishes that such proofs of quantumness cannot be used to build either classical or quantum cryptography using methods that remain valid across different computational models.

This limitation stems from the oracle’s properties, which also equate $B Q P^{O}$ with $P S P A C E^{O}$ , effectively raising the bar for classical computational power relative to this oracle. Nearly all established forms of classical cryptography rely on the impossibility of solving certain problems efficiently, and these break down when P equals NP; similarly, many quantum cryptographic schemes depend on assumptions that fail if BQP equals PSPACE.

The team’s findings demonstrate that even with the potential advantages offered by quantum phenomena, constructing robust cryptographic systems remains fundamentally constrained under these specific conditions. “There is no relativizing construction of (most forms of) classical or quantum cryptographic primitives from polynomial-round PoQ or two-message qv-PoQ,” the researchers state, highlighting the inherent limitations of this approach. The work highlights that achieving cryptographic security requires more than just demonstrating quantum advantage. It demands a careful consideration of the underlying computational assumptions and the limitations of proof techniques.

Quantum Verifier Proofs of Quantumness (qv-PoQ)

This finding challenges a common assumption that demonstrating quantum advantage, the ability of a quantum computer to outperform classical computers, necessarily implies limitations on classical computational power. The research highlights the broader applicability of oblivious state preparation, showing it can be used to construct proofs of quantum memory and search-secure quantum-computation-classical-communication oblivious transfer. Quantum verifier versions of these proofs, where the verifier possesses quantum capabilities, are particularly interesting as they allow for quantum verification even against quantum adversaries.

OSP and the Construction of Quantum Memory Proofs

Oblivious state preparation (OSP) extends beyond proofs of quantumness to enable the construction of proofs of quantum memory, a demonstration of quantum capability requiring sustained quantum coherence. A proof of quantum memory distinguishes a classically limited prover and a quantum prover lacking sufficient memory, establishing a higher bar for demonstrating quantum resources during protocol execution. This contrasts with protocols like factoring and discrete log, which can also serve as foundations for proofs of quantumness, alongside cryptographic assumptions such as the learning with errors (LWE) assumption and indistinguishability obfuscation (iO).

Post-quantum versions of assumptions used in OSP constructions, like LWE, can also be used to achieve OSP, though these protocols are inherently interactive, differing from constructions relying on NP ∩ BQP. The research reveals a fundamental limit. No relativizing construction can build either OSP or proofs of quantum memory from proofs of quantumness, even when verification is inefficient.

This means that demonstrating quantum advantage through PoQ alone does not automatically translate into secure cryptographic primitives under the constraints of a relativizing proof. Specifically, the existence of BQP = PSPACE precludes the existence of nearly all forms of quantum cryptography, a result stemming from a PSPACE-effective variant of OpenAI’s unitary synthesis algorithm. Constant-round proofs of quantumness are also impossible if P = NP, creating a barrier to reducing the number of rounds required for PoQ and partially hindering the construction of classically verifiable PoQ from quantum-verified versions.

Complexity Lower Bounds for PoQ and qv-OSP

Researchers have identified scenarios where PoQ can coexist with P = NP, challenging a common assumption that demonstrating quantum capabilities necessitates a separation between these complexity classes. Known constructions of PoQ rely on assumptions that classically-secure one-way functions exist, but the research indicates this dependency may not be universal. The team’s analysis also reveals a connection between oblivious state preparation (OSP) and the quantum vs classical complexity classes, specifically BQP and QCMA.

It remains open whether the existence of quantum verifier oblivious state preparation (qv-OSP) implies BQP ≠ QCMA, but lower bounds on both primitives are established. If BPP = PP, PoQ cannot exist, as a classical prover with access to a PP oracle could simulate quantum computation. Similarly, qv-OSP cannot exist if BQP = PP, highlighting the constraints on building quantum advantages from specific classical computational capabilities.

👉 More information
🗞 Quantum Advantage has Few Complexity Implications
✍️ Eli Goldin and Alex Lombardi (Princeton University); Tomoyuki Morimae (Yukawa Institute for Theoretical Physics)
🧠 ArXiv: https://arxiv.org/abs/2611.05303

More like this