Verification of quantum computation
Suppose a company offers a quantum computer over the internet, and it returns an answer you cannot check yourself, because checking would need a quantum computer. How do you know it did the computation, rather than returning something plausible? For problems in NP, like factoring, you can verify the answer. For a general quantum computation, it is a genuine puzzle, and its solutions are among the most surprising results in the field.
On the plate: what a server sees when it computes for you blindly.
Interactive proofs with a quantum prover
Classical complexity theory already knew that a weak verifier can check a powerful prover by asking questions: interactive proofs can certify everything in PSPACE, which includes BQP. But those protocols need the prover to have unbounded power, not just a quantum computer. The goal is a protocol in which an honest quantum computer can convince you, a dishonest one cannot, and you need little or no quantum ability. Established
Blind computation
Anne Broadbent, Joseph Fitzsimons and Elham Kashefi gave universal blind quantum computation in 2009, built on measurement-based computing (Chapter 147). The client sends single qubits prepared at random angles , then asks the server to measure at angle , where is the angle the client actually wants and a random bit. Choose the client’s secret angle: , and . The server’s view is uniformly random whatever you choose: it learns nothing about the computation, the input or the output. Hide a few trap qubits with known outcomes among the real ones, and a server that deviates is caught with high probability. The client needs only to prepare single qubits. Established
No quantum at all: two routes
Two entangled servers. Ben Reichardt, Falk Unger and Umesh Vazirani showed in 2013 that a purely classical verifier can control two non-communicating quantum servers sharing entanglement, using Bell-inequality tests (Chapter 51) to force them to behave honestly. The same line of work led, in 2020, to MIP* = RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen: with entangled provers, a classical verifier can check answers to problems as hard as the halting problem. It also refuted a long-standing conjecture in operator algebras, Connes’ embedding problem.
One server, plus cryptography. In 2018 Urmila Mahadev, then a graduate student at Berkeley, gave a protocol in which a classical verifier checks a single quantum computer, assuming that the learning-with-errors problem (Chapter 133) is hard for quantum computers. The key tool is a trapdoor claw-free function: the server can create a superposition over two preimages but cannot find both, while the verifier, holding the trapdoor, can. Some assumption is believed necessary: without one, efficient classical verification of BQP with a single prover would have unlikely complexity consequences. Established
Trap tests compound: 10 independent rounds, each catching a cheating server with probability 1/2.
What you now have
Why verification is a problem, blind computation with hidden angles and trap qubits, two-prover verification and MIP* = RE, and Mahadev’s classical verification under the learning-with-errors assumption.
· · ·
Three questions to carry with you.
And one to work out. Each of 10 independent test rounds catches a cheater with probability 1/2. What is the probability a cheater escapes all ten?
Sources: A. Broadbent, J. Fitzsimons and E. Kashefi, Proc. 50th IEEE FOCS, 517 (2009). B. W. Reichardt, F. Unger and U. Vazirani, Nature 496, 456 (2013). U. Mahadev, SIAM J. Comput. 51, 1172 (2022) (FOCS 2018). A. Gheorghiu, T. Kapourniotis and E. Kashefi, Theory Comput. Syst. 63, 715 (2019). Z. Ji, A. Natarajan, T. Vidick, J. Wright and H. Yuen, arXiv:2001.04383; Commun. ACM 64, 131 (2021).