PaperlayerView exact revision on arXiv

Source-linked AI summary

Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources

Andrea Coladangelo, Alex Grilo, Stacey Jeffery, Thomas Vidick

arXiv:1708.07359v3quant-phcs.CCcs.CR

TL;DR

Classical verification of quantum computation requires protocols that control potentially untrusted quantum devices without prohibitive resource overhead. This paper introduces a robust rigidity theorem and combines it with Broadent’s quantum-verifier delegation protocol to obtain two-prover classical-verifier schemes with O(g log g) resources. One scheme is blind with depth-linear rounds, while the other uses constant rounds but is not blind.

  • Problem

    Classical parties need device-independent ways to verify quantum systems and delegate computations, but prior multi-prover protocols incur prohibitively large polynomial resource overheads.

    Source: §1 · p. 2

  • Method

    The paper introduces a rigidity test for arbitrary tensor products of single-qubit Clifford observables and combines it with Broadent’s EPR delegation protocol [Bro18].

    Source: §1 · pp. 4–5

  • Results

    The two classical-verifier protocols use O(g log g) resources; the first is blind with rounds linear in circuit depth, while the second is non-blind and constant-round.

    Source: §1 · pp. 5–6

  • Takeaways & Limitations

    Efficient rigidity can transform quantum-verifier delegation into quasilinear-resource classical-verifier delegation with a choice between blindness and constant-round interaction.

    Source: §1 · pp. 5, 7

    The rigidity robustness has an ε-dependence that the authors do not optimize and believe could scale as C√ε for a reasonable constant C.

    Source: §1 · p. 5

Abstract

from arXiv · show

The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two non-communicating but entangled quantum provers. Our protocols have near-optimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as $O(g\log g)$ for delegating a circuit of size $g$. This is in contrast to previous protocols, which all require a prohibitively large polynomial overhead. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit being delegated. The second protocol is not blind, but requires only a constant number of rounds of interaction. Our main technical innovation is an efficient rigidity theorem which allows a verifier to test that two entangled provers perform measurements specified by an arbitrary $m$-qubit tensor product of single-qubit Clifford observables on their respective halves of $m$ shared EPR pairs, with a robustness that is independent of $m$. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent (Theory of Computing, 2018).

1 Introduction

The paper addresses the high overhead of classical-verifier quantum delegation by introducing efficient rigidity tests and two two-prover protocols. The protocols achieve quasilinear resources while trading blindness against interaction rounds.

Motivation and prior work

  • The work targets prohibitively large prior overheads, including estimated g^8192 resources for [RUV13] and at least Ω(g^4 log g) for the most efficient prior multi-prover protocols.Earlier efficient approaches also sacrificed blindness, used weaker models, or relied on post-hoc verification.Source: §1 · p. 3

New rigidity results

  • The central technical contribution is a robust rigidity theorem for arbitrary m-qubit tensor products of single-qubit Clifford observables, with robustness independent of m.The theorem combines an extension of the Pauli braiding test to σY with a conjugation test for Clifford observables, while handling an undetectable complex-phase ambiguity.Source: §1 · pp. 4–5

New delegation protocols

  • O(g log g) total resources enable classical-verifier delegation of a g-gate quantum circuit with two entangled provers.The resource accounting includes prover operations, entanglement, and communication, with correctness amplified to 99% for comparisons in Table 1.Source: Table 1 · p. 4, §1 · p. 5

Open questions and directions for future work

  • The approach transforms Broadbent’s quantum-verifier delegation protocol [Bro18] into a classical-verifier protocol and may extend to other computation models.The authors identify measurement-based delegation [FK17] and computation by teleportation [RUV13] as possible starting points for similar transformations.Source: §1 · pp. 5, 7

New rigidity results

  • The rigidity theorem supports verifiable delegation by enforcing that the second prover performs the single-qubit and Bell-basis measurements used in Broadbent’s protocol.The test has completeness at least 1 − e^-Ω(m), and near-perfect success implies closeness to the intended EPR-pair strategy up to local isometries.Source: §1 · p. 5

