PaperlayerView exact revision on arXiv

Source-linked AI summary

Classical Verification of Quantum Computations

Urmila Mahadev

arXiv:1804.01082v3quant-ph

TL;DR

The paper addresses whether a classical polynomial-time verifier can verify computations performed by an efficient quantum prover. It constructs a measurement protocol using cryptographic assumptions, obtaining classical interactive verification for BQP.

  • Problem

    The paper asks whether an efficient classical verifier can verify the output of an efficient quantum prover through purely classical interaction.

  • Method

    The protocol uses an interactive measurement protocol and an extended trapdoor claw-free family to make the quantum prover act as a trusted measurement device.

  • Results

    BQP computations can be verified by an efficient classical machine through interaction, assuming an extended trapdoor claw-free family.

  • Takeaways & Limitations

    Classical interactive verification of BQP is achieved under the assumption that suitable post-quantum cryptography is secure against efficient quantum machines.

  • Takeaways & Limitations

    The protocol relies on post-quantum cryptographic assumptions, and the overview uses idealized primitives replaced by approximate versions in the main body.

Abstract

from arXiv · show

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which enables a classical verifier to use a quantum prover as a trusted measurement device. The protocol forces the prover to behave as follows: the prover must construct an n qubit state of his choice, measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier. The soundness of this protocol is enforced based on the assumption that the learning with errors problem is computationally intractable for efficient quantum machines.

1 Introduction

The paper addresses whether a classical verifier can verify an efficient quantum computation through interaction with a single quantum prover. It constructs a measurement protocol that makes the prover function as a trusted measurement device, yielding classical verification of BQP under cryptographic assumptions.

  • Motivation: The paper resolves the open question of whether a BPP verifier can verify the output of a BQP prover through purely classical means.Earlier approaches either gave the verifier a small quantum computer or used two entangled, non-communicating quantum provers.
  • Measurement protocol: The measurement protocol forces a quantum prover to classically commit to a quantum state and report requested standard- or Hadamard-basis measurements.The commitment string prevents the prover from adaptively changing the state after learning the verifier’s measurement choices.
  • Verification: The protocol extends to verification of all BQP computations by reducing verification to estimating the energy of a local Hamiltonian using standard/Hadamard measurements.The classical verifier requests a state and checks whether its measured energy is sufficiently low.
  • Cryptographic construction: The extended trapdoor claw-free construction uses strengthened claw-free properties to randomize deviations from requested measurements.The construction relies on the assumption that quantum machines cannot efficiently solve Learning with Errors with superpolynomial noise ratio.
  • Novelty: The paper’s new contribution is controlling an untrusted prover while it carries out a particular computation, rather than merely generating randomness or hiding information.This requires stronger control and new protocol and proof techniques.

2 Overview

The overview introduces cryptographic primitives for committing a quantum state through a classical string and extracting standard- or Hadamard-basis measurement outcomes. Idealized primitives simplify the overview, while the full construction uses approximate versions.

  • Overview: The measurement protocol uses two cryptographic primitives to give a classical verifier leverage over a quantum prover.The overview presents idealized primitives before the detailed construction and soundness analysis.
  • Caveat: The full paper replaces the overview’s idealized primitives with approximate versions, adding technical details while preserving the overview’s protocol and analysis.The approximate construction is supplied later from Learning with Errors.
  • Trapdoor claw-free functions: A trapdoor claw-free family uses two injective branches with equal images, while finding matching preimages across branches is computationally difficult.The shared image creates a claw, and the trapdoor enables inversion for the verifier.
  • State commitment: State commitment applies the two function branches in superposition, measures the function-output register, and records the resulting y as the commitment string.The committed qubit and preimage register retain the committed state’s structure.
  • Hadamard measurement: The verifier obtains a logical Hadamard measurement by measuring the preimage register and applying a trapdoor-dependent X decoding operation.After measurement, decoding is implemented as a classical XOR operation.
  • Standard measurement: A trapdoor injective family has disjoint branch images, so measuring y collapses the branch and lets the verifier recover the standard-basis bit.The trapdoor recovers both the branch bit and its unique preimage.

2.2 Measurement Protocol

