Source-linked AI summary
Interactive proofs for BQP via self-tested graph states
Matthew McKague
TL;DR
A classical verifier needs interactive proofs that use quantum computational resources while detecting malicious provers and addressing problems beyond the verifier's own computational power. The construction self-tests graph states and uses them for measurement-based quantum computation with adaptive measurements. For x ∈ L, there exists a set of honest quantum provers, each performing a single operation, such that V accepts with probability at least c = 2/3.
Problem
A classical verifier needs interactive proofs that use quantum computational resources while detecting malicious provers and addressing problems beyond the verifier's own computational power.
Source: §1 · pp. 1–2Method
The construction self-tests graph states and uses them for measurement-based quantum computation with adaptive measurements.
Source: §2.1 · p. 12, §3 · p. 18Results
For x ∈ L, there exists a set of honest quantum provers, each performing a single operation, such that V accepts with probability at least c = 2/3.
Source: §1.2 · p. 5Takeaways & Limitations
No single quantum prover has enough power to convince even itself whether the input is in the language; substantial computation requires combining the verifier, provers, and state preparation.
Source: §5.3 · p. 47Extending the approach to X-Y plane measurements is complicated by complex conjugation, which cannot be undone through an isometry.
Source: §5.4 · p. 47
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. In this regard we introduce two important improvements over previous work. Specifically, we derive new error bounds which scale polynomially with the size of the graph compared with exponential dependence on the size of the graph in previous work. We also extend the self-testing error bounds on measurements to a very general set which includes the adaptive measurements used for measurement-based quantum computation as a special case.
1 Introduction
The paper constructs interactive proofs for every language in BQP using polynomially many non-communicating provers, each performing a single operation when honest. It combines self-testing of graph states with measurement-based quantum computation.
1 Introduction
- The paper addresses interactive proofs in which a polynomial-time classical verifier queries a polynomial-time quantum prover and should detect malicious behavior.The motivation includes allowing a classical computer to use quantum computational resources while checking the interaction.Source: §1 · pp. 1–2
1.1 Previous work
- Earlier general BQP interactive proofs used PSPACE-complete prover computations, while this work studies polynomially many provers restricted to a single operation.Reichardt et al. [RUV12] instead use two provers, each running in polynomial time.Source: §1 · p. 2, §1.1 · p. 4
1.2 Contributions
- The graph-state error bound improves from exponential to polynomial dependence on graph size, and the measurement error analysis extends to adaptive patterns used in measurement-based computation.The paper also extends the graph-state test to X-Z plane measurements and applies its adaptive bounds to general quantum circuits incorporating untrusted measurements.Source: §1.2 · pp. 4–5
- For every language in BQP, honest provers each performing one operation achieve acceptance probability at least 2/3, while any provers on inputs outside the language are accepted with probability at most 1/3.The verifier interacts with a polynomial number of non-communicating quantum provers.Source: §1.2 · p. 5
1.3 Overview of construction
- The construction combines graph-state self-testing with measurement-based quantum computation, using the verified resources to perform the desired calculation.The verifier randomly tests honesty or performs the calculation, and calculation queries also occur in the honesty test.Source: §1.3 · pp. 6–7
- The honesty test samples among subtests and has an inverse-polynomial gap at constant error; deviations beyond δ reduce the pass probability below the honest rate by ε.The stated bound is ctest−ε, where ctest is the honest-prover pass probability and ε depends on δ.Source: §1.3 · pp. 6–7
2 Technical introduction
The section introduces measurement-based quantum computation and the graph-state resources used in the construction, then sets out the notation, closeness criterion, and prover model needed for the proof.
2 Technical introduction
- The section collects notation and definitions for the construction and proof, with further technical results placed in Appendix A.Source: §2 · p. 7
2.1 Measurement-based Quantum Computation
- MBQC prepares and entangles |+⟩ states, then measures qubits sequentially with adaptive bases; triangular cluster states support universal computation using X-Z-plane measurements with polynomial overhead.Source: §2.1 · pp. 11–12
2.2 Operators, isometries, bit strings
- The section establishes notation for tensor products, bit strings, and isometries, including local isometries acting separately on subsystems.Source: §2.2 · pp. 12–13
2.3 Graph states
- A graph state is stabilized by commuting graph-dependent operators and can be prepared from |+⟩ qubits with CTRL-Z gates on graph edges.Source: §2.3 · pp. 14, 16
2.4 Definition for “closeness”
- Closeness is defined up to a local isometry and an arbitrary junk state; the criterion cannot test imaginary components of ideal states or operators, which are real in this work.Source: §2.4 · p. 17
2.5 Modelling the provers
- Even dishonest provers can be modeled by a pure joint state and one observable per possible query, since each prover receives one query and returns one message.Source: §2.5 · p. 18
3 Test for honesty
This section develops honesty tests for graph-state provers, covering graph states, X–Z-plane and adaptive measurements. It relates test acceptance and self-testing error bounds to the accuracy of adaptive measurement outcomes.
3.1 Self-test for triangular cluster states
- The self-test uses modified techniques to identify triangular cluster states and X and Z measurements up to local unitaries and ancillas, and extends to any stabilizer state.The modifications are intended to tighten the error analysis and clarify notation.Source: §3.1 · p. 19
3.1.1 Preliminary technical estimations
- Because every triangular-lattice vertex lies in a triangle, the proof can establish local X′–Z′ anticommutation; the result extends to graphs where every vertex lies in a triangle.For connected graphs, one triangle or edge can suffice, but with a less robust result.Source: §3.1.1 · p. 20
3.1.2 Proof of Theorem 3
- The isometry proof uses an entangled-pair ancilla and an initial CTRL-X gate; the entangled ancilla enables tighter robustness analysis than the earlier circuit version.When the queried observables are Pauli X and Z, the circuit acts as a SWAP gate.Source: §3.1.2 · p. 23
3.2 Error bounds for non-Pauli measurements
- X–Z-plane measurements suffice for universal computation, and the graph-state test together with further measurements is used to derive error bounds for them.The prover’s measurement observable is not assumed in advance; its relationship is derived.Source: §3.2 · p. 28
3.3 Error bounds for measurement patterns
- Measurement-pattern bounds address sequential subsystem measurements whose bases depend on earlier outcomes, and the section considers the stronger case of coherent quantum queries and returned results.In this model, provers may choose their measurement observables, while their actions are required to have the specified form.Source: §3.3 · p. 30
- For any adaptive measurement made using the M′s, the probability of a particular outcome differs from the ideal case by at most 2(2nm + 1)δ.Source: §3.3 · p. 33
3.4 A one-shot test
- The test uses stabilizer checks that honest provers pass with certainty and Rθ compound checks whose quantum-limited success separates honest from cheating strategies.The honest strategy simultaneously passes the VERTEX and TRIANGLE subtests, while the Rθ checks have a matching honest value and quantum upper bound.Source: §3.4 · pp. 34, 35, 37, 38
- The one-shot graph-state test makes honest provers maximally successful, and excessive deviation in any adaptive outcome limits their acceptance probability.The test uses stabilizer-based vertex and triangle checks alongside Rθ subtests; its acceptance bound follows by combining the test’s self-testing guarantee with the adaptive-measurement error bound.Source: §3.4 · pp. 40–41
4 Interactive proofs
The protocol combines an honesty test with measurement-based computation on a triangular cluster state, then repeats the interactive proof to amplify its completeness–soundness gap.
4 Interactive proofs
- The verifier randomly chooses a test or a calculation, using the honesty test or the adaptive measurement-based computation, respectively.In the calculation branch, the adaptive measurement supplies each vertex’s measurement angle and adaptation functions.Source: §4 · pp. 41–42
- Theorem 1 gives an interactive proof for every language in BQP, with completeness at least c_ip for honest provers and soundness at most s_ip.The proof uses a polynomial-size triangular cluster state for the computation and amplifies the resulting protocol.Source: §4 · p. 44
- Repeating the protocol with fresh randomness preserves a per-trial soundness bound even when dishonest provers vary their behavior across trials.The analysis uses Hoeffding’s inequality; the repetitions can be run in parallel with nN provers, each queried once in the honest case.Source: §4 · pp. 44–45
5 Discussion
The discussion states the construction’s quantum-mechanics assumption and reviews its implementation trade-offs, simplicity, measurement scope, and future directions.
5.1 Assumptions
- The argument assumes provers obey quantum mechanics, so using it to verify quantum mechanics itself would be circular.The authors leave open whether BQP interactive proofs are possible without that assumption.Source: §5.1 · pp. 45–46
5.2 Time-space trade-offs
- Gap amplification trades prover count against measurements per prover, while triangular-cluster-state preparation remains polynomial and can have constant circuit depth.The parallel option uses nN provers with one measurement each; triangular states require at most 3n two-qubit gates, plus n single-qubit preparations.Source: §5.2 · p. 46
5.3 Simplicity
- Triangular cluster states and a discrete measurement set let the verifier read circuit gates, look up measurement angles, and perform the remaining XORs.The provers need only fixed measurement bases, and the state preparation and self-testing depend on the calculation size.Source: §5.3 · pp. 46–47
- No individual prover can perform the full calculation: the quantum resources lack the XOR operations needed to complete measurement-based computation.The verifier, provers, and state preparation together provide the capacity for substantial calculations.Source: §5.3 · p. 47
5.4 X-Y plane measurements
- The usual X-Y-plane graph-state model is a possible extension, but complex-conjugated provers do not satisfy equation (23) as stated.A suitable relaxation may work; the authors identify making the techniques robust and extending them to X-Y measurements as remaining tasks.Source: §5.4 · p. 47
5.5 Future work
- The error bounds are suboptimal because several estimates are loose, leaving tighter bounds as a future improvement.The current construction uses many simple provers, complementing Reichardt et al.’s constant-prover result.Source: §5.5 · p. 47
- Much of the construction may adapt to two provers, but odd cycles likely obstruct the graph-state self-test; bipartite graph states remain a possibility.The stated difficulty is testing entanglement across an edge whose vertices are held by one prover.Source: §5.5 · p. 48
A Technical lemmas for estimation
This appendix collects technical estimates used in the proofs, including norm inequalities and averages over bit strings and graph subsets.
Technical estimates
- For normalized states and involutions with high expectation on one state, the proof uses norm definitions, the triangle inequality, and an operator-norm bound.The cited lemma states premises involving errors α and β, but the supplied passage does not give its conclusion.Source: A Technical lemmas for estimation · p. 52
- Averaging the parity character over n-bit strings gives 1 for the zero string and cancels to zero for any nonzero string.For nonzero t, half the strings have inner product 0 with t and half have inner product 1.Source: A Technical lemmas for estimation · p. 52
- For a uniformly chosen vertex subset, each graph edge is included with probability one quarter, yielding an expected induced-edge count of 2^(n-2)|E| across all bit strings.The passage also relates average inner products with a fixed bit string to half its number of ones, and to n/2 for an average string.Source: A Technical lemmas for estimation · p. 52
B Local complementation and self-testing stabilizer states
The appendix explains how local complementation relates graph states and how component-wise self-testing establishes the needed local relations.
Local complementation
- Local complementation toggles edges among a vertex’s neighbors and relates the resulting graph states by local Clifford operations that relabel Pauli measurements and outcomes.The stabilizer generators change by multiplying neighboring generators by the complemented vertex’s generator and exchanging specified Pauli operators.Source: B Local complementation and… · p. 53
Self-testing stabilizer states
- Because every stabilizer state is locally Clifford-equivalent to a graph state, testing stabilizer states reduces to testing graph states.The local Clifford operations relabel Pauli operators, up to sign.Source: B Local complementation and… · p. 53
- Self-testing handles graph components separately: isolated vertices are trivial, while two-vertex components are EPR pairs testable with Mayers-Yao or CHSH.The component graph state factors as a product across connected components.Source: B Local complementation and… · p. 53
- For larger connected components, a triangle test establishes approximate anticommutation, which propagates along paths; local complementation can create a triangle from an induced length-two path.The component isometry is then formed by tensoring the isometries for its components.Source: B Local complementation and… · pp. 53–54