Verifying Quantum Computations
How can you check a computer you cannot simulate?
If a quantum computer solves a problem no classical computer can, how would you know it did? For factoring you multiply the factors. For a general BQP computation there may be no short certificate at all. Yet a purely classical verifier can check a quantum computer, under a cryptographic assumption, by forcing it to commit to its state before it learns how that state will be measured.
What you’ll learn
- Formalize verification as an interactive proof or argument, and explain why general BQP computations lack known short certificates.
- Prove single-qubit blindness of the Broadbent–Fitzsimons–Kashefi protocol, and explain trap-based verification.
- Explain how CHSH rigidity lets a classical verifier command two entangled provers.
- Derive the measurement protocol at the heart of Mahadev's classical verification, using trapdoor claw-free functions.
- Describe proofs of quantumness and certified randomness, and the assumptions they rest on.
The verification problem
Easy cases exist: factoring is in NP, so you check the factors. But BQP is not believed to lie in NP, and sampling tasks have no short certificate at all. Since (Shamir 1992), some classical interactive proof exists for every BQP language, but its honest prover needs PSPACE power. The real question, raised by Gottesman and framed by Aharonov and Vazirani as "Is quantum mechanics falsifiable?", is whether a BQP prover can convince a BPP verifier.
| Model | Verifier | Provers | Soundness | Landmark |
|---|---|---|---|---|
| Slightly quantum verifier | prepares or measures single qubits | one | information-theoretic | Aharonov, Ben-Or & Eban (2008); Broadbent, Fitzsimons & Kashefi (2009); Fitzsimons & Kashefi (2017) |
| Entangled provers | classical | two, non-communicating | information-theoretic | Reichardt, Unger & Vazirani (2013) |
| Single prover | classical | one | computational (LWE) | Mahadev (2018) |
Blind quantum computation
Universal blind quantum computation (Broadbent, Fitzsimons & Kashefi 2009) builds on measurement-based quantum computing: a computation is a sequence of single-qubit measurements at angles on a "brickwork" graph state, each angle adapted to earlier outcomes. The client hides the angles:
- The client sends qubits , each uniform in .
- The server entangles them into the brickwork state with CZ gates.
- For each qubit in turn the client sends , where is the adapted angle and a fresh random bit.
- The server measures in the basis and returns ; the client records .
The hiding rotation commutes with the entangling gates, so it can be moved to just before the measurement.
Measuring the rotated qubit at angle equals measuring the plain graph-state qubit at ; the extra just flips the outcome, which the client undoes with . That is correctness.
For fixed and , a uniform makes uniform: the classical message alone reveals nothing.
Given , the two equally likely values of leave . Averaged over , the server's qubit is maximally mixed whatever is, so its joint view is independent of the computation. The full proof handles adaptivity across many qubits the same way.
What would go wrong if the client always used ?
- Nothing; the random alone guarantees blindness
- Given , the server's qubit would be the pure state , which carries information about ; the returned outcomes would also be unpadded
- The computation would produce wrong answers
- The server could clone the client's qubits
Show the answer
B. Given , the server's qubit would be the pure state , which carries information about ; the returned outcomes would also be unpadded
With , fixes , so the qubit is a known function of the secret angle. A dishonest server could measure it in another basis to learn about , and the outcomes would reveal the computation's results. Averaging over makes the qubit maximally mixed and one-time-pads the outcomes.
Blindness becomes verification by hiding traps. The client secretly isolates some qubits (dummy or inputs break the graph around them) whose outcomes it can predict. A deviating server cannot tell traps from computation qubits, so it disturbs a trap with some probability. Encoding the computation in an error-correcting code, so that only deviations affecting many qubits matter, makes the acceptance probability of a wrong answer exponentially small (Fitzsimons & Kashefi 2017).
Suppose each independent round catches a deviating server with probability at least . How many rounds make the probability of never catching it at most ?
Show the answer
49 rounds
needs , so . Repetition amplifies soundness exponentially; trap-based protocols get a similar effect within one run through the error-correcting encoding.
Two entangled provers: CHSH rigidity
Reichardt, Unger and Vazirani (2013) removed the verifier's quantum device by using two provers who share entanglement but cannot communicate. The verifier interleaves many rounds of the CHSH game with rounds in which one prover helps prepare resource states and the other uses them, never telling either which kind of round it is in.
The original overhead was a large polynomial, later reduced, and the model needs provers who provably cannot communicate. The multi-prover story ended in a surprise: (Ji, Natarajan, Vidick, Wright & Yuen 2020), so entangled provers can convince a classical verifier of statements as hard as the halting problem.
A classical verifier: Mahadev's protocol
Mahadev (2018) showed that one quantum prover can be checked by a purely classical verifier, with soundness against quantum polynomial-time provers under the assumption that Learning With Errors (LWE) is hard for quantum computers. The setup has two layers.
- From BQP to measurements. Via Kitaev's circuit-to-Hamiltonian construction and later refinements, deciding a BQP language reduces to checking that a state has low energy for a local Hamiltonian built from and terms. It suffices for the verifier to obtain, for each qubit of the prover's state, the outcome of a or an measurement of its choice.
- A measurement protocol. The core of the work: make the prover commit to an -qubit state, then report or outcomes of the verifier's choosing, without being able to tell which basis was requested for which qubit.
The prover evaluates coherently, controlled on the committed qubit, over a uniform superposition of .
The prover sends , its commitment. With an injective key, determines , which the verifier recovers with the trapdoor: a -basis measurement has occurred, with . With a claw-free key the superposition survives, entangled with the claw.
In a Hadamard round the verifier asks for every qubit to be measured in the Hadamard basis. Factor out the phase .
Here means for and for : is an -basis outcome of the committed qubit. Only the verifier, who can compute and from with the trapdoor, learns ; the prover cannot even tell which kind of key it received.
In test rounds the verifier asks for a preimage and checks it. The adaptive hardcore bit property says no efficient prover can output both a valid preimage and a valid pair noticeably more often than chance. That forces a prover who passes tests to have genuinely committed to a qubit before seeing the basis.
Proofs of quantumness and certified randomness
A weaker goal than verifying a computation: prove that a device is quantum at all, or that its outputs are genuinely random. Brakerski et al. (2018) gave a single-device proof of quantumness. The verifier sends a claw-free key, the device commits to , and the verifier asks either for a preimage or for an equation . A quantum device answers either challenge using the claw state. A classical device could be rewound to answer both for the same , contradicting the adaptive hardcore bit property; so under LWE no classical device passes both kinds of challenge with high probability.
Other proofs of quantumness use different assumptions: Kahanamoku-Meyer et al. (2022) built one from a "computational Bell test" requiring fewer quantum operations, and Yamakawa and Zhandry (2022) one relative to a random oracle, with no algebraic structure. Certified randomness from random circuit sampling (Aaronson & Hung 2023) relies instead on the classical hardness of producing high-XEB samples quickly; in 2025 a trapped-ion experiment combined it with verification on classical supercomputers, with security resting on assumptions about an adversary's classical computing budget.
Key takeaways
- Verifying BQP means interactive proofs or arguments: completeness for an efficient honest prover, soundness against cheaters; NP-style certificates are not expected in general.
- BFK blindness: random and make each uniform and each qubit maximally mixed given ; hidden traps plus encoding turn blindness into verification.
- CHSH rigidity lets a classical verifier control two non-communicating entangled provers (RUV), and in the extreme .
- Mahadev's protocol uses trapdoor claw-free functions to make a single prover commit to qubits and reveal or hidden outcomes; soundness rests on the quantum hardness of LWE.
- The same tools give proofs of quantumness and certified randomness; practical verification remains open.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why is checking a quantum computer's answer easy for factoring but hard for general BQP problems?
- Factoring outputs are always small numbers
- Quantum computers cannot solve other problems
- Factoring is in NP, so multiplying the claimed factors verifies them; BQP is not believed to be in NP, so general answers need not have short certificates
- General BQP problems do not have definite answers
Show the answer
C. Factoring is in NP, so multiplying the claimed factors verifies them; BQP is not believed to be in NP, so general answers need not have short certificates
Verification is easy when a short certificate exists and is efficiently checkable. Factoring has one; for BQP-complete problems none is known, and is not believed.
In the Broadbent–Fitzsimons–Kashefi protocol, what does an honest-but-curious server learn?
- Only public parameters, such as the dimensions of the brickwork state
- The measurement angles, but not the input
- The input, but not the output
- Everything, though it cannot change the result
Show the answer
A. Only public parameters, such as the dimensions of the brickwork state
Each is uniform and each qubit is maximally mixed given ; outcomes are one-time-padded. Only the size of the resource state leaks.
Mahadev's protocol is computationally sound. What does that mean here, and which assumption is used?
- Sound against all provers; no assumption is needed
- Sound against classical provers only; it assumes factoring is hard
- It needs two non-communicating provers; it assumes LWE
- Sound against quantum polynomial-time provers, assuming LWE is hard for quantum computers
Show the answer
D. Sound against quantum polynomial-time provers, assuming LWE is hard for quantum computers
It is an argument: a cheating prover with unbounded power might succeed, but an efficient quantum prover cannot, as long as LWE resists quantum algorithms. Factoring would not do, since the prover is quantum.
In the claw-free case, after the Hadamard-basis measurement returns , who can compute the -basis outcome ?
- The prover, since it holds the claw state
- The verifier, using the trapdoor to find and from
- Anyone, since and are public
- Nobody: the information is destroyed by the measurement
Show the answer
B. The verifier, using the trapdoor to find and from
Computing needs , which requires finding the claw; that is hard without the trapdoor. The verifier holds the trapdoor, so only it decodes the outcome.
Further reading
- A. Broadbent, J. Fitzsimons & E. Kashefi, "Universal blind quantum computation", Proc. FOCS (2009).
- B. W. Reichardt, F. Unger & U. Vazirani, "Classical command of quantum systems", Nature 496, 456 (2013).
- U. Mahadev, "Classical verification of quantum computations", Proc. FOCS (2018); SIAM J. Comput. (2022).
- Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani & T. Vidick, "A cryptographic test of quantumness and certifiable randomness from a single quantum device", Proc. FOCS (2018); J. ACM (2021).
- A. Gheorghiu, T. Kapourniotis & E. Kashefi, "Verification of quantum computation: an overview of existing approaches", Theory of Computing Systems 63, 715 (2019).