New delegation protocols

  • The blind Verifier-on-a-Leash Protocol uses (2d + 1) rounds, O(n + g) EPR pairs, and O(g log g) time for a g-gate circuit of depth d.Blindness is obtained by hiding the circuit in the input to a universal circuit, which adds a log n factor to circuit depth and contributes overhead.Source: §1 · pp. 5–6
  • The non-blind Dog-Walker Protocol achieves constant-round interaction with the same O(g log g) time complexity, while the input is given to one prover in the clear.Both protocols adapt Broadbent’s EPR protocol and use rigidity to control a prover playing the quantum verifier’s role.Source: §1 · pp. 5–6
  • The Dog-Walker construction can be adapted to classical-verifier two-prover protocols for all languages in QMA.The first prover supplies and teleports a QMA witness, while the verifier delegates the verification circuit to the second prover.Source: §1 · p. 6

2 Preliminaries

The preliminaries establish notation and circuit conventions, then describe Broadbent’s EPR protocol as the basis for later delegation constructions. The protocol uses one-time pads, computation and test rounds, and EPR-based gadgets with completeness and soundness guarantees.

2.1 Notation

  • The rigidity-test notation represents strings of single-qubit observables and their associated projective measurements, including Pauli and Clifford observables.Observable strings are written as W = W1 · · · Wm, while measurement operators are constructed from commuting single-qubit observables.Source: §2.1 · p. 8

2.2 Quantum circuits

  • Quantum circuits are compiled over {H, T, CNOT}, with T depth defined by layering gates so each wire receives at most one T gate per layer.The compiled form may introduce extra T gates, while the resulting T depth remains proportional to the original circuit depth.Source: §2.2 · p. 9

2.3 Broadbent’s EPR Protocol

  • Broadbent’s EPR protocol delegates a BQP computation using a verifier with limited quantum powers and a prover, with a constant soundness-completeness gap.The verifier receives a circuit and input, interacts with the prover, and outputs accept or reject.Source: §2.3 · p. 9
  • If the circuit’s desired output probability is at most 1/3, the EPR protocol’s acceptance probability is bounded above by psound.The soundness analysis relates computation-round behavior to rejection in the test rounds.Source: §2.3 · pp. 9, 14
  • The protocol shares n + t EPR pairs: n pairs encode the input and t auxiliary pairs implement the circuit’s T gates.The verifier prepares one-time-padded input states and uses auxiliary EPR halves for the T-gate gadgets.Source: §2.3 · pp. 10–11
  • The verifier randomly selects computation, X-test, or Z-test rounds after interaction, preventing the prover from tailoring behavior to the round type.Computation rounds delegate the circuit, while test rounds check honest behavior; deviations affecting computation are intended to be detected by at least one test type.Source: §2.3 · p. 10
  • One-time-pad keys are updated after CNOT, H, and T gadgets, while test-round gadgets are designed to act as identity operations.The verifier tracks the keys throughout the computation, and the T gadget depends on a verifier-chosen random bit.Source: §2.3 · pp. 10–11, Table 2 · p. 10
  • For an honest prover, computation-round acceptance equals the circuit’s output probability, whereas test-round acceptance is 1.The resulting completeness bound is (1 − p) + p(1 − δ) when the desired output probability is at least 1 − δ.Source: §2.3 · p. 13

3 Rigidity

This section develops a robust rigidity framework for testing arbitrary tensor products of single-qubit Clifford observables, including conjugation, Pauli-braiding extensions, and tomography. It controls both the prover observables and the resulting post-measurement states, yielding a distributional characterization.

3 Rigidity

  • RIGID(Σ, m) certifies, up to local isometries, m shared EPR pairs and measurements matching the queried observables or their complex conjugates, with error poly(ε) independent of m.The honest strategy succeeds with probability 1 −e^-Ω(m), while the unavoidable Pauli-representation ambiguity is isolated in an ancilla bit.Source: §3 · pp. 14–16

3.1 Testing

  • The testing framework defines state-dependent equivalence and robust self-testing of operator relations up to local isometries, with consistency tests enforcing matching answers for identical questions.Modified tests mix the original game with a consistency check; success at least 1 −ε implies success at least 1 −2ε in both components.Source: §3.1 · pp. 16–17