The measurement protocol directs basis choices for each committed qubit and uses cryptographic checks and trapdoors to recover the requested measurement results. Honest execution is complete because the verifier’s decoding matches the commitment process.

  • Basis selection: The verifier chooses standard or Hadamard measurement independently for each qubit, represented by h ∈ {0, 1}^n.hi = 0 denotes the standard basis.
  • Commitment round: During commitment, the verifier sends function keys chosen according to the requested bases, and the honest prover constructs an n-qubit state before committing to each qubit.Hadamard positions use trapdoor claw-free functions; standard positions use trapdoor injective functions.
  • Hadamard round: In a Hadamard round, the verifier requests Hadamard measurements of the committed qubit and preimage register and rejects invalid or zero preimage responses.The prover reports b′i and non-zero di.
  • Standard round: For standard-basis positions, the verifier ignores the reported Hadamard-round values and uses the trapdoor to invert yi, storing the first inverted bit as mi.This extracts the standard-basis measurement result from the commitment.
  • Hadamard decoding: For Hadamard-basis positions, the verifier decodes b′i by XORing it with di · (x0,yi ⊕ x1,yi), then stores the result as mi.The decoding operator can equivalently be viewed as an X operation controlled by the trapdoor-derived value.

2.3 Measurement Protocol Soundness

The soundness proof shows that accepted prover behavior yields measurement distributions consistent with an underlying quantum state. Its central step replaces arbitrary Hadamard-round attacks with computationally indistinguishable X-trivial attacks.

  • Proof strategy: For a prover passing the test round perfectly, the proof first characterizes the prover’s state and the verifier’s measurement distribution DP,h.The argument begins with n = 1 and extends to n qubits because function keys are drawn independently.
  • Test-round characterization: The test round forces the prover’s committed registers into a superposition over the two preimages of the reported value y.This structure provides a well-defined committed state even for dishonest provers.
  • Underlying state: The proof defines a state ρ from the committed state, the prover’s operator U, and the verifier’s X decoding operator.Hadamard-basis measurements of ρ reproduce the verifier’s corresponding distribution, while standard-basis consistency remains to be shown.
  • X-triviality: An X-trivial operator is one that commutes with standard-basis measurement of the committed qubit.The soundness argument seeks to replace a general Hadamard-round attack with an X-trivial one.
  • Prover characterization: The prover can be represented using commitment, test, and Hadamard-round unitaries, with the test-round attack reducible to the identity.This yields a characterization by two unitary attacks, U0 and U.
  • Soundness conclusion: The replacement argument produces a prover P′ with an X-trivial Hadamard attack whose distributions are computationally indistinguishable from those of the original prover.Combined with the earlier state-construction argument and the triangle inequality, this establishes an underlying state ρ.

2.4 Replacement of a General Attack with an X-Trivial Attack

The proof replaces a general prover attack with an X-trivial attack while preserving computational indistinguishability, using Pauli twirling and hardcore-bit security.

  • Reduction: A perfectly test-round-accepted prover has an indistinguishable counterpart whose Hadamard-round attack is X-trivial.This reduction, combined with the triangle inequality, yields an efficiently computable underlying state for the measurement distribution.
  • Pauli twirling: The replacement uses a Z Pauli twirl, which is equivalent after Hadamard-basis measurement.The twirl conjugates the attack by a random Z operator and converts it into an X-trivial CPTP map.
  • Cryptographic hiding: Trapdoor claw-free randomness hides whether Z operators are applied before and after the prover’s attack.The verifier’s decoding operator supplies posterior randomness, while the claw-free structure hides the relevant phase information.
  • Hardcore-bit security: The required bit d · (x0,y ⊕x1,y) must be computationally indistinguishable from a uniformly random bit.This requirement is formalized through two hardcore-bit conditions for the function pair fk,0, fk,1.
  • Soundness argument: Distinguishability between the diagonal terms would let a BQP attacker recover the claw difference bit, violating the adaptive hardcore-bit property.The attacker obtains b, xb,y, d, and d · (x0 ⊕x1), contradicting the claw-free assumption.

2.5 Extension of Measurement Protocol to a Verification Protocol for BQP

The measurement protocol extends to BQP verification because local-Hamiltonian energy estimation requires only standard- and Hadamard-basis measurements. Its soundness ensures those results arise from an underlying quantum state.

  • Local-Hamiltonian verification: A BQP instance reduces to a local Hamiltonian whose ground-state energy is separated by an inverse-polynomial gap.Yes-instances have energy at most a, while no-instances have energy at least b.
  • Local-Hamiltonian verification: Because Hamiltonian terms are products of X and Z operators, energy estimation requires only individual standard- or Hadamard-basis measurements.The verifier therefore needs measurement access rather than a general quantum computation.
  • Protocol extension: Replacing the trusted measurement step with the paper’s protocol preserves completeness and soundness.The protocol supplies the required measurements, and its soundness guarantees that the reported distribution comes from an underlying quantum state.

