Verifying Quantum Computations Protocols

Short answer: If a quantum computer produces an answer that no classical machine can check by brute force, how do you know it is right? Verification protocols address this by letting a verifier with little or no quantum power test a quantum prover through interaction. Papers from 2017 and 2018 give a classical verifier relying on a computational assumption, and a verifier that only prepares random single qubits with unconditional soundness. These are theoretical results in the language of interactive proof systems.

The question

A 2017 arXiv overview of verification approaches frames the problem. The quantum description of many-particle systems appears to need exponential resources to simulate, so the results of an experiment cannot in general be predicted by classical devices in reasonable time. That led Gottesman in 2004 to ask whether a classical verifier can verify quantum evolution, which Vazirani phrased as whether quantum mechanics is a falsifiable theory at large scale. The overview adds a practical point: experimentalists building quantum computers want to test that their systems perform correctly, yet tests whose predictions can be computed do not probe the aspects that cannot be simulated efficiently. It also notes a cryptographic version of the problem, since early quantum computers are expected to be very expensive.

Two weaker settings first

A 2018 arXiv paper recalls that, with no technique for the full question, two weaker versions were studied. In one, the verifier has access to a small quantum computer, and verification of all efficient quantum computations was shown possible. In the other, a classical verifier interacts with two entangled, non-communicating quantum provers and can verify arbitrary quantum computations.

A classical verifier, with an assumption

The same 2018 paper presents what it describes as the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. It builds a measurement protocol that lets a classical verifier use a quantum prover as a trusted measurement device. The prover must construct an n-qubit state of its choice, measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the results. Soundness rests on the assumption that the Learning with Errors problem is intractable for efficient quantum machines. The paper says the verifier may use post-quantum cryptography that the prover cannot break, and leaves open whether such a protocol is possible without that assumption.

Unconditional soundness with a small quantum ability

A 2018 Theory of Computing paper gives a different tradeoff. It shows any language in BQP has a quantum interactive proof system with a polynomial-time classical verifier who can also prepare random single-qubit pure states, and a quantum polynomial-time prover. Soundness is unconditional, holding even for computationally unbounded provers. The technique relies on encryption of the input, with computation on encrypted inputs, and on a random choice between three types of run, one computational and two tests. The authors say the overhead per run is linear in the circuit size and that the verifier needs no quantum memory or processing power. The proof uses a reduction to an entanglement-based protocol.

What this does not tell you

These are protocol designs and proofs, not an account of verification running on a device. The two approaches make different assumptions, one computational and one requiring random qubit preparation, so neither simply replaces the other.

FAQ

Why verify a quantum computation?

Because its output may be impossible for classical machines to check by direct simulation.

Can a purely classical verifier do it?

A 2018 arXiv paper gives a protocol for this, assuming Learning with Errors is hard for quantum machines.

Is an assumption always needed?

The paper leaves open whether the protocol is possible without it. A 2018 Theory of Computing protocol has unconditional soundness but lets the verifier prepare random single qubits.

What was the earlier approach?

Verifiers with a small quantum computer, or two entangled non-communicating provers.

Is this implemented on hardware?

These papers are theoretical and describe none.