Researchers Demonstrate Complex Computations Remain Consistent with Classical Data Use

Scott Aaronson and colleagues at UT Austin in collaboration with MIT and UC Berkeley, investigate a fundamental question in quantum complexity theory concerning the relationship between quantum and classical computation. The containment of $\mathsf{BQP}$ within $\mathsf{MIP}$ holds true for any classical oracle. This finding addresses a long-standing open problem, specifically whether this containment ‘relativizes’, and builds upon previous work by Grover and Rudolph, as well as Aharonov, Arad, and Vidick. This result suggests that progress in the ‘oracle world’ could enable a practical, non-cryptographic protocol to verify quantum computations with a classical computer, a key goal in the field.

Quantum computation verification bypasses cryptographic reliance with exponentially-long classical proofs

The construction of a Probabilistically Checkable Proof (PCP) system now demands an exponentially-long classical proof, a substantial reduction from previous methods. Earlier approaches to quantum verification either discarded the inherent quantum structure of the computation, effectively reducing it to a classical problem, or relied on cryptographic assumptions, such as the hardness of factoring or discrete logarithms. This new system avoids both of these limitations, offering a potentially more robust and broadly applicable verification method. The significance of this reduction lies in the fact that the length of the classical proof required to verify a quantum computation has been a major bottleneck in developing practical verification protocols. An exponential reduction in proof length translates directly to a reduction in the computational resources required by the classical verifier. A PCP system for $\mathsf{BQP}^{O}$, quantum computations with a classical oracle, achieves this threshold with the verifier performing a polynomial number of queries, a feat previously unattainable without compromising computational efficiency or relying on unproven cryptographic principles. The oracle, denoted by ‘O’, represents an additional computational resource available to the quantum computation, but crucially, the verifier’s complexity remains polynomial even with its inclusion.

Establishing this containment of $\mathsf{BQP}$ within $\mathsf{MIP}$ for any classical oracle represents a key step towards verifying quantum computations with classical computers. A pathway to potentially develop practical, non-cryptographic verification methods is now open with this new approach. A Probabilistically Checkable Proof (PCP) system, a method for verifying computations, now requires an exponentially-long classical proof, marking a substantial improvement over previous approaches. PCP systems work by allowing a verifier to check a proof with a small probability of error, even if the proof is extremely long. The verifier achieves this by making a limited number of queries to the proof, and probabilistically determining whether the computation is correct. The efficiency of a PCP system is measured by the length of the proof and the number of queries the verifier needs to make. Reducing both of these parameters is a major goal in the field.

The system applies to $\mathsf{BQP}^{O}$, quantum computations utilising a classical oracle, and crucially, the verifier only needs to make a polynomial number of queries to both the proof and the oracle. This achievement bypasses limitations found in earlier protocols, including those discarding quantum structure or relying on unproven cryptographic assumptions; the standard sum-check protocol and protocols from Aharonov, Arad, and Vidick all fail to relativize, meaning they cannot function effectively when combined with an oracle. Drawing inspiration from the state synthesis algorithm, a technique used in control theory to design systems that achieve desired states, the construction offers a complement to existing “exponential PCP” methods. The state synthesis algorithm provides a framework for constructing proofs that can be efficiently verified, and this framework is adapted to the quantum setting in this work. The combination of state synthesis and exponential PCP techniques allows for a more efficient and robust verification protocol.

Relativisation and its implications for quantum verification protocols

Containing quantum computations within classical frameworks remains a central challenge, and this work offers a striking advance by demonstrating that the containment of $\mathsf{BQP}$ within $\mathsf{MIP}$ holds true even when a classical ‘oracle’ is introduced. This achievement highlights a persistent tension within the field, as this containment ‘relativizes’, meaning it functions consistently even with added computational shortcuts, while other key results, such as the equivalence of $\mathsf{IP}$ and $\mathsf{PSPACE}$, demonstrably do not. The fact that $\mathsf{IP} = \mathsf{PSPACE}$ does not relativize, meaning there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$, suggests that these results may be fundamentally different from the containment of $\mathsf{BQP}$ within $\mathsf{MIP}$. Acknowledging this difference in behaviour creates understandable doubt about its ultimate significance, and motivates further research into the underlying reasons for this discrepancy. The concept of ‘relativization’ is crucial in complexity theory, as it allows researchers to isolate the core computational properties of a problem from the specific details of its implementation. A result that relativizes is considered more robust and likely to be true in a wider range of settings.

Demonstrating this behaviour with a classical ‘oracle’, in effect, a computational shortcut, provides a valuable testbed for future research into quantum verification protocols. Specifically, it offers a potential pathway towards proving quantum computations to classical computers, a long-standing goal in the field and a key step towards building practical quantum technologies. The ability to verify quantum computations with classical computers would have profound implications for the development of quantum technologies, as it would allow us to ensure the correctness of quantum algorithms and prevent errors. This work confirms that containing quantum computation within a classical framework, specifically showing that the class of problems solvable by quantum computers in polynomial time ($\mathsf{BQP}$) is contained within a multi-prover interactive proof system ($\mathsf{MIP}$), remains true even when a classical computational shortcut, or oracle, is used. This ‘relativizing’ containment distinguishes this result from other established findings in complexity theory where similar containments fail when oracles are introduced, suggesting a unique durability to this particular relationship. The implications extend beyond theoretical computer science, potentially impacting areas such as cryptography and materials science, where quantum computations are expected to play an increasingly important role.

The researchers demonstrated that the class of problems solvable by quantum computers in polynomial time ($\mathsf{BQP}$) is contained within a multi-prover interactive proof system ($\mathsf{MIP}$) even when utilising a classical computational shortcut known as an oracle. This containment, which ‘relativizes’, differs from other complexity class containments and suggests a robust relationship between quantum and classical computation. This finding provides a valuable testbed for future research into quantum verification protocols, potentially offering a pathway towards proving quantum computations to classical computers. The authors hope that progress in this ‘oracle world’ will contribute to solving the longstanding open problem of creating a non-cryptographic interactive protocol for verifying quantum computation.