3.2 The conjugation test

  • CONJ(A, B, R) is a (1, δ) self-test with δ = O(√ε), certifying the relation RAR† = B and an associated decomposition of the tested observable.The test does not directly access R because R need not itself be a measurement.Source: §3.2 · pp. 19–20

3.3 Testing Clifford unitaries

  • The Clifford-conjugation construction tests an m-qubit Clifford’s action on Pauli observables, extending the Pauli braiding test to tensor products that include σY.The extension accommodates the phase ambiguity that arises when testing σY; a simpler PBT(X, Z) variant remains available when Y need not be tested.Source: §3.3 · pp. 20–21
  • The Clifford conjugation test CONJ-CLIFF(R) certifies that an m-qubit Clifford operation is implemented under an isometry up to a unitary ambiguity commuting with the phase ambiguity ΔY.Its completeness is perfect for the honest strategy, while the soundness analysis has error polynomial in ε and independent of m.Source: §3.3 · pp. 21–23

3.4 Tensor products of single-qubit Clifford observables

  • Theorem 11 rigidifies tensor products of X, Y, Z, F, and G observables under a common isometry, with the remaining ambiguity determined by the locations containing F or G.The CLIFF test combines conjugation, consistency, multiplicativity, and cross-location checks to show that the ambiguity factors through a single observable ΛF commuting with ΔY.Source: §3.4 · pp. 24–25

3.5 Post-measurement states

  • Corollary 12 lifts the F/G outcome-label ambiguity using tomography, yielding a post-measurement-state characterization, while honest provers pass with probability 1 −e^-Ω(m).The tomography augmentation sacrifices perfect completeness but retains completeness exponentially close to 1.Source: §3.5 · pp. 26–27

3.6 Tomography

  • Corollary 13 shows that success in RIGID and TOM makes the second prover’s reported measurement and outcomes consistent with a distribution over the first prover’s post-measurement states.The tomography component has perfect completeness for honest provers and remains valid when the second prover chooses which measurement to report.Source: §3.6 · p. 29

4 The Verifier-on-a-Leash Protocol

The Leash Protocol combines sequential rigidity testing with a delegation game to enforce honest measurements while preserving blindness. It achieves constant completeness-soundness gaps and, using a universal circuit, can hide the computation input and circuit description from both provers, revealing only their lengths and sizes.

4.1 Protocol and statement of results

  • The protocol alternates between a sequential rigidity game and a delegation game, using m = Θ(n + t) EPR pairs and sequential interactions to enforce measurements and blindness.The verifier hides the game choice from PV; sequential rigidity retains the original rigidity guarantees because it reduces the provers’ ability to cheat.Source: §4.1 · pp. 30, 31, 35
  • The protocol leaks no information about the input x⃗ to either prover individually, except an upper bound on its length.PV’s sequential measurement schedule prevents later observable choices from influencing earlier answers, which is required for blindness.Source: §4.1 · p. 31

4.2 Completeness

  • For yes instances, honest provers are accepted with probability at least pcompl = pr(1 − e^-Ω(n+t)) + 8pd/9.The delegation game has the same honest success probability as Broadbent’s EPR Protocol, while the rigidity game succeeds except with probability e^-Ω(n+t).Source: §4.2 · p. 36

4.3 Soundness

  • For no instances, every prover strategy is accepted with probability at most psound = pcompl − ∆ for a constant ∆ > 0.Soundness first bounds cheating PP by 7/9 when PV is honest, then uses rigidity to replace an almost-honest PV with an honest one while losing only poly(ε).Source: §4.3 · pp. 36–38
  • The protocol achieves the desired constant completeness-soundness gap Δ.Source: §4.3 · p. 38

4.4 Blindness

  • Blindness holds against both provers for arbitrary strategies: each prover’s reduced state is independent of the input except for its length, and a universal-circuit transformation hides the circuit description as well.The proof compares the original and an alternative interaction order, showing identical final states via commuting prover actions and equivalent transcript-validity projections; this technique was previously used in [RUV13]. For a g-gate circuit on n qubits, the universal circuit uses O(g log n) gates, so the protocol reveals only g and n.Source: §4.4 · pp. 39–40

5 Dog-Walker protocol

