131
Part Three · C · Complexity and cryptography

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 θ∈{0,π/4,…,7π/4}\theta\in\{0, \pi/4, \dots, 7\pi/4\}, then asks the server to measure at angle δ=ϕ+θ+rπ\delta = \phi + \theta + r\pi, where ϕ\phi is the angle the client actually wants and rr 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.

Why does the server learn nothing in blind computation?tap
Each measurement angle is shifted by a uniformly random secret θ + rπ, making the angles it sees uniformly random.
What forces two entangled servers to be honest?tap
Bell tests: only the intended measurements on maximally entangled states can win them near-optimally.
What assumption underlies Mahadev’s protocol?tap
That learning with errors is hard for quantum computers.

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?

P =

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).

Next · Chapter 132
Quantum key distribution: BB84, E91, security proofs, device independence

A key whose secrecy is guaranteed by physics. Real systems have still been hacked, through their hardware rather than the physics.

Turn the page