PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust self-testing of many-qubit states

Anand Natarajan, Thomas Vidick

arXiv:1610.03574v1quant-phcs.CC

TL;DR

The paper addresses the poor scaling of existing self-tests for many-qubit states. It introduces a two-player Pauli test combining quantum linearity and anticommutation checks, with constant robustness, and applies it to EPR-pair certification, Hamiltonian verification, and delegated computation.

  • Problem

    Existing self-tests for n-qubit states had robustness that degraded polynomially with n, limiting certification of large entangled states.

    Source: §1 · p. 1

  • Method

    The paper combines X- and Z-basis quantum linearity tests with an anticommutation game to certify tensor-product Pauli observables.

    Source: §1.2 · p. 5

  • Results

    Near-optimal strategies are poly(ε)-close to the ideal strategy with robustness independent of n, yielding robust n-EPR self-testing and related protocols.

    Source: §1 · p. 2, §1.2 · p. 5

  • Takeaways & Limitations

    The construction supports constant-gap multiprover verification for suitable local Hamiltonians and robust delegated computation with a classical verifier.

    Source: §1.1 · p. 4

    The Hamiltonian protocol uses polynomial-length rather than logarithmic questions, and the delegated-computation protocol is not blind.

    Source: §1.1 · p. 4, §1.4 · p. 7

Abstract

from arXiv · show

We introduce a simple two-player test which certifies that the players apply tensor products of Pauli $\sigma_X$ and $\sigma_Z$ observables on the tensor product of $n$ EPR pairs. The test has constant robustness: any strategy achieving success probability within an additive $\varepsilon$ of the optimal must be $\mathrm{poly}(\varepsilon)$-close, in the appropriate distance measure, to the honest $n$-qubit strategy. The test involves $2n$-bit questions and $2$-bit answers. The key technical ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld. As applications of our result we give (i) the first robust self-test for $n$ EPR pairs; (ii) a quantum multiprover interactive proof system for the local Hamiltonian problem with a constant number of provers and classical questions and answers, and a constant completeness-soundness gap independent of system size; (iii) a robust protocol for delegated quantum computation.

1 Introduction

The paper develops robust self-tests for Pauli observables and many-qubit states, addressing prior robustness that degraded with the number of tested qubits. It applies the construction to EPR-pair certification, local Hamiltonians, delegated computation, and related quantum PCP questions.

1 Introduction

  • Robustness independent of n lets near-optimal strategies encode eigenvectors of averaged Pauli operators up to local isometries.The test applies when the target is characterized by tensor-product σX, σZ, or ±I observables; n EPR pairs arise as a principal example.Source: §1 · pp. 1–2

1.1 Applications

  • For XZ local Hamiltonians, the construction yields a one-round protocol with seven entangled provers, classical polynomial-length questions, constant-length answers, and a constant gap when the promise gap is inverse-polynomial.The gap is independent of system size, but the questions are polynomial rather than logarithmic in length.Source: §1.1 · pp. 2–4
  • The resulting two-player game robustly self-tests n EPR pairs with O(n)-bit questions and O(1)-bit answers, achieving distance δ = poly(ε) from the ideal state.A Magic Square instantiation gives perfect completeness using (n + 1) EPR pairs.Source: §1.1 · p. 4
  • The delegated-computation application gives a classical-verifier protocol with a constant number of BQP provers and a size-independent constant gap, but it is not blind.The verifier must reveal the entire circuit to all provers before verification.Source: §1.1 · p. 4

1.2 Proof overview

  • The Pauli braiding test combines X- and Z-basis linearity tests with an anticommutation game to certify quantum observables rather than classical linear functions.It uses two-player questions of length 2n and constrains the relation between the two incompatible bases.Source: §1.2 · p. 5
  • The proof encodes quantum states into a constant number of shares and extends stabilizer-based tests to obtain constant-ε guarantees, at the cost of linear-length questions.The construction combines locally verifiable encoding with a quantum analogue of the BLR linearity test.Source: §1.2 · pp. 4, 6

1.3 Related work

  • Compared with prior many-EPR self-tests, the work removes robustness dependence on the number of tested pairs through its linearity tests.The main unresolved efficiency question is whether the test can be derandomized to sublinear or logarithmic questions.Source: §1.3 · p. 7, §1.4 · p. 7

1.4 Open questions and future directions

  • Open directions include preserving completeness for alphabet reduction when honest strategies are not maximally entangled and developing parallel device-independent QKD.The paper also asks whether its framework supports broader device-independent property tests.Source: §1.4 · p. 7

2 Preliminaries

The preliminaries define the quantum states, Pauli observables, stabilizer-code and local-Hamiltonian settings, state-dependent approximation measures, and nonlocal-game framework used later.

2.1 Quantum states and measurements

  • Quantum states are vectors or density matrices, and measurements are POVMs whose outcome probabilities are given by Tr(M_iρ); POVMs may be dilated to projective measurements.Observables are Hermitian operators squaring to identity, with ±1 eigenvalues and expectation values determined by the state.Source: §2.1 · p. 8
  • Pauli observables provide an orthogonal basis, while σX(a) and σZ(b) encode which qubits receive X or Z rather than identity.The bit strings a and b specify the acted-on qubits, enabling two-basis descriptions of many-qubit operators.Source: §2.1 · pp. 8–9