The Dog-Walker protocol uses tomography and rigidity tests to support adaptive measurements in a two-round, two-prover classical-verifier setting. It achieves a constant soundness-completeness gap and yields a QMA verification game with polynomial communication.

5 Dog-Walker protocol

  • Two sequential interaction rounds replace blindness: V sends PP’s non-output outcomes and input x to PV, enabling PV’s adaptive measurements without further interaction.The protocol risks prover communication, but dishonest PP behavior is exposed in test rounds; only computation-round outcomes are forwarded.Source: §5 · pp. 40–41
  • The protocol adds a Tomography test and rigidity theorem because PV chooses measurements adaptively from prior outcomes and the input x.Its rounds combine EPR computation and testing with Rigidity Clifford and Tomography sub-rounds, selected using parameters p1, p2, p3, and p4.Source: §5 · p. 41, §5.1 · p. 41
  • The Dog-Walker Protocol extends to a classical-verifier two-prover protocol for all QMA languages by combining QMA verification, witness teleportation, and PV’s reusable computation gadgets.One prover runs the QMA verification circuit while the second creates and teleports the corresponding witness, allowing the verifier to check the first prover’s operations.Source: §5 · p. 41

5.2 Completeness

  • For ∥Π0Q|x⟩∥2 ≥ 2/3, honest provers achieve acceptance at least p_compl = p1(1 − e^-Ω(n+t)) + p2 + 2/3 p3 + p4.Rigidity-Tomography has perfect completeness, Rigidity-Clifford succeeds with probability at least 1 − δc, and EPR computation accepts according to the computation’s acceptance probability.Source: §5.1 · p. 41, §5.2 · p. 43

5.3 Soundness

  • For ∥Π0Q|x⟩∥2 ≤ 1/3, every prover strategy is accepted with probability at most p_sound = p_compl − Δ.The soundness proof uses a hybrid argument across Rigidity-Clifford, EPR-Test, EPR-Computation, and Rigidity-Tomography scenarios.Source: §5.1 · p. 41, §5.3 · pp. 44–45
  • Under the stated acceptance assumptions, there exist modified provers using honest strategies in Rigidity-Clifford, EPR-Test, and Rigidity-Tomography rounds, with a shared state consisting of m EPR pairs and arbitrary ancilla.If PV* plays honestly in EPR-Test rounds and q2 = 1 − ε′, the EPR-Computation input (⃗c,⃗z) is within O(ε′) total variation distance of uniform on {0,1}^t × {0,1}^t.Source: §5.3 · pp. 45–46
  • The protocol’s soundness follows by combining rigidity, EPR-test, and computation-round analyses, choosing round probabilities so error terms remain non-positive.Lemma 25 bounds acceptance by p1(1 − δc) + p2q2 + p3(5/3 − 4q2/3) + p4, while parameter choices yield the constant gap.Source: §5.3 · pp. 47–48
  • Any provers are accepted with probability at most p_sound = p_compl − ∆ for universal ∆ > 0 on no-instances satisfying the stated condition.This establishes a constant soundness-completeness gap for the Dog-Walker protocol.Source: §5.3 · p. 48

5.4 Two-prover game for QMA

  • The construction gives, to the authors’ knowledge, the first two-prover QMA game with a classical verifier, polynomial-size messages, honest quantum provers, and a constant completeness-soundness gap.The verifier and provers exchange messages in two rounds, one with each prover.Source: §5.4 · pp. 48–49
  • The QMA protocol adapts Dog-Walker rounds by teleporting witness states between EPR halves and using reported teleportation outcomes to decrypt computation outputs.X- and Z-Test rounds supply witness registers from selected EPR halves, while Rigidity-Computation and EPR-Computation rounds coordinate teleportation and verification.Source: §5.4 · p. 49
  • For a QMA instance with verification circuit size g and input length n, the protocol uses two rounds with O(n + g)-bit questions and O(n + g)-bit answers.Yes-instances are accepted with probability at least p_compl, while no-instance acceptance is bounded by the protocol’s soundness guarantee.Source: §5.4 · p. 51
  • Soundness combines Dog-Walker soundness with QMA-circuit soundness: after rigidity tests enforce honest behavior, the verifier rejects no-instance witnesses with high probability.If the rigidity and EPR-test rounds are sufficiently successful, an equivalent honest-strategy analysis changes EPR-Computation acceptance only slightly.Source: §5.4 · p. 52

