PaperlayerView exact revision on arXiv

Source-linked AI summary

Interactive Proofs For Quantum Computations

Dorit Aharonov, Michael Ben-Or, Elad Eban

arXiv:0810.5375v2quant-ph

TL;DR

The paper addresses how to verify arbitrary quantum computations when their outcomes cannot be efficiently predicted classically. It defines QPIP, combining a BQP prover with a BPP verifier having limited quantum access, and proves protocols for Q-CIRCUIT that are fault tolerant and can be made blind. The results include BQP = QPIP, while correctness guarantees depend on sufficiently frequent non-abort and the verifier retains a small quantum register.

  • Problem

    The paper asks whether customers or experimentalists can verify arbitrary quantum computations when classical devices cannot efficiently predict their outcomes.

  • Method

    The paper defines QPIP with a BQP prover and a BPP verifier holding a constant number of qubits, using quantum authentication schemes for verification.

  • Results

    The paper proves that Q-CIRCUIT has a QPIP, yielding BQP = QPIP, with protocols that also support local noise and blind computation.

  • Takeaways & Limitations

    These protocols provide a way to verify computations in BQP without requiring the verifier to classically simulate the underlying quantum computation.

  • Takeaways & Limitations

    The guarantees require a verifier with a constant-size quantum register, and the Shor-based approach does not fully address universal quantum computation.

Abstract

from arXiv · show

The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantum computers might already be too large to be simulated classically. Is it possible to experimentally test that these systems perform as they should, if we cannot efficiently compute predictions for their behavior? Vazirani has asked: If predicting Quantum Mechanical systems requires exponential resources, is QM a falsifiable theory? In cryptographic settings, an untrusted future company wants to sell a quantum computer or perform a delegated quantum computation. Can the customer be convinced of correctness without the ability to compare results to predictions? To answer these questions, we define Quantum Prover Interactive Proofs (QPIP). Whereas in standard Interactive Proofs the prover is computationally unbounded, here our prover is in BQP, representing a quantum computer. The verifier models our current computational capabilities: it is a BPP machine, with access to few qubits. Our main theorem can be roughly stated as: "Any language in BQP has a QPIP, and moreover, a fault tolerant one". We provide two proofs. The simpler one uses a new (possibly of independent interest) quantum authentication scheme (QAS) based on random Clifford elements. This QPIP however, is not fault tolerant. Our second protocol uses polynomial codes QAS due to BCGHS, combined with quantum fault tolerance and multiparty quantum computation techniques. A slight modification of our constructions makes the protocol "blind": the quantum computation and input are unknown to the prover. After we have derived the results, we have learned that Broadbent at al. have independently derived "universal blind quantum computation" using completely different methods. Their construction implicitly implies similar implications.

1 Introduction

The paper asks whether a classical verifier with limited quantum capability can verify arbitrary quantum computations, and defines QPIP to address this problem. It establishes QPIP protocols for Q-CIRCUIT, including fault-tolerant and blind variants, while identifying limits and open questions.

  • 1.2 Quantum Prover Interactive Proofs (QPIP): QPIP models a BQP prover interacting with a BPP verifier that has access to only a constant number of qubits.The verifier is intended to represent current computational capabilities while retaining limited quantum access.
  • 1.3 Main Results: Q-CIRCUIT has a QPIP, and because it is BQP-complete, the paper concludes that BQP = QPIP.The QPIP formulation captures verification of computations represented by polynomial-size quantum circuits.
  • 1.3 Main Results: The QPIP result remains valid under the usual local noise model used in quantum fault-tolerance settings.The theorem extends the basic protocol to a fault-tolerant setting.
  • 1.3 Main Results: A blind QPIP hides both the quantum circuit and its input from the prover.The construction uses a fixed universal quantum circuit, which reveals neither the encoded circuit nor the input string.
  • 1.4 Proofs Overview (and More Results About Quantum Authentication Schemes): The simpler protocol uses a new random-Clifford quantum authentication scheme, while the fault-tolerant construction uses signed polynomial-code authentication and related fault-tolerance techniques.The polynomial-code approach addresses complications arising when authenticated qubits must support fault-tolerant computation.
  • 1.5 Interpretations of the Results: Correctness of the final state requires a high probability of non-abort: conditioned on non-abort probability at least γ, the trace distance is at most 2δ.The paper notes that a prover may otherwise force aborts frequently while producing an incorrect state when the verifier does not abort.
  • 1.5 Interpretations of the Results: Under an additional hardness assumption, a prover who avoids aborting with high probability cannot be simulated by a BPP machine.The assumption involves a BQP language and a efficiently samplable distribution on which BPP errs with non-negligible probability.
  • 1.5 Interpretations of the Results: The verifier still requires a constant-size quantum register, and removing it or extending the model to multiple provers remains open.The paper also leaves open whether multiprover QPIP can work with classical communication only.