2.6 Paper Outline

The paper develops an extended trapdoor claw-free family, constructs and analyzes the measurement protocol, and then derives classical interactive verification for BQP under a quantum-hard LWE assumption.

  • Preliminaries and construction: The paper defines approximate trapdoor function families and ensures they retain the properties required by the protocol.These families replace the ideal families used in the overview.
  • Measurement protocol: Sections 5 and 6 establish completeness and soundness of the measurement protocol, including the attack-replacement argument.The soundness analysis characterizes the prover and replaces a general attack with one commuting with standard-basis measurement.
  • Main result: Assuming an extended trapdoor claw-free family, BQP equals QPIP0.This is stated as the paper’s main verification theorem.
  • Cryptographic foundation: An extended trapdoor claw-free family is constructed from LWE assumed hard for efficient quantum machines with superpolynomial noise ratio.This supplies the cryptographic assumption used for the main theorem.

3 Preliminaries

The preliminaries define the distributional, cryptographic, quantum-information, and algebraic tools used to analyze computational indistinguishability and Pauli-based attack transformations.

  • Security notions: Computational indistinguishability is defined for classical distributions and quantum states against efficient quantum algorithms or CPTP maps.The definitions require distinguishing advantage to be negligible in the security parameter.
  • LWE tools: The LWE framework includes standard, trapdoor, and lossy modes used by the paper’s cryptographic construction.Trapdoors enable inversion, while under LWE the lossy sampler is computationally indistinguishable from uniform.
  • Quantum operators: The preliminaries introduce Pauli operators, their anticommutation, and their decomposition as a matrix basis.These properties support the later Pauli-twirling analysis.
  • Quantum information: CPTP maps represent general quantum operations, and trace distance is contractive under such maps.These facts support comparisons between transformed quantum states and attack-induced distributions.
  • Pauli twirling: A Z Pauli twirl conjugates an operation by random Pauli operators and yields an equivalent map after Hadamard-basis measurement.This corollary is the technical tool used to simplify prover attacks.

4 Function Definitions

The paper defines noisy trapdoor claw-free and trapdoor injective function families through efficient generation, inversion, range operations, and security properties. It then extends NTCF families with injective invariance and an additional computational condition.

  • Noisy trapdoor claw-free families: NTCF families use efficiently generated keys and trapdoors, with function pairs that are invertible using the trapdoor and linked by a perfect matching.The defining conditions include efficient function generation, trapdoor inversion, and an injective-pair relation between the two function branches.
  • Noisy trapdoor claw-free families: NTCF families additionally provide efficient range superposition, membership checking without the trapdoor, and sampling procedures that can be implemented unitarily.The sampling procedure prepares the relevant quantum state while auxiliary qubits are returned to |0⟩.
  • Noisy trapdoor claw-free families: An adaptive hardcore bit condition requires a large efficiently recognizable good set and an efficiently computable injection J into {0,1}^w.For quantum polynomial-time procedures, the associated hardcore-bit condition holds except with negligible probability.
  • Trapdoor injective families: Trapdoor injective families instead require disjoint supports across distinct branch-input pairs, enabling inversion of both the branch and input.Their efficient generation, support checking, and sampling procedures form the basis for comparison with NTCF families.
  • Extended trapdoor claw-free families: An extended trapdoor claw-free family is an NTCF family that is injective invariant and satisfies an additional negligible-distinguishability condition.The paper motivates these definitions from LWE constructions, which approximately satisfy the ideal definitions.

5 Measurement Protocol

The measurement protocol uses cryptographic commitments to make a classical string represent an n-qubit state while allowing verifier-directed standard- or Hadamard-basis measurements. Honest execution is complete up to negligible error.

  • State commitment: The prover commits to each qubit using an NTCF or trapdoor injective function, producing commitment strings that the verifier later uses to recover measurement results.The commitment process entangles the state with function preimages and measures the output register to obtain y.
  • Measurement rounds: For Hadamard-basis measurements, the prover applies UJ, measures the committed and preimage registers, and reports b′ and d.The verifier combines these values with the two recovered preimages and the injection J to compute the Hadamard result.
  • Measurement rounds: For standard-basis measurements, the verifier uses trapdoor inversion to recover the branch and stores it as the measurement result.With the injective family, disjoint supports ensure that measuring y acts as a standard-basis measurement of the committed qubit.
  • Protocol structure: The verifier generates function keys according to the requested basis, receives commitment strings, and randomly selects a test or Hadamard round.Standard-basis positions use GENG, while Hadamard-basis positions use GENF.
  • Completeness: For every n-qubit state and basis choice, the honest prover is accepted perfectly in test rounds and with probability at least 1−µ in Hadamard rounds.The error function µ is negligible.