6 Running our protocols in sequence

The protocols are sequentially repeated to amplify their small completeness-soundness gap and to distinguish computation outcomes using runs on Q and Q′. The resulting procedure can achieve 99% correctness, with exponentially small honest-abort probability and constant repetitions for constant-gap amplification.

6 Running our protocols in sequence

  • 99% correctness is obtained by sequentially repeating either protocol, while honest provers face an exponentially small abort probability.The sequential procedure either aborts or returns the correct computation outcome with probability 99%.Source: §6 · p. 52
  • For constant-gap amplification, the number of sequential repetitions remains constant, although stronger soundness targets require more rounds.The sequential protocol uses a security parameter κ and runs κ copies on each of Q and Q′.Source: §6 · p. 52, §6.1 · p. 53
  • The sequential construction is needed because the original protocols have only a very small constant completeness-soundness gap and rejection can falsely report a yes-instance as no.Sequential repetition amplifies the gap, while the paired Q/Q′ runs address this asymmetric rejection problem.Source: §6 · p. 52
  • The verifier runs the protocol on Q and on Q′, where Q′ appends an X gate to the output wire, then accepts only complementary outcomes.Matching outcomes cause an abort; complementary outcomes identify the result for the bounded-error computation.Source: §6 · p. 52, §6.1 · p. 53

6.1 Sequential version of our protocols

  • Theorem 28 states completeness and soundness guarantees for the sequential protocol in terms of the base protocol’s completeness c and gap ∆.The supplied theorem statement introduces separate guarantees for honest and cheating provers, but their explicit bounds are not included here.Source: §6.1 · p. 53
  • Soundness is analyzed with a super-martingale and Azuma’s inequality, treating the sequential dependence rather than each protocol as an isolated black box.The leash protocol requires an additional argument because it is blind; its soundness remains valid when the input is revealed.Source: §6.1 · pp. 53–54
  • The sequential leash construction remains blind, preserving the original protocol’s blindness property.This follows from an argument analogous to the soundness proof for the leash protocol.Source: §6.1 · p. 54

A Some simple tests

The appendix collects elementary tests used as building blocks, including Bell-basis and SWAP tests and a robust self-test for the m-qubit Pauli group.

A Some simple tests

  • The appendix reviews elementary tests, formulates a Bell-basis test with its associated two-qubit SWAP observable, and extends to self-test the m-qubit Pauli group.These tests are used as building blocks for the paper’s protocols.Source: A Some simple tests · p. 57

A.1 The Magic Square game

The Magic Square game provides a robust self-test for the two-qubit Weyl–Heisenberg group through consistency and parity constraints on provers’ answers.

A.1 The Magic Square game

  • The Magic Square game tests triples of commuting Pauli observables associated with rows or columns of the square.There are six questions, and each answer contains three values in {±1}.Source: §A.1 · p. 57
  • Accepted answers must be entrywise consistent and have product +1 on every row or column except the last, which requires −1.Source: §A.1 · p. 57
  • The honest strategy measures the commuting Pauli observables on two halves of shared EPR pairs.Source: §A.1 · p. 57
  • A near-perfect strategy is constrained by a self-test that yields local isometries extracting two-qubit systems and an auxiliary state.Lemma 29 applies when the strategy succeeds with probability at least 1−ε.Source: §A.1 · p. 57

A.2 Elementary tests

The elementary tests certify consistency, commutation, and observable relations, with robustness derived from the provers’ success probability.

A.2 Elementary tests

  • The elementary tests certify specified relations among observables, while every protocol also includes a consistency test comparing identical questions sent to both provers.Source: §A.2 · pp. 58–59
  • The commutation test accepts the honest strategy with probability 1 when the tested observables commute and the provers share a maximally entangled state.Source: §A.2 · p. 59
  • Success probability at least 1−ε in the commutation test implies approximate commutation, with error scaling as O(√ε).Source: §A.2 · p. 59
  • Under the lemma’s hypotheses, observables decompose into Pauli components whose unwanted components have norm bounded by O(δ1+δ2) and O(δ1+δ3).The resulting approximations isolate identity, X, Y, and Z components on an extracted qubit.Source: §A.2 · p. 59
  • The decomposition conditions can become vacuous when either δi equals 1.Source: §A.2 · p. 59