2 Background

The background introduces Pauli and Clifford groups, their algebraic relations, and signed polynomial codes used for quantum authentication. Clifford operators preserve the Pauli group under conjugation, while the signed polynomial code uses m = 2d + 1 coordinates to detect d errors.

  • Generalized Pauli operators X, Z, and Y act over F_q, with ZX = ω_qXZ and ω_q a primitive q-root of unity.
  • The Pauli group provides a basis for matrices acting on n-qubit systems, enabling operators to be expressed in Pauli components.
  • The Clifford group is generated by Hadamard and controlled-NOT gates and maps Pauli operators to Pauli operators up to a phase.
  • Random Clifford elements can be sampled efficiently from succinct classical descriptions of polynomial length.
  • The signed polynomial code C_k uses m = 2d + 1 and detects d errors; it is also self-dual.

3 Quantum Authentication

This section defines quantum authentication schemes and presents Clifford- and polynomial-code-based constructions. Both achieve security 2^-d, while the polynomial scheme supports shared sign keys across registers but has worse encoding parameters.

  • A quantum authentication scheme consists of polynomial-time quantum encoding and decoding algorithms with a classical key set.
  • The encoder maps an m-qubit message and key to a transmitted system of m + d qubits, while the decoder returns the message and a validity flag.
  • The Clifford QAS applies a keyed Clifford operation to n = m + d qubits and decodes by applying its inverse and checking auxiliary registers.
  • Security 2^-d: the Clifford scheme detects adversarial attacks with exponentially small error.
  • Security 2^-d: concatenating Clifford authentication preserves individual-register security regardless of the number of authenticated blocks.
  • The polynomial protocol combines a signed degree-d polynomial code with random sign and Pauli keys, then decodes by undoing the Pauli and checking for errors.
  • Security 2^-d: the polynomial authentication scheme is secure against general attacks.
  • The polynomial scheme encodes dimension q into q^(2d+1), compared with q · 2^d for the Clifford QAS, so its parameters are worse despite exponential security.

4 Interactive Proof For Quantumness

The paper presents two QPIP protocols for Q-CIRCUIT using Clifford and polynomial authentication, each achieving completeness 1 −δ and soundness δ + ǫ. The verifier authenticates data, interacts with the prover gate by gate, and accepts only authenticated outputs.

  • Clifford Authentication Based Protocol: Protocol 4.1 authenticates input qubits with concatenated Clifford QAS and processes each circuit gate through verifier decoding and re-authentication.The verifier requests the authenticated qubits for each gate, decodes them, aborts on detected errors, applies the gate, and sends newly authenticated qubits back.
  • Clifford Authentication Based Protocol: Protocol 4.1 has completeness 1 −δ and soundness δ + ǫ for Q-CIRCUIT.The soundness bound combines the QAS security parameter ǫ with the circuit error probability δ.
  • Clifford Authentication Based Protocol: The Clifford soundness proof decomposes prover attacks into Pauli components, each either being detected or causing the verifier to abort.The final state separates valid, corrupted-valid, and abort components; the QAS and circuit-error terms bound acceptance of incorrect outputs.
  • Polynomial Authentication Based Protocol: Protocol 4.2 uses concatenated polynomial QAS, three registers of m = 2d + 1 qudits, and authenticated Toffoli states for a universal gate set.The verifier authenticates inputs and required Toffoli states sequentially, then performs the circuit interactively with the prover.
  • Polynomial Authentication Based Protocol: The polynomial protocol’s verifier register can be reduced from 3m qudits to m + 2; with ǫ = 1/2, five qutrits suffice.The reduction uses the same sequential decoding and re-encoding idea as the Clifford protocol.

