⚛️ quantum physics

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

This paper constructs protocols for classically verifiable quantum advantage and the verification of BQP computations using quantum indistinguishability obfuscation (qiO), providing a rigorous cryptographic foundation for heuristic proposals and achieving the first publicly verifiable BQP verification under standard computational assumptions.

Original authors: Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu

Published 2026-10-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the race to build machines that can solve problems beyond the reach of today's computers, scientists face a peculiar paradox. To prove a new quantum computer is working, you must ask it to perform a task so complex that a standard computer cannot check the answer. Yet, if the answer cannot be checked, how do you know the machine didn't just guess? This is the central tension of quantum advantage: the need for a test that is hard for classical machines to fake but easy for a human auditor to verify. For years, researchers have tried to design these tests, often relying on complex mathematical puzzles or specific hardware capabilities that are not yet available. The goal has always been to find a way to confirm that a device is truly harnessing the strange laws of quantum mechanics without needing a supercomputer to watch over its shoulder.

A team of researchers has now proposed a new way to solve this puzzle, shifting the problem from the realm of hardware engineering to the field of cryptography. Their work, published in October 2026, suggests that if we can hide the inner workings of a computer program in a specific, mathematically rigorous way, we can create a test that is both easy to run on near-term quantum devices and easy for anyone to verify. The core idea relies on a concept called "obfuscation," which is like scrambling a recipe so thoroughly that you can still cook the dish, but no one can read the ingredients list to figure out how it was made. By applying this scrambling technique to quantum circuits, the authors show how to create a "proof of quantumness" that is secure against classical attempts to deceive.

The researchers built two main protocols based on this idea. The first is a test to prove a device is quantum. In this scenario, a verifier sends a challenge to a prover. The challenge consists of several scrambled instructions. A classical computer, looking at these scrambled instructions, cannot tell what the instructions actually do. However, a quantum computer can run the instructions and produce a specific pattern of results. The verifier checks if the results match the expected pattern. If they do, the verifier knows the prover must be quantum. Crucially, the authors showed that this test can be made "publicly verifiable" by adding a specific cryptographic ingredient: a post-quantum secure one-way function. This allows anyone to check the answer without needing a secret key or private information, whereas the initial private version of the protocol does require the verifier to retain a secret state.

The second protocol goes a step further, allowing a classical computer to verify the results of specific complex quantum calculations, specifically BQP decision problems. This is known as classical verification of quantum computation. The researchers demonstrated that if the obfuscation technique works, a classical auditor can delegate a massive calculation to a quantum machine and be certain of the result. They achieved this by hiding "trap" circuits within the challenge. These traps are designed to reveal the answer if the machine is honest, but they are hidden so well that a machine attempting to deceive cannot tell which parts are traps and which are real calculations. The authors proved that under reasonable assumptions about the difficulty of certain mathematical problems, a classical machine cannot trick the system.

A major contribution of this work is that it does not rely on the specific hardware of the quantum computer being tested. Instead, it relies on the mathematical difficulty of breaking the obfuscation. The authors also addressed a practical hurdle: real quantum computers often use extra "helper" bits, called ancillas, that must be reset to zero after use. They showed that their obfuscation method works even for these messy, real-world circuits by converting them into a cleaner mathematical form that the obfuscation can handle. This bridges the gap between theoretical cryptography and the noisy, imperfect devices we have today.

The paper also tackles the question of whether such obfuscation is even possible to build. While the authors do not provide a finished, working obfuscator, they offer a roadmap. They propose a method to construct these obfuscators by breaking complex circuits into smaller, random pieces and reassembling them in a way that preserves the function but hides the structure. They prove that if this method works for random circuits, it will work for any circuit. This "worst-to-average" reduction provides a strong theoretical foundation, suggesting that the security of the entire system rests on the difficulty of distinguishing random quantum circuits, a problem that is widely believed to be hard.