6 Measurement Protocol Soundness

The soundness analysis characterizes general prover behavior and connects trivial prover behavior to measurement distributions consistent with an underlying quantum state.

  • Soundness framework: The soundness section first characterizes the behavior of a general prover in the measurement protocol.This characterization follows the overview’s treatment of general provers.
  • Soundness framework: It then studies the case where the characterization satisfies a requirement called triviality.The passage identifies triviality as the condition used in the subsequent soundness argument.
  • Soundness framework: Under that requirement, the prover’s measurement results are shown to be consistent with an underlying quantum state.This consistency is the stated soundness requirement for the measurement protocol.

6.1 Prover Behavior

The prover-behavior analysis reduces any BQP prover to a canonical prover characterized by efficiently computable unitary attacks, without changing test acceptance or measurement distributions.

  • Prover characterization: Every BQP prover is equivalent to a prover P′ whose test-round acceptance probabilities and measurement distributions match those of the original prover.The equivalence holds for every basis choice h.
  • Canonical prover: The canonical prover separates committed qubits, preimage registers, commitment strings, and auxiliary space.It applies U0 after receiving the verifier’s function choice and sends the measured commitment strings y′ to the verifier.
  • Canonical prover: In Hadamard rounds, P′ applies UJ to the preimage registers before applying the attack unitary U and measuring in the Hadamard basis.The construction appends auxiliary zero qubits before applying UJ.
  • Prover characterization: The reduction absorbs the honest prover’s intermediate operations into attack unitaries while preserving observable protocol behavior.The analysis shifts UT before commitment-string measurement and conjugates the attack by UJ.

6.2 Construction of Underlying Quantum State

This section constructs an efficiently computable quantum state whose standard- and Hadamard-basis measurement distributions are computationally indistinguishable from those of a trivial prover.

  • Definition and construction: A trivial prover is defined by a Hadamard-round attack that commutes with standard-basis measurement on the first n committed qubits.The prover is characterized by a unitary U0 and an efficiently computable CPTP map S.
  • Definition and construction: For every trivial prover, there exists an n-qubit state ρ, creatable by a BQP circuit, matching its measurement distributions up to computational indistinguishability.The state is constructed from the prover characterization, function keys, preimage measurements, and trapdoor-based corrections.
  • State construction: The construction samples function keys, follows the prover characterization, measures preimage registers in the Hadamard basis, and applies trapdoor-controlled Z corrections to committed qubits.These steps produce the state whose qubits are subsequently measured according to the verifier’s basis choice.
  • Hybrid argument: For basis choices with h_i = 0, removing the Z correction leaves the standard-basis distribution unchanged because the qubit is measured immediately afterward.Thus the corresponding hybrid distribution equals the original state’s measurement distribution for every h.
  • Conclusion: The proof concludes that the constructed state’s distribution is computationally indistinguishable from the prover’s distribution for every measurement-basis string h.This establishes the underlying-state condition for trivial provers.

6.3 Replacement of a General Attack with an X-Trivial Attack for Hadamard Basis

This section shows that, for Hadamard-basis coordinates, a general perfect prover’s attack can be replaced coordinate by coordinate with an X-trivial attack without changing observable distributions beyond computational indistinguishability.

  • Conclusion: The section’s replacement argument supports transitioning from a general perfect prover toward a prover whose Hadamard-round attack is trivial on selected coordinates.This is the key intermediate step used later to obtain a fully trivial prover.
  • X-trivial replacement: For a perfect prover, replacing the Hadamard-round attack on a coordinate j with an X-trivial attack preserves computational indistinguishability when h_j = 1.The replacement is expressed through modified CPTP maps and Kraus operators.
  • State decomposition: The proof focuses on one committed qubit, treating the remaining committed qubits, preimage registers, and keys as auxiliary state.The remaining operations are represented by a CPTP map independent of the focused function key and trapdoor.
  • Verifier decoding: The verifier’s decoding operator is chosen to recover the correct committed-qubit measurement outcome, including the case where the required decoding condition fails.The set R_{c,d,k} captures accepted decoding outcomes and assigns a random bit otherwise.
  • Indistinguishability proof: The indistinguishability proof uses diagonal and cross-term analyses, reducing any distinguisher to a computationally distinguishable pair of states.Non-negligible distinguishing advantages contradict the assumed indistinguishability properties through efficiently computable CPTP maps.