A Polynomial Quantum Error Correction Codes

This section develops polynomial quantum error-correcting codes and their logical operations, emphasizing the self-dual case m = 2d + 1 and its error-detection capability.

  • Code Construction: A polynomial code encodes a field element using evaluations of a polynomial at m distinct nonzero points of Fq.The encoding relies on the fact that a polynomial of degree at most m − 1 is determined by its values at those points.
  • Logical Operations: Logical Pauli operators and controlled-SUM can be implemented transversally on encoded registers.The logical Z operator is the tensor product of physical Z operators, while controlled-SUM is applied between corresponding register positions.
  • Logical Operations: The logical Fourier transform requires an explicit identity relating encoded states to sums over low-degree polynomials.The derivation groups interpolation polynomials according to their value at zero and uses degree constraints to eliminate omitted terms.
  • Logical Operations: The Fourier-transform derivation uses the condition that the code subspace has norm one to show that omitted coefficients vanish.This establishes the claimed encoded-state identity used for the logical Fourier operator.
  • Logical Operations: The proof of the logical Pauli-Z claim is omitted because it is extremely similar to the proof of the Fourier-transform claim.The section states the claim but does not reproduce its proof.

B.1 Security Proof of Clifford QAS

The Clifford QAS security proof reduces arbitrary attacks to Pauli mixtures and bounds the probability that authentication accepts a corrupted state. Independent authentication of registers preserves the same security parameter.

  • Single-Register Security: An arbitrary attack can be decomposed into Pauli operators acting jointly on the message and an adversarial system.This Pauli-basis decomposition is the starting point for analyzing the decoded state.
  • Single-Register Security: After decoding, the prover’s intervention is represented by a mixing operator Ms on the unencoded message space.The resulting state is analyzed by projecting onto the valid subspace and distinguishing identity from non-identity Pauli components.
  • Single-Register Security: Non-identity attacks that leave auxiliary qubits unchanged are limited to 4^m2^d − 1 undetected Pauli operators.These operators act as arbitrary Paulis on the message and only I or Z on each auxiliary qubit.
  • Single-Register Security: The Clifford QAS security bound is 1 − 1/2^d for the projection onto the valid state space.The proof also notes that interventions closer to the identity are more likely to remain in the valid subspace.
  • Single-Register Security: Random Clifford conjugation maps every non-identity Pauli uniformly over all non-identity Paulis.This symmetry is used to show that nontrivial attacks are unlikely to preserve the authenticated subspace.
  • Concatenated Security: For concatenated authentication, independent random Clifford operations reduce attacks across multiple registers to separate attacks on each register.The probability of fooling the verifier remains at most 2^−d regardless of the number of authenticated blocks.

C.1 Security Proof of Polynomial QAS