The implications of this work are profound for the future of quantum computing. It offers a rigorous, cryptographic foundation for the idea of "peaked circuit sampling," a heuristic method recently proposed by other researchers to test quantum advantage. By replacing heuristic guesses with provable security, the authors provide a way to move from "we think this is hard" to "we can prove this is hard." Their work suggests that the path to verifying quantum computers does not necessarily require more powerful quantum hardware or complex interactive games. Instead, it may be found in the clever application of cryptographic hiding techniques, allowing a classical observer to trust a quantum machine's word with mathematical certainty.

The researchers are careful to note that their results depend on the existence of these obfuscation tools. While they have not built the tools themselves, they have shown exactly what properties they need and how to use them if they exist. They also showed that the security of their system does not require any additional, unproven assumptions about the future of computing power beyond the existence of the obfuscation and, for public verification, one-way functions. If the obfuscation holds, the verification holds. This separation of concerns allows the scientific community to focus on building the obfuscation tools while having a clear, verified framework for how they will be used.

In the end, this paper does not claim to have solved the problem of quantum verification with a finished product. Rather, it has drawn a precise map of the terrain. It shows that if we can scramble quantum programs effectively, we can verify them perfectly. It replaces the uncertainty of heuristic tests with the certainty of cryptographic proof. For the field of quantum computing, this is a shift from hoping a machine is working to knowing, with mathematical rigor, that it is. The work stands as a bridge between the abstract world of cryptographic theory and the practical need to trust the results of the next generation of computers.

Technical Summary: Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

Problem Statement

The paper addresses the fundamental challenge of establishing verifiable quantum advantage and classical verification of BQP computations in the near-term era. Existing approaches face a dichotomy:

Cryptographic proofs of quantumness (e.g., based on trapdoor claw-free functions) allow for efficient classical verification but require fault-tolerant quantum hardware, making them infeasible for current noisy devices.
Random circuit sampling (e.g., Google's Sycamore experiment) is implementable on near-term hardware but lacks efficient classical verification; verifying the output distribution requires exponential classical resources.

A heuristic proposal by Aaronson and Zhang (peaked circuit sampling) attempted to bridge this gap by embedding a hidden "peak" (a high-probability output string) into a complex circuit, allowing for efficient verification if the peak is known. However, previous attempts to obfuscate these circuits heuristically have been broken by classical attacks. The paper asks whether the security of such a scheme can be grounded in a rigorous cryptographic assumption rather than heuristic indistinguishability.

Methodology

The authors adopt a modular cryptographic approach, shifting the burden of security from heuristic circuit transformations to the primitive of Quantum Indistinguishability Obfuscation (qiO).

1. Cryptographic Framework

The core methodology relies on qiO, defined as a classical polynomial-time algorithm that takes a quantum circuit description and outputs an obfuscated circuit description. The security guarantee is that obfuscations of two circuits with the same "shape" (gate count, qubit counts) and negligibly close induced channels (in diamond distance) are computationally indistinguishable.

The paper constructs protocols assuming:

qiO: Specifically for ancilla-free unitary circuits and tidy circuits (circuits that return ancillas to zero).
Complexity Separation: A slightly stronger variant of $BQP \neq BPP$ , specifically $BQP \not\subseteq i.o.BPP$ (BQP is not contained in "infinitely-often" BPP).
Post-Quantum One-Way Functions (OWFs): For public verification protocols.

2. Protocol Construction

The authors design two primary types of protocols:

Proofs of Quantumness (PoQ):
- Private Verification: The verifier generates a random string $b$ and obfuscates a set of circuits. Each circuit is either an identity or a bit-flip, determined by $b$ . The prover runs these on $|0\rangle$ and returns the measured bits. The verifier checks if the output matches $b$ . Security relies on the indistinguishability of the obfuscated identity and bit-flip circuits, which is linked to the hardness of a BQP problem via a reduction.
- Public Verification: To remove the need for the verifier's secret state, the verifier publishes $y = f(b)$ , where $f$ is a one-way function. The prover returns $b'$ , and anyone can verify $f(b') = y$ . The paper proves that the existence of such classically secure OWFs is implied by the qiO and complexity assumptions used for the PoQ, requiring no additional hardness assumptions.
Classical Verification of BQP (CVQC):
- Private Verification: The verifier creates a grid of obfuscated circuits. Most are "test" circuits (simple bit-flips), while a few "planted" locations contain the obfuscated target BQP circuit $C$ masked by random bits. The prover returns a grid of measurement outcomes. The verifier checks the test locations and un-masks the planted locations to verify consistency. Security relies on the prover's inability to distinguish planted locations from test locations due to qiO.
- Public Verification: Similar to the PoQ, the verifier publishes parity information and one-way images of the expected answers. This allows any classical party to verify the result without secret state, assuming post-quantum OWFs.

3. Constructing qiO (Theoretical Foundations)

Recognizing that general-purpose qiO is a strong primitive, the paper proposes a path toward its construction inspired by the local-mixing framework of Canetti et al. (CCMR) for classical circuits.

Reduction to Ancilla-Free Circuits: The authors prove that qiO for "tidy" circuits (which use ancillas but return them to zero) can be constructed from qiO for ancilla-free unitary circuits. This involves a compilation technique that embeds the tidy circuit into a larger ancilla-free unitary, effectively hiding the action on non-clean inputs.
Worst-to-Average-Case Reduction: They propose a reduction showing that if one can obfuscate random ancilla-free circuits, one can obfuscate arbitrary ancilla-free circuits. This relies on two new assumptions:
1. Quantum Random Input Obfuscation (RIO): The ability to obfuscate random circuits such that the output looks like a post-processed ideal equivalent circuit.
2. Quantum Split-Circuit Pseudorandomness (SCP): The ability to hide the fact that a circuit was constructed by splitting and recombining parts with random separators.
3. Stability: An assumption ensuring that circuits with negligibly close channels yield indistinguishable obfuscations.

Key Contributions and Results

Rigorous Foundation for Peaked Circuit Sampling: The paper provides the first rigorous cryptographic realization of the "peaked circuit" concept. It replaces heuristic indistinguishability with a precise qiO guarantee, yielding a two-message, publicly verifiable proof of quantumness under the assumption $BQP \not\subseteq i.o.BPP$ and the existence of qiO.
Private CVQC without One-Way Functions: The authors construct a protocol for the private classical verification of arbitrary BQP decision problems using only qiO. This is a rare example of a non-trivial cryptographic application of (quantum) iO that does not rely on additional computational hardness assumptions (like LWE or trapdoor functions).
Public CVQC in the Standard Model: They present the first publicly verifiable protocol for classical verification of BQP computations in the standard model (without idealized oracles), assuming qiO and post-quantum OWFs.
Theoretical Path to qiO: The paper separates the cryptographic applications of qiO from the problem of constructing it. It provides a conditional route to constructing qiO for ancilla-free and tidy circuits via the local-mixing framework, extending the CCMR classical results to the quantum setting.
Implications for Complexity: The authors show that the existence of their proof of quantumness (with an efficient verifier) implies $P \neq NP$ , highlighting qiO as a "hardness transformer."

Significance and Claims

The paper claims to offer a rigorous cryptographic foundation for quantum advantage proposals that were previously heuristic. By grounding the security in qiO, it shifts the focus from breaking specific circuit constructions to the broader, well-studied problem of obfuscation.

Modesty on Construction: The authors explicitly state they do not provide a concrete instantiation of qiO. Instead, they provide a framework (the local-mixing reduction) in which candidate constructions can be studied and attacked.
Scope of Verification: The classical verification results are specifically for BQP decision problems (yes/no questions), not general sampling or relation problems.
Blindness: The private verification protocols are "computationally blind," meaning the prover learns nothing about the specific instance or the answer beyond the circuit's shape. The public verification protocols reveal the answer but hide the specific instance.
Assumption Hierarchy: The work clarifies the assumption landscape:
- Private PoQ and Private CVQC require only qiO and $BQP \not\subseteq i.o.BPP$ .
- Public PoQ and Public CVQC additionally require post-quantum OWFs (which the paper shows are implied by the PoQ assumptions, making them "free" in the PoQ context).

In summary, the paper establishes that if quantum indistinguishability obfuscation exists, then efficient, verifiable quantum advantage and classical verification of quantum computation are possible, providing a new theoretical paradigm for benchmarking quantum computers.