6.4 Proof of Measurement Protocol Soundness

This section proves measurement-protocol soundness by transforming an arbitrary prover into a perfect prover and then a trivial prover, whose results correspond to measuring an underlying quantum state.

  • Soundness strategy: Soundness is established by transitioning from a general prover to a perfect prover and then from a perfect prover to a trivial prover.The final distribution remains close or computationally indistinguishable through these transformations.
  • Soundness theorem: For every prover P, there exist a state ρ, a prover P′, and negligible μ such that P’s distribution is bounded by its test-round rejection probability plus μ from P′’s distribution.P′’s distribution is computationally indistinguishable from the distribution obtained by measuring ρ in basis h.
  • General to perfect prover: A general prover can be converted into a perfect prover by conditioning on acceptance in the test round while preserving efficiency through repeated verification checks.The resulting distance depends on the test-round rejection probability and a negligible error term.
  • Perfect to trivial prover: Every perfect prover has a trivial prover whose measurement distributions are computationally indistinguishable for all basis choices h.The proof applies the Hadamard-basis replacement repeatedly and then handles standard-basis coordinates.
  • Conclusion: Combining the transformations with the underlying-state lemma yields a quantum state whose measurements computationally reproduce the accepted prover’s reported results.This completes the measurement protocol’s soundness argument.

7 Extension of Measurement Protocol to a Verification Protocol for BQP

The paper first uses the Morimae-Fitzsimons protocol to verify BQP instances through Hamiltonian measurements, then replaces direct qubit transmission with its measurement protocol to obtain a QPIP0.

  • Morimae-Fitzsimons protocol: Protocol 7.1 verifies BQP instances by having the verifier sample Pauli terms from a Hamiltonian and test corresponding measurement outcomes.The verifier samples S with probability πS, receives a state, measures the relevant two qubits in the X or Z basis, and checks the product of outcomes.
  • Morimae-Fitzsimons protocol: Protocol 7.1 is a QPIP1 for all languages in BQP with completeness c and soundness s whose gap c − s is inverse polynomial.Polynomial repetition amplifies this gap to obtain exponentially small verification error.
  • Extension to QPIP0: The extended protocol replaces the prover’s direct transmission of qubits for measurement with Protocol 5.1.The verifier derives a basis choice, runs the measurement protocol, and uses Hadamard-round results in the Hamiltonian acceptance test.
  • Extension to QPIP0: Measurement-protocol soundness supplies a state whose basis-measurement distributions are computationally indistinguishable from the prover’s reported distributions.The guarantee relates the Hadamard-round and test-round acceptance probabilities to a state ρ and a prover P′.

8 Extended Trapdoor Claw-Free Family from LWE

This section constructs the extended trapdoor claw-free family required by the measurement protocol from LWE-based function families. It proves that FLWE has the needed extended properties, while GLWE supplies a trapdoor injective family under the same assumption.

  • Parameters: The construction uses polynomially bounded security and function parameters, with q chosen as a prime integer at least 2.The parameters λ, q, ℓ, n, m, and w are specified subject to conditions (186).
  • FLWE and GLWE: FLWE is defined from an LWE-based noisy trapdoor claw-free family and is shown computationally indistinguishable from the corresponding GLWE distributions under LWE hardness.The indistinguishability claim is established for quantum polynomial-time attackers with binary secrets.
  • Trapdoor Injective Family: Theorem 8.2 establishes that GLWE is a trapdoor injective family under the hardness assumption LWEℓ,q,D.Its generation procedure uses a trapdoor for matrix inversion, and the generated matrix distribution is negligibly close to uniform.
  • Extended Properties: The extended construction proves the hardcore-bit condition by showing that inner products ˆd · s are computationally difficult to recover from LWE samples.Lemma 8.5 replaces the relevant inner product with a uniformly random bit, while Lemma 8.6 transfers this property to the extended claw-free definition.
Loading 1804.01082v3…