A.3 The Bell basis

The Bell-basis test uses commuting and anticommuting observables to certify a four-outcome Bell measurement and a corresponding qubit-swap observable.

A.3 The Bell basis

  • The Bell-basis test certifies a four-outcome projective measurement in the joint eigenbasis of X1X2 and Z1Z2.Source: §A.3 · p. 60
  • The test also checks an SW observable that exchanges the qubits specified by the observable pairs.The SW relation is checked alongside the Bell measurement relations.Source: §A.3 · pp. 60–61
  • The BELL test is a robust (1,δ) self-test with δ(ε) = O(√ε).Source: §A.3 · p. 60
  • The BELL test is complete for the honest Magic Square strategy using Bell-basis measurement and the specified SW observable.Source: §A.3 · p. 60
  • The Magic Square structure supplies commuting products X1X2 and Z1Z2, whose joint measurement has projectors Wc,d = (1/4)(1 + (−1)cZ1Z2)(1 + (−1)dX1X2).Source: §A.3 · p. 61

A.4 The m-qubit Pauli group

The section extends robust self-testing from the two-qubit setting to the m-qubit Pauli group, including σY observables.

A.4 The m-qubit Pauli group

  • The result formulates a robust self-test for the m-qubit Pauli group and extends prior work to allow testing of σY observables.Source: §A.4 · p. 61

A.4.1 The m-qubit Weyl-Heisenberg group

The m-qubit Weyl–Heisenberg group is characterized by tensor-product Pauli relations that can be robustly self-tested with error independent of m.

A.4.1 The m-qubit Weyl-Heisenberg group

  • The Pauli braiding test PBT(X, Z) tests tensor products of σX and σZ observables defining the m-qubit Weyl–Heisenberg group.Its tested relations include canonical anticommutation and coordinate-wise commutation and involution relations.Source: §A.4.1 · pp. 61–62
  • PBT(X, Z) is a robust (1, δ) self-test with δ(ε) = O(ε^1/2), independently of the number of qubits.Source: §A.4.1 · p. 62
  • The defining relations are δ-stable with δ(ε) = O(ε), so approximately satisfying them implies proximity to the intended Pauli observables up to a local isometry.Source: §A.4.1 · p. 62
  • The multi-qubit extension avoids the qubit-dependent error that would arise from applying the corresponding single-qubit lemma sequentially.Source: §A.4.1 · p. 62

(A similar claim holds with X replaced by Z.)

After extracting the tensor-product Pauli structure, an arbitrary observable can be decomposed into Pauli components whose relations constrain its nonidentity terms.

(A similar claim holds with X replaced by Z.)

A.4.2 The m-qubit Pauli group

The extended Pauli braiding test adds Y observables and resolves their otherwise undetectable complex-phase ambiguity, yielding a tensor-product Pauli self-test.

A.4.2 The m-qubit Pauli group

  • Classical correlations cannot detect complex conjugation, so the test represents the remaining choice between Y = iXZ and Y = −iXZ using an ancilla observable.Source: §A.4.2 · p. 63
  • The test enforces pairwise anticommutation among X, Y, and Z at each site while preserving the multi-qubit tensor-product structure.Source: §A.4.2 · pp. 63–65
  • The extended test PBT(X, Y, Z) combines Pauli testing, Y–X/Z anticommutation checks, and consistency tests to control the Y-observable phase ambiguity.Its third component uses SWAP-like comparisons between different Y(c) observables after Bell measurements connect registers.Source: §A.4.2 · p. 64, Figure 27 · p. 64
  • A strategy succeeding with probability at least 1 − ε in PBT(X, Y, Z) admits local isometries extracting m qubits and the intended Pauli observables.Source: §A.4.2 · p. 64
  • The analysis derives consistency and stabilization properties for X(a), Z(b), and Y(c), including averaged relations over random strings and permutations.Source: §A.4.2 · p. 65
Loading 1708.07359v3…