2.2 Stabilizer codes

  • CSS stabilizer codes use commuting Pauli-I/X/Z generators, with logical X and Z operators and stabilizer partners that extend single-qubit Paulis across the code.These structural properties eliminate σY from the relevant operators and support the protocol’s two-basis formulation.Source: §2.2 · p. 9

2.3 Local Hamiltonians

  • Local Hamiltonians are positive semidefinite sums of bounded k-local terms, and deciding whether their minimum eigenvalue is below a or above b is QMA-complete for suitable XZ-restricted families.The paper focuses on Hamiltonians whose terms use only tensor products of I, σX, and σZ.Source: §2.3 · p. 10

2.4 State-dependent distance measure and approximations

  • State-dependent distances compare operators or POVMs on a particular state, while consistency and Naimark dilation support transferring approximate relations to projective measurements.Approximately commuting observables can be replaced by a nearby observable representing their product; Lemma 7 gives dρ(AB,C)^2 ≤ δ^2/2.Source: §2.4 · pp. 10–12

2.5 Nonlocal games

  • A nonlocal game is a one-round classical interaction in which a verifier distributes questions to entangled players and accepts or rejects their answers.The quantum value ω∗(G) is the largest winning probability achievable with shared entanglement; completeness and soundness characterize honest and near-optimal strategies.Source: §2.5 · pp. 13–14
  • CHSH and Magic Square are anticommutation games: CHSH uses one EPR pair for an optimal strategy, whereas Magic Square has value 1 but requires two EPR pairs.The anticommutation condition is needed for the Hamiltonian self-test but not for the Pauli braiding test.Source: §2.5 · pp. 13–14

3 The linearity test

The linearity test turns approximate quantum linearity into exact linear observables and uses a two-player protocol to test consistency across incompatible X and Z bases.

3 The linearity test

  • A quantum two-player variant of the Blum–Luby–Rubinfeld linearity test uses oracularization with a dummy question and matrix-valued Fourier analysis.Its two-player form is essential because later self-tests require consistency in mutually incompatible X and Z bases.Source: §3 · p. 14
  • Approximate expectation-valued linearity can be rounded, after adding an ancilla, to observables satisfying A(a)A(b) = A(a + b) exactly while remaining close on average in state-dependent distance.Here a + b is bitwise XOR, and the rounded observables obey the exact linear relations for all a,b.Source: §3 · pp. 14–15
  • The rounding constructs a Fourier-transformed POVM, applies Naimark dilation to obtain projectors, and derives observables from the dilated measurement.This supplies the exact-linear observable family used in the subsequent test analysis.Source: §3 · pp. 15–16
  • The two-player protocol sends each player a pair of n-bit strings, with the verifier selecting consistency or linearity checks; success at least 1−ε yields the theorem’s approximate linearity conclusion.The protocol assumes the strings are presented in lexicographic order and analyzes separate consistency and linearity error contributions.Source: §3 · pp. 15–16

4 The Pauli braiding test

This section presents the Pauli braiding test and its proof, combining linearity and anticommutation tests to certify tensor-product Pauli observables. It establishes approximate Pauli relations and consistency through operator transfers, yielding a robust self-test for n EPR pairs.

4 The Pauli braiding test

  • The test combines linearity with an anticommutation game to certify tensor products of σX and σZ observables satisfying Pauli braiding relations.Near-optimal strategies are close in state-dependent distance to operators obeying the commutation and anticommutation relations under a local isometry.Source: §4 · p. 17

4.1 The protocol

  • The protocol uses W-queries for X or Z observables and G-queries from an anticommutation game, with players answering two bits or one game answer.Strategies may be represented using a shared pure state and projective measurements by Naimark’s theorem.Source: §4.1 · p. 18

4.2 Statement of results

  • Theorem 13 derives approximate consistency, linearity, and anticommutation relations from near-optimal success in the Pauli braiding test.The commutation relation is obtained separately as a consequence of the other tested properties.Source: §4.2 · p. 19, §4.3.3 · p. 22
  • Theorem 14 shows that these approximate relations imply observables satisfying exact Pauli braiding relations after extending the systems and applying a local isometry.The resulting observables obey P^A(a,b)P^A(a′,b′) = (−1)^(a′·b)P^A(a+a′,b+b′), with analogous relations for Bob.Source: §4.2 · pp. 19–20

4.3 Proof of Theorem 13

  • The analysis of Theorem 13 combines consistency, linearity, anticommutation, and derived commutation properties from the protocol’s subtests.Consistency establishes cross-player agreement, linearity comes from the linearity test, and anticommutation applies when a·b = 1 mod 2.Source: §4.3 · p. 20

4.3.1 Consistency Test

  • A consistency-test success probability of 1 − ε yields cross-player X and Z observables within ε_stab = O(ε) in state-dependent distance.The honest strategy succeeds in the consistency test with probability 1.Source: §4.3.1 · p. 21, §5.4 · p. 30

4.3.2 Anticommutation test

  • The anticommutation test enforces anticommutation when a·b = 1 mod 2, while commutation for a·b = 0 mod 2 follows from linearity, consistency, and anticommutation.Thus the protocol need not include a separate commutation test.Source: §4.3.2 · p. 21, §4.3.3 · p. 22

4.4 Proof of Theorem 14

  • Theorem 14’s proof constructs corrected observables using EPR ancillas, applies the linearity test over {0,1}^2n, and obtains observables close to the required Pauli representation.The construction produces D(a,b) with D(a,b)D(a′,b′) = D(a+a′,b+b′) and average distance O(ε^1/8) from the intermediate operators.Source: §4.4 · pp. 23–24
  • The proof handles operators P_A(a,0) by exploiting the exact Pauli braiding relation for a fixed coordinate.This step uses the exact relation together with approximate consistency to establish the needed operator consistency.Source: §4.4 · p. 24
  • Approximate consistency is applied repeatedly to shift Z_A(d) and X_A(c) to Bob’s space and relate the resulting operators.The argument invokes approximate consistency of P_A multiple times, including after applying anticommutation and linearity.Source: §4.4 · p. 25
  • The derivation combines approximate anticommutation with approximate linearity to combine X_A(a+c) and X_A(c) and complete the consistency argument.These steps use property 3 for anticommutation and property 2 for linearity, followed by approximate consistency with X_B(c).Source: §4.4 · p. 25

5 The Hamiltonian Self-Test

The Hamiltonian self-test encodes a ground state in a CSS code and combines Pauli-braiding, energy, and consistency tests to certify its energy-related observables. Its completeness and soundness hold for XZ Hamiltonians, with gap amplification yielding constant-gap verification.

5 The Hamiltonian Self-Test

  • The protocol restricts to Hamiltonians formed from tensor products of I, σX, and σZ, encoding each ground-state qubit with a CSS code across r players.The Pauli-braiding tests are lifted to physical players because Pauli measurements can be implemented transversally in CSS codes.Source: §5 · pp. 25–26, §5.1 · p. 26

5.1 The protocol

  • The verifier randomly combines a Pauli-braiding test, an energy test measuring a Hamiltonian term, and an energy-consistency test linking XZ measurements to Pauli observables.The honest strategy applies Pauli-braiding measurements for X, Z, and G queries, and measures compatible σX(a) and σZ(b) for XZ queries.Source: §5.1 · pp. 27–29, §5.4 · p. 30

5.2 Statement of results

  • Theorem 23 bounds every strategy’s success probability by ωhonest(H) + η when the energy-test probability is chosen as p = Θ(η1−d).The theorem applies to not-necessarily-local Hamiltonians with terms of the form Hℓ = σX(aℓ)σZ(bℓ).Source: §5.2 · pp. 29–30

5.3 Analysis of the energy test

  • The energy test estimates a randomly selected Hamiltonian term, while the consistency analysis relates special-player XZ measurements to the Pauli operators certified by the braiding test.The honest strategy succeeds in the consistency test with probability 1.Source: §5.3 · p. 30, §5.4 · p. 30

5.5 Amplification

  • Gap amplification shifts the Hamiltonian and tensors sufficiently many copies, converting inverse-polynomial energy separation into constant thresholds for a non-local instance.For suitable p(n) > q(n), the amplified Hamiltonian has λmin(H′) ≤ 1/2 in the low-energy case and λmin(H′) ≥ 1 in the high-energy case.Source: §5.5 · pp. 32–33
  • The amplification result is combined with Theorem 23 to obtain a protocol with constant completeness-soundness gap, while preserving classical constant-size answers and polynomial-length questions.The construction relies on allowing non-local XZ Hamiltonians in the self-test.Source: §5.5 · p. 33

6 Delegated Computation

The paper turns its Hamiltonian verification protocol into post-hoc delegated quantum computation using the Feynman-Kitaev history Hamiltonian. The resulting one-round protocol has seven quantum entangled players, a classical verifier, and a constant gap independent of circuit size.

6 Delegated Computation

  • A poly-size circuit is encoded as a Feynman-Kitaev history Hamiltonian whose ground-state energy reveals whether the computation accepts or rejects.The honest players prepare the encoded history state and distribute its shares before verification.Source: §6 · pp. 33–34
  • The delegated-computation scheme has a constant completeness-soundness gap independent of circuit size, but it is not blind because the verifier reveals the entire circuit.This contrasts with the cited schemes [FH15] and [RUV13].Source: §6 · p. 33
  • Theorem 27 gives a one-round interactive proof with seven quantum entangled players, polynomial-bit questions, constant-bit answers, and honest players requiring only BQP power.The verifier announces the history Hamiltonian and runs the Hamiltonian self-test.Source: §6 · pp. 33–34
Loading 1610.03574v1…