Source-linked AI summary
Interactive proofs for BQP via self-tested graph states (extended abstract)
Matthew McKague
TL;DR
The paper addresses how a classical verifier can check quantum computation and results without relying on classical prediction of complex experiments. It uses self-tested graph states for measurement-based computation, yielding interactive proofs for BQP with polynomially many non-communicating provers that each make one measurement when honest.
Problem
Classical prediction of complex quantum experiments can require exponential resources, motivating interactive proofs that let a verifier check quantum-computer results.
Source: §1 · p. 1Method
The construction combines graph-state self-testing with measurement-based quantum computation and specified single-qubit measurements.
Source: §1 · p. 3Results
For every language in BQP, a polynomial-time verifier has at least 2/3 completeness with honest provers and at most 1/3 soundness against arbitrary provers.
Source: §1 · pp. 2–3Takeaways & Limitations
The measurement-based computation follows the trusted-device model, allowing interactive proofs to be added by modifying only classical control.
Source: §1 · p. 3The construction assumes that the provers are quantum, which the authors note may create circularity when using it to experimentally verify quantum mechanics.
Source: §5 · p. 10
Abstract
from arXiv · showhide
Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in BQP with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. Our techniques use self-tested graph states which allow us to test the provers for honesty, establishing that they hold onto a particular graph state and measure it in specified bases. In this extended abstract we give an overview of the construction and proofs.
1 Introduction
The paper gives a classical verifier a way to check quantum computation through non-communicating quantum provers, using self-tested graph states and measurement-based computation. Its construction recognizes every language in BQP with polynomially many provers, each making only one one-qubit measurement when honest.
Motivation
- Interactive proofs can certify quantum-computer results when classical prediction of complex quantum experiments is infeasible.The introduction also notes that known BQP proofs via BQP ⊆ PSPACE and PSPACE = IP require the prover to solve PSPACE-complete problems.Source: §1 · pp. 1–2
Limitations
- The construction assumes quantum provers, while prior self-testing works also rely on repeated independent, identically used devices; [MMMO06] additionally assumes product-form states.The authors point to a possible circularity if interactive proofs with quantum computers are used to test quantum mechanics itself.Source: §1 · p. 2
Previous work
Contributions
- For every language in BQP, a polynomial-time verifier achieves at least 2/3 acceptance on yes-instances with honest provers and at most 1/3 on no-instances.The construction uses polynomially many non-communicating quantum provers, each performing a single one-qubit measurement in the honest case.Source: §1 · pp. 2–3
- The protocol combines self-testing of graph states and specified single-qubit measurements with measurement-based quantum computation.The tests establish that provers hold the required graph state and use the prescribed measurements.Source: §1 · p. 3
- The graph-state test improves error scaling exponentially in the graph size, enabling constant-error self-testing with polynomially many trials.The authors also analyze adaptive measurements and extend the test to X-Z-plane measurements for universal computation.Source: §1 · p. 3
- Unlike Reichardt et al. [RUV12], this measurement-based construction uses polynomially many constant-time provers, each making one measurement, rather than a constant number of polynomial-time provers.The provers need four measurement bases after graph-state preparation, and the construction requires no separate gate tests.Source: §1 · pp. 2–3
- The measured computation matches the trusted-device model, so interactive proofs can be added by modifying only the classical control.The paper contrasts this with Reichardt et al.'s need to teleport qubits between provers at each gate.Source: §1 · p. 3
2 Construction of the interactive proof protocol
The protocol randomly chooses computation or an honesty test, while preventing individual provers from distinguishing computation from testing. Repeating the protocol amplifies its acceptance gap to 2/3 versus 1/3.
2 Construction of the interactive proof protocol
- The verifier randomly chooses computation or testing, and structures the test so individual provers cannot distinguish computation from testing.A prover may recognize a test, but should not positively identify when computation is underway better than guessing.Source: §2 · p. 4
- The preliminary procedure has completeness cip and soundness sip bounds with cip>sip, but its gap can shrink as |x| increases.The protocol therefore repeats the procedure polynomially many times to amplify the gap.Source: §2 · p. 4
- For Lemma 2, when x∈L and the provers are honest, Algorithm 2 accepts with probability at least 2/3; when x∉L, it accepts with probability at most 1/3.Source: §2 · p. 4
- Repetition can be serial or parallel; in the parallel version, each prover is queried at most once.The acceptance gap amplification follows from a standard application of Hoeffding’s inequality.Source: §2 · p. 5
3 The Calculation
The calculation uses measurement-based quantum computation on a triangular cluster-state resource, with adaptive measurements that implement the computation. The resource is distributed across non-communicating provers, one vertex per prover.
3 The Calculation
- Measurement-based computation replaces gates with measurements on a prepared graph-state resource, with teleportation-induced unitaries and corrections absorbed into later behavior.The resource state depends on the size of the circuit to be performed.Source: §3 · p. 5
- Triangular cluster states are universal for measurement-based computation using X, Z, and X±Z measurements, with polynomially many vertices in the original circuit size.The construction uses the triangular-lattice graph as its resource-state geometry.Source: §3 · p. 6
- The measurement settings and output are computable in polynomial time, and each vertex’s setting may depend on earlier measurement outcomes.The calculation measures the resource-state vertices sequentially according to those settings.Source: §3 · p. 6
- The n-qubit cluster state is distributed among n provers, one vertex per prover, who measure in the requested basis and return ±1.Dishonest provers are assumed non-communicating and limited to quantum operations, with no restriction on their state-space dimension.Source: §3 · p. 6
4 Test for honesty
The honesty test samples measurement settings and checks outcomes against honest behavior. Its proof identifies logical qubits and a graph state within the provers’ systems, then relates passing the test to correct computation.
4 Test for honesty
- The proof models the provers’ joint state and each queried measurement as a two-outcome observable with responses ±1.The state is the one actually held by the provers; no Hilbert-space dimension assumption is made.Source: §4 · p. 7
- The verifier randomly selects a setting from M(L, x), queries the corresponding provers, and accepts when the combined outcome matches the expected result.The settings are built from a circuit-size-dependent triangular graph, triangles covering its vertices, and a fixed neighbor for each vertex.Source: §4 · p. 7
- Anticommuting X′_v and Z′_v identify a logical qubit, and the tested stabilizers establish that the logical qubits form the graph state |G⟩.The proof also relates the additional measurement operators to the corresponding logical-qubit measurements.Source: §4 · pp. 8–9
- A circuit analogous to SWAP moves the logical qubit into an ancilla, where prover operators X′_v and Z′_v act as logical X and Z.The proof tracks how applying X′_v or Z′_v before the swap corresponds to applying X or Z on the ancilla afterward.Source: §4 · p. 9
- The identified graph-state resources and measurements make the provers’ behavior equivalent to the honest protocol for the calculation.An individual prover cannot distinguish the test from the calculation on settings they share, so its behavior on those settings must be fixed across both.Source: §4 · pp. 7, 10
- When tested-setting statistics match the honest protocol, the sketch establishes that the calculation produces a correct result.The full robust proof is cited elsewhere; this sketch treats only the special case of matching honest-setting statistics.Source: §4 · pp. 8, 10
5 Discussion
The construction combines a size-dependent graph-state resource, simple prover measurements, and verifier calculations. Its scope assumes quantum provers and currently uses many constant-sized provers.
5 Discussion
- The graph state and test depend only on the calculation’s size, while provers need only measure in a fixed set of bases and the verifier performs lookups and XORs.The verifier reads gates from the input circuit and looks up the measurement angle for each gate.Source: §5 · p. 10
- No individual prover can determine whether the input is in the language; the verifier, provers, and state preparation together supply the needed computational power.The quantum components alone lack the XOR operations required for a full measurement-based calculation.Source: §5 · p. 10
- The construction assumes quantum mechanics applies to the provers, so using it to test quantum mechanics risks circularity.The authors propose treating the proof interaction itself as an experiment whose deviations from predicted behavior could signal a problem with the theory.Source: §5 · p. 10
- The current construction uses many constant-sized provers; a two-prover adaptation remains uncertain, particularly for graphs with odd cycles.The authors suggest bipartite graph states may still be self-tested with two provers.Source: §5 · p. 10