The polynomial QAS security proof analyzes generalized Pauli attacks and shows that authentication detects nontrivial corruption with probability at least 1 − 2^−d. Concatenation uses shared sign keys and independent Pauli keys across registers.

  • Single-Register Security: For generalized Pauli attacks, the polynomial QAS projects onto the correct encoded state with probability at least 1 − 2^−d.The proof first analyzes X-type attacks and then uses self-duality to handle Z-type attacks.
  • Single-Register Security: An X-type attack of weight at most d is detected with certainty by the polynomial error-detection procedure.A nonzero interpolating polynomial would require degree at least d + 1 under the stated parameter choice.
  • Single-Register Security: For higher-weight X-type attacks, the probability of avoiding detection is at most 2^−d over the random sign key.The attack must agree with a degree-at-most-d signed polynomial on all remaining coordinates.
  • Single-Register Security: Random Pauli keys shift any attack to another Pauli operator, allowing the detection bound to apply to arbitrary Pauli corruption.The proof decomposes generalized attacks and uses commutation and orthogonality lemmas to isolate matching Pauli terms.
  • Concatenated Security: For multiple registers, the probability that a non-identity attack fools Bob is at most 2^−d.The argument requires every corrupted register to evade detection, while uncorrupted registers are accepted with certainty.
  • Concatenated Security: The concatenated polynomial QAS uses one shared sign key and independent Pauli keys for each authenticated register.Each register is encoded and shifted separately, and Bob accepts the concatenated message only if every register authenticates.

D.1 Secure Application of Quantum Gates

The protocol lets the verifier implement logical operations on authenticated states largely by updating secret Pauli keys, while the prover performs selected transversal operations and measurements.

  • Secure Application of Quantum Gates: The verifier can apply generalized Pauli operations by changing Pauli keys without asking the prover to act.Other operations, including SUM, Fourier, and measurement, are handled through corresponding prover actions and verifier key updates.
  • Secure Application of Quantum Gates: For Pauli X and Z, key updates reinterpret the authenticated state as if the corresponding logical operation had been applied.The updates are (x, z) → (x − k, z) for X and (x, z) → (x, z − t) for Z.
  • Secure Application of Quantum Gates: For SUM, the prover applies a transverse controlled-sum, while the verifier updates keys to (xA, zA − zB) and (xB + xA, zB).The key update accounts for the Pauli masking of the authenticated registers.
  • Secure Application of Quantum Gates: For Fourier, the prover applies the operation transversely, which swaps the roles of X and Z Pauli operators.The relations FXxF† = Zx and FZzF† = X−z describe this swap.
  • Secure Application of Quantum Gates: Standard-basis measurement lets the verifier interpolate the encoded polynomial and abort if the received values are inconsistent with a low-degree polynomial.The prover sends measurement results, and the verifier uses the x key and sign key k to interpret them.
  • Secure Application of Quantum Gates: A Toffoli gate is implemented through Clifford operations on a Toffoli state, with key changes determined by the operations actually performed.The authenticated Toffoli state is denoted using the encoded form of |a,b,ab⟩.

D.2 Proof of Lemma 4.2

The lemma establishes that the verifier’s sign and Pauli keys remain uniformly and independently distributed throughout the protocol.

  • Proof of Lemma 4.2: At every protocol stage, the verifier’s sign key k and all Pauli-key pairs {(x,z)i} remain uniformly and independently distributed.The proof checks that each possible key update preserves this distribution.
  • Proof of Lemma 4.2: Updates induced by Pauli operations and Fourier transforms are shifts, swaps, or negations, which preserve uniform independent distributions.The sign key k remains unchanged during the protocol.
  • Proof of Lemma 4.2: SUM preserves independence because modular sums and differences of independently uniform key components remain uniformly distributed and independent in the relevant pairs.The transformed components are xB + xA and zA − zB modulo q.
  • Proof of Lemma 4.2: A prover’s standard-basis measurement outcome is uniformly random and does not depend on the authenticated information or secret keys.Thus the measurement reveals no information about k or the Pauli keys of other registers.

E Fault Tolerant QPIP

The fault-tolerant QPIP combines authenticated qudits, concatenated error correction, purification, and the polynomial QPIP to tolerate local noise.

  • E Fault Tolerant QPIP: The fault-tolerant construction extends the QPIP to quantum communication and computation devices subject to the usual local noise model.Its proof uses standard fault-tolerant quantum computation techniques while accounting for sequential verifier authentication.
  • E Fault Tolerant QPIP: The prover receives authenticated qudits one by one and encodes each authenticated component with a polylogarithmic-length concatenated error-correction code.Below a noise threshold η, the encoded qudit has effective error probability at most η′, independent of n.
  • E Fault Tolerant QPIP: Encoded qudits can undergo repeated error correction, keeping their effective error below a constant for polynomially long computations.Polynomially many authenticated qudits are sent to the prover in this way.
  • E Fault Tolerant QPIP: A purification stage protects authenticated messages and reduces the total error to at most ∆/poly(nT), where T is the circuit size.The union bound then limits the probability that any purified state is effectively incorrect.
  • E Fault Tolerant QPIP: After purification, Protocol 4.2 performs the logical computation and measurement, with the verifier interpreting the output using the secret key.The prover applies logical SUM, Fourier, and measurement operations to authenticated registers.
  • E Fault Tolerant QPIP: The fault-tolerant protocol retains the standard QPIP soundness, while noisy computation reduces completeness by an additional 2∆.If standard completeness is 1 − δ − ϵ, the fault-tolerant completeness is bounded by 1 − δ − ϵ − 2∆.

F Blind QPIP

The paper defines blind computation so the prover learns no information about the client’s function or input, and proves a blind QPIP for Q-CIRCUIT.

  • F Blind QPIP: Blindness requires that the prover gets no information beyond an upper bound on circuit size, with identical reduced states for every function in the family.Security retains the completeness and soundness properties of the underlying quantum authentication scheme.
  • F Blind QPIP: Theorem 1.4 states that a blind QPIP exists for Q-CIRCUIT.The construction uses the paper’s Clifford-based and polynomial QPIP protocols.
  • F Blind QPIP: A universal circuit allows the verifier to compute the desired result with the prover regardless of the input, using input and control bits.The universal circuit acts on the classical description c(U) of the target circuit.
  • F Blind QPIP: Randomized authentication makes the prover’s state completely mixed and independent of the circuit input, hiding the initial, intermediate, and final states.The same blindness argument applies to both authentication schemes, with random Clifford operations including random Pauli randomization.

G Interpretation of Results

The Clifford-based QPIP analysis bounds the verifier’s accepted state’s deviation from the correct final state using protocol soundness and non-abort probability. The polynomial-based QPIP satisfies the same property by an analogous proof.

  • After cheat detection, the protocol state separates into correct, rejected, and bad components with corresponding coefficients.The verifier’s procedure checks that control registers are in the |0⟩ state.
  • The analysis considers the state when the verifier declares the computation valid and bounds its trace distance from the correct state.
  • The bad-component weight is at most the QPIP soundness δ, while the non-aborting probability satisfies γ = αbad + s.
  • The polynomial-based QPIP has the same property by following the exact same proof structure.

H Symmetric Definition of QPIP

The symmetric QPIP definition gives the verifier YES, NO, and ABORT outcomes, addressing the asymmetry of convincing the verifier only on YES instances. The symmetric and one-sided formulations are equivalent when a language and its complement have QPIPs, and BQP closure under complement yields the result for BQP languages.

  • The asymmetric formulation focuses on convincing the verifier solely for YES instances, an asymmetry the paper identifies as unnatural in complexity and cryptographic settings.
  • Because BQP is closed under complement, the symmetric definition is equivalent for BQP languages.
  • QPIPsym retains the original prover, verifier, and communication resources while adding symmetric YES, NO, and ABORT outcomes.
  • In QPIPsym, YES means the verifier is convinced that x ∈L, while NO means the verifier is convinced that x /∈L.
  • The symmetric formulation preserves the possibility of verifier abortion as an explicit outcome for detected cheating.
  • If both L and its complement have QPIPs, a first prover message selects the corresponding protocol, yielding a QPIPsym through completeness and soundness.
Loading 0810.5375v2…