Classical Verification of Quantum Computations

1 Introduction

• A classical polynomial-time verifier can interact with an efficient quantum prover to verify BQP computations under the assumption that quantum machines cannot efficiently solve Learning with Errors.Without cryptographic assumptions, whether such verification is possible remains open.Source: §1 · p. 1

1.1 Classical Commitment to Quantum States

• The measurement protocol uses a classical string to commit the prover to a quantum state and enforce non-adaptive standard- or Hadamard-basis measurement results.The reported distributions must correspond to an underlying quantum state, preventing the prover from changing states after learning the requested bases.Source: §1.1 · pp. 1–2

1.2 Linking Commitment to Verification

• The verifier reduces a BQP instance to a local Hamiltonian and estimates the requested state’s energy using only standard/Hadamard-basis measurements.Low energy certifies membership, while high energy for every state rejects the instance; this capability is exactly what the measurement protocol supplies.Source: §1.2 · pp. 2–3

1.3 Measurement Protocol Construction

• The protocol’s weaker commitment permits only deviations commuting with standard-basis measurement, which can be absorbed into a different committed state without changing either measurement distribution.Its construction uses an extended trapdoor claw-free family that randomizes harmful deviations and limits the prover’s post-commitment control.Source: §1.3 · pp. 3–4
• Assuming an extended trapdoor claw-free family, all BQP decision problems can be verified by an efficient classical machine through interaction, yielding BQP = QPIP0.The paper constructs this family from Learning with Errors with superpolynomial noise ratio, assuming quantum computational intractability.Source: §1.3 · p. 4

1.4 Related Work

• Unlike prior uses of trapdoor claw-free functions for randomness generation or information hiding, [Mah18], this work constrains an untrusted prover while carrying out a computation.The paper introduces a new protocol and proof techniques to obtain this stronger control.Source: §1.4 · p. 4

2 Overview

• The overview uses two cryptographic primitives to build a measurement protocol whose soundness forces provers to create and measure states in verifier-chosen bases, then extends it to all of BQP.The overview uses idealized primitives for clarity; the main body replaces them with approximate versions, preserving the protocol and analysis up to technical details.Source: §2 · p. 4

2.1.1 Trapdoor Claw-Free Families

• A trapdoor claw-free family consists of two injective functions with equal images, making claws hard to find while allowing a trapdoor holder to recover both preimages.Its two hardcore-bit properties further make certain information about the preimages computationally difficult to obtain.Source: §2.1.1 · p. 5
• State commitment with a claw-free family hides both preimages from the prover but lets the verifier recover them using the trapdoor, giving the verifier leverage over the committed qubit.The construction applies the two functions in superposition, measures an output commitment string y, and leaves a committed qubit entangled with its two preimages.Source: §2.1.1 · p. 5
• The committed state supports a logical Hadamard measurement: the prover reports measurement bits, and the verifier uses the trapdoor-derived decoding bit to recover the Hadamard result.The decoding operator is an X Pauli determined by d · (x0,y ⊕ x1,y), implemented after measurement as a classical XOR.Source: §2.1.1 · pp. 5–6

2.1.2 Trapdoor Injective Function Families

• A trapdoor injective family has injective functions with disjoint images, and its keys are computationally indistinguishable from claw-free-family keys.The overview assumes this family exists, while the paper defines an approximate version and constructs it from Learning with Errors in Section 8.2.Source: §2.1.2 · p. 6
• With an injective family, measuring the output y collapses the superposition onto one branch with probability |α_b|2, leaving a unique preimage.The trapdoor recovers the branch label b and preimage from y.Source: §2.1.2 · p. 6
• In the interactive setting, the verifier obtains the prover’s standard-basis measurement result simply by requesting the commitment string y and applying the injective-family trapdoor.The trapdoor extracts both b and the unique preimage from y.Source: §2.1.2 · p. 6

• The verifier encodes per-qubit basis choices as h ∈ {0, 1}^n, with 0 denoting standard basis and 1 denoting Hadamard basis.Source: §2.2 · p. 6
• During commitment, the verifier supplies function keys matched to each requested basis, and the prover commits an arbitrary n-qubit state and returns values y_i.Source: §2.2 · p. 7
• After receiving the commitments, the verifier randomly selects a test round or a Hadamard round; in a test round, it requests standard-basis measurements and checks that the returned values are preimages of y_i.Source: §2.2 · p. 7
• In a Hadamard round, the verifier rejects invalid responses, inverts g_{k_i} for standard-basis positions, and records the first inverted bit as the measurement result.Source: §2.2 · p. 7
• For Hadamard-basis positions, the verifier decodes b′_i by XORing it with d_i · (x_{0,y_i} ⊕ x_{1,y_i}) and stores the result as m_i; completeness follows from the commitment construction.Source: §2.2 · p. 7

2.3 Measurement Protocol Soundness

• For n = 1, a prover accepted perfectly in the test round induces a state ρ whose measurement distributions computationally match the verifier’s for every basis; arbitrary n follows from independent function keys.Provers accepted with non-negligible probability can be conditioned on acceptance to obtain a perfectly passing prover.Source: §2.3 · p. 7

2.3.1 Prover Behavior

• The test round characterizes any perfectly passing prover by a committed state and a Hadamard-round unitary U, with the committed registers in a superposition over the two preimages of the reported y.The verifier can model test-round behavior as standard-basis measurement and Hadamard-round behavior as applying U before measurement.Source: §2.3 · p. 8

2.3.2 Construction of Underlying Quantum State

• If U is X-trivial, defining ρ using the committed qubit and the verifier’s Z decoding operator makes DP,h computationally indistinguishable from Dρ,h for both h = 0 and h = 1.The proof’s crux is replacing U with an X-trivial U′ using hardcore-bit properties, preserving the measurement distributions up to computational indistinguishability.Source: §2.3 · p. 8, §2.3.2 · p. 10

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

• For n = 1 and perfect test-round success, a prover P′ with an X-trivial Hadamard-round attack is computationally indistinguishable from P, implying soundness via a state ρ.The argument combines the replacement with Section 2.3.2 and the triangle inequality.Source: §2.4 · p. 10
• The general attack U is replaced by an X-trivial CPTP map using the Z Pauli twirl, with computational randomness from verifier decoding and the prover’s state hiding the conjugated phase flips.The required indistinguishability reduces to showing d · (x0,y ⊕ x1,y) is computationally indistinguishable from a uniform bit, formalized through two hardcore-bit conditions.Source: §2.4 · p. 11

2.4.1 Computational Indistinguishability of Phase Flip

• Computational indistinguishability of the original and phase-conjugated distributions follows by splitting their mixed states into diagonal and cross terms and proving both pairs indistinguishable.The cross-term reduction constructs an efficient CPTP map, while the diagonal and cross terms are each tied to a hardcore-bit violation.Source: §2.4.1 · p. 12, §2.4.1.2 · p. 13

2.4.1.1 Diagonal Terms

• A distinguisher for the diagonal terms would recover d · (x0 ⊕ x1), violating the adaptive hardcore-bit property of the trapdoor claw-free family.The reduction uses the verifier’s decoding bit to identify which phase-flipped state was created, then extracts the claw parity from the distinguisher’s output.Source: §2.4.1.1 · pp. 12–13

2.4.1.2 Cross Terms

• A distinguisher for the cross terms would determine d · (x0,y ⊕ x1,y), violating the claw-free family’s hardcore-bit condition that the claw parity bit cannot be computed by a BQP attacker.Applying Z^d to the preimage register is equivalent to applying Z^(d·(x0,y⊕x1,y)) to the committed qubit, enabling the reduction.Source: §2.4.1.2 · pp. 13–14

2.5 Extension of Measurement Protocol to a Verification Protocol for BQP

• A BQP instance reduces to a local Hamiltonian whose ground-state energy is at most a for yes-instances and at least b for no-instances, with inverse-polynomial gap b −a.Estimating the received state’s energy is sound because no state has energy below b on no-instances.Source: §2.5 · p. 14
• Because H is a sum of products of X and Z operators [BL08], energy estimation requires only Hadamard- or standard-basis measurements on individual qubits.The resulting protocol repeats energy estimation polynomially many times, achieving a completeness/soundness gap negligibly close to 1 [MF16].Source: §2.5 · p. 14
• Replacing [MF16]’s single-qubit measurement step with our measurement protocol yields a verification protocol for BQP with completeness and soundness.The extension is described in Section 7.Source: §2.5 · pp. 14–15
• Soundness is preserved because the verifier’s measurement outcomes are guaranteed to come from measuring an underlying quantum state.The protocol therefore supplies the standard and Hadamard basis measurements required by the verification procedure.Source: §2.5 · pp. 14–15

Trapdoor families

• The paper uses approximate rather than ideal trapdoor function families, defining them in Section 4 to preserve the protocol’s required properties at the cost of additional notation.These properties are needed throughout the protocol developed in the remainder of the paper.Source: §2.6 · p. 15

Measurement protocol

• Sections 5 and 6 present the measurement protocol, prove completeness, characterize prover behavior, reduce attacks to ones commuting with standard-basis measurement, and prove soundness.Section 6.4 combines the results of Sections 6.1–6.3 to complete the soundness proof.Source: §2.6 · p. 15

QPIP0 extension

• Section 7 extends the measurement protocol to a QPIP0, yielding the main result BQP = QPIP0 assuming an extended trapdoor claw-free family.This result is stated informally as Theorem 1.1 and formally as Theorem 7.6.Source: §2.6 · p. 15

LWE construction

• Section 8 constructs an extended trapdoor claw-free family from Learning with Errors, assuming LWE with superpolynomial noise ratio is computationally intractable for efficient quantum machines.This establishes the existence claim stated informally as Theorem 1.2 and formally as Theorem 8.1.Source: §2.6 · p. 15

3.1 Notation

• Notation fixes modular representations, norms, distributions, statistical distances, and computational indistinguishability for quantum polynomial-time attackers.Computational indistinguishability requires every quantum polynomial-time attacker’s distinguishing advantage to be negligible.Source: §3.1 · pp. 15–16

3.3.1 Quantum Operations

• Quantum operations are expressed using Pauli and Clifford operators, universal Hadamard-Toffoli circuits, and completely positive trace-preserving maps.Pauli operators form a matrix basis, Clifford operations preserve them up to phase, and CPTP maps represent general quantum operations.Source: §3.3.1 · p. 17

3.3.2 Trace Distance

• Trace distance is contractive under CPTP maps, and computational indistinguishability extends from classical distributions to quantum-state families tested by efficiently implementable CPTP maps.The section also relates Hellinger distance to trace distance for superpositions.Source: §3.3.2 · p. 18

3.3.3 Pauli Twirl

• A Z Pauli twirl randomizes a CPTP map into an equivalent form, and before Hadamard-basis measurement its effect is captured by an equivalent measured map.The corollary uses that a Z operation before standard-basis measurement has no effect.Source: §3.3.3 · pp. 18–19

3.4 QPIP Definition

• A QPIP consists of a BQP prover and a hybrid BPP-plus-quantum verifier interacting through quantum and classical channels, with completeness c and soundness s separated by a constant.The verifier holds at most τ qubits, while the prover has access to a τ-qubit channel and classical communication is polynomially bounded.Source: §3.4 · p. 20

4 Function Definitions

• The function definitions capture constructions that approximately, rather than ideally, realize the function properties used in the protocol.Their technical conditions arise from this approximate nature and are motivated by Learning with Errors constructions.Source: §4 · p. 20

4.1 Noisy Trapdoor Claw-Free Functions

• An NTCF family provides efficient key and trapdoor generation, trapdoor inversion, a matching between the two function branches, range-superposition procedures, and an adaptive hardcore-bit condition.The trapdoor separates supports for distinct inputs and enables inversion, while the injective pair uses a perfect matching R_k between branches.Source: §4.1 · p. 21
• The adaptive hardcore-bit condition uses efficiently recognizable good sets and an efficiently invertible injection J to constrain quantum polynomial-time procedures.The good sets exclude only negligible probability mass, and the condition is formulated over matched inputs and their encoded parity relation.Source: §4.1 · p. 21

4.2 Extended Trapdoor Claw-Free Functions

• An extended trapdoor claw-free family adds injective invariance and a further security property to an NTCF family.The underlying trapdoor-injective family has disjoint branch images, efficient inversion, range checking, and state preparation; injective invariance requires computational indistinguishability for quantum polynomial-time procedures.Source: §4.2 · p. 22

5.1 How to Commit

• Using an NTCF function, commitment measures a function-output register to obtain y while leaving a committed qubit paired with a uniquely recoverable preimage for each branch.Trapdoor and injective-pair conditions guarantee the paired preimages x_0,y and x_1,y, defining the committed qubit and preimage register.Source: §5.1 · p. 23

5.1.1 Hadamard Measurement of a Committed State

• Hadamard measurement applies the efficiently invertible map J, Hadamard-transforms the first registers, measures the preimage register, and corrects the committed-qubit bit using the two recovered J values.The resulting measurement of the original first qubit is b′ ⊕ d · (J(x_0,y) ⊕ J(x_1,y)).Source: §5.1.1 · p. 24

5.1.2 How to Commit Using a Trapdoor Injective Family

• With a trapdoor injective family, measuring y directly implements a standard-basis measurement, and the basis bit is recovered by applying the trapdoor inversion procedure.Disjoint output supports ensure that y identifies the branch with probability |α_b|^2.Source: §5.1.2 · p. 24

5.2 Measurement Protocol

• The protocol lets a verifier choose standard or Hadamard measurement independently for each qubit, receive commitment strings, and verify test-round reports or compute measurement results in Hadamard rounds.For standard-basis positions, the verifier uses trapdoor inversion; for Hadamard-basis positions, it checks preimage conditions and applies the correction b′_i ⊕ d_i · (J(x_0,y_i) ⊕ J(x_1,y_i)).Source: §5.2 · pp. 24–25

5.2.1 Honest Prover

• The honest prover creates ρ, commits each qubit using the verifier’s function choices, and measures committed qubits and preimage registers in the requested basis during the selected round.In Hadamard rounds, it first applies U_J to all preimage registers before measuring.Source: §5.2.1 · pp. 25–26

5.3 Notation

• The notation defines basis choices, verifier function-choice distributions, perfect provers, ideal measurement distributions, conditioned distributions, and the corresponding density matrices.It also identifies computational indistinguishability of the distributions with that of their associated density matrices.Source: §5.3 · p. 26

5.4 Completeness of Measurement Protocol

• An honest prover is perfect in test rounds and is accepted with probability at least 1−µ in Hadamard rounds for every n-qubit state and basis choice.The proof bounds rejection by negligible terms from the adaptive hardcore-bit condition and negligible trace-distance approximations.Source: §5.4 · p. 27
• Completeness follows because honest commitments pass the test checks perfectly, while Hadamard-round rejection occurs only with negligible probability and commitment states differ from ideal states by negligible trace distance.The final negligible bound is µ = µ_H + µ′.Source: §5.4 · p. 27

6 Measurement Protocol Soundness

• The soundness proof characterizes general provers, shows that trivial provers produce results consistent with an underlying quantum state, reduces general attacks to attacks commuting with standard-basis measurement, and combines these results.Sections 6.1–6.4 respectively develop the prover characterization, consistency result, attack reduction, and final soundness proof.Source: §6 · p. 27

Claim 6.1 Prover Behavior

• The characterized prover uses first n qubits as committed qubits, next n registers as preimage registers, final n registers as commitment strings, and remaining registers as auxiliary space.Upon receiving k′, it applies U0, then measures commitment-string registers to obtain and send y′ to the verifier.Source: §6.1 · p. 28
• In a Hadamard round, the prover appends eJ·n zero qubits, applies UJ to all preimage registers and U to its state, then measures committed and preimage registers in the Hadamard basis.In a test round, it instead measures those registers in the standard basis and sends the resulting bit string to the verifier.Source: §6.1 · p. 28

Notation 6.2

• The same characterization can be stated using CPTP maps S0 and S instead of U0 and U, while preserving test-round acceptance and DP,h for every basis choice.The corresponding prover follows the same five-step procedure with the maps substituted for the unitaries.Source: §6.1 · p. 28

Proof of Claim 6.1

• The proof derives the characterization by rewriting a general prover as an arbitrary initial unitary attack followed by honest measurements, then shifting and conjugating round-specific operations into U0 and U.This preserves both test-round acceptance and the distributions DP,h, while accounting for the UJ operation and the measured commitment string y′.Source: §6.1 · pp. 28–29

Construction of Underlying Quantum State

• Every trivial prover has an underlying n-qubit state ρ, constructible by a BQP circuit, whose basis-dependent measurement distributions are computationally indistinguishable from the prover’s protocol outputs.Triviality means the prover’s CPTP map S commutes with standard-basis measurement on the first n qubits.Source: §6.2 · p. 29
• The state ρ is built by sampling function keys and trapdoors, following the prover-dependent construction, measuring preimage registers in the Hadamard basis, applying trapdoor-controlled Z corrections, and retaining only the n committed qubits.The construction obtains d_1,...,d_n from preimage-register measurements and applies Z corrections before tracing out the remaining qubits.Source: §6.2 · p. 29
• For basis choices with h_i=0, removing the corresponding Z correction does not change the distribution because that qubit is immediately measured in the standard basis.This establishes equality between the relevant hybrid distribution and D_ρ,h for every basis choice h.Source: §6.2 · pp. 29–30
• The remaining hybrid transitions rely on injective invariance: without the discarded trapdoor, keys sampled from K_F are computationally indistinguishable from keys sampled from K_G.The argument applies independently to indices with h_i=0, where the trapdoors are discarded.Source: §6.2 · p. 30
• The final distributions agree because perfect-prover behavior makes standard-basis measurement outcomes match the commitment strings, while triviality lets S commute with that measurement.Thus the hybrid distribution equals the protocol distribution D_P,h for every h.Source: §6.2 · p. 30

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

• For any committed qubit j with h_j = 1, the general attack S can be replaced by an attack S_j acting trivially on qubit j, while DP,h and DPj,h remain computationally indistinguishable.The argument constructs the corresponding states σP,h and σPj,h and proves their indistinguishability, which transfers to the measurement-result distributions.Source: §6.3 · p. 31

6.3.1 Indistinguishability of Diagonal Terms (Proof of Claim 6.10)

• Diagonal-term distinguishability would yield a BQP attacker violating the hardcore-bit clause of Definition 4.1, so the diagonal components are computationally indistinguishable.The reduction uses a distinguisher for σD0 and σD1 to construct an attacker with non-negligible hardcore-bit advantage.Source: §6.3 · p. 35, §6.3.1 · pp. 35, 37

6.3.2 Indistinguishability of Cross Terms (Proof of Claim 6.11)

• Cross-term distinguishability would likewise yield a BQP attacker violating the hardcore-bit clause of Definition 4.4 by guessing d · (J(x0,y) ⊕ J(x1,y)) with non-negligible advantage.The reduction applies the distinguisher to states derived by applying Zd to the preimage register and a random Z correction to the committed qubit.Source: §6.3 · p. 35, §6.3.2 · pp. 37–38
• The expression in (133) is non-negligible because the assumed CPTP map O distinguishes ˆσ0 from ˆσ1.Source: §6.3.2 · p. 39

6.3.3 Reduction to Diagonal/Cross Terms (Proof of Claim 6.9)

• If the quantity in (139) is non-negligible, the CPTP map OS′ computationally distinguishes ˆσ0 from ˆσ1.The reduction uses an equality and the triangle inequality to show that a non-negligible quantity must arise from one of two diagonal or cross-term quantities.Source: §6.3.3 · p. 39

6.4 Proof of Measurement Protocol Soundness

• Lemma 6.12 establishes that every prover is related to a state ρ and prover P′ whose distributions are computationally indistinguishable from measuring ρ, with error bounded by p_h,T + µ.Here µ is negligible, and the construction combines the general-to-perfect and perfect-to-trivial transitions.Source: §6.4 · pp. 40–41

6.4.1 General to Perfect Prover (Proof of Claim 6.13)

• Claim 6.13 constructs an efficient perfect prover by conditioning on test-round acceptance, using the function-key-only procedures CHKF or CHKG.The construction uses bounded repetitions of a test-checking procedure and falls back to an honest prover operation if acceptance is not observed.Source: §6.4 · p. 40, §6.4.1 · pp. 41–42

6.4.2 Perfect to Trivial Prover (Proof of Claim 6.14)

• Claim 6.14 transforms every perfect prover into a trivial prover by sequentially replacing attacks on Hadamard- and standard-basis qubits while preserving or computationally approximating measurement distributions.For standard-basis positions, the attack can be changed without affecting the verifier’s distribution because the committed-qubit measurement is obtained directly from the commitment.Source: §6.4 · p. 41, §6.4.2 · pp. 43–44

7.1 Morimae-Fitzsimons Protocol

• Protocol 7.1 [MF16] verifies BQP instances by randomly choosing S with probability πS, receiving a state one qubit at a time, measuring two qubits in X or Z, and accepting when the product is −sign(dS).Theorem 7.2 [MF16] states completeness c and soundness s with c − s inverse polynomial in |x|.Source: §7.1 · pp. 44–45
• Protocol 7.3 [MF16] verifies x ∈ L for L ∈ BQP by independently choosing polynomially many Si, receiving a state one qubit at a time, and measuring each with two-qubit X- or Z-basis tests.Theorem 7.4 [MF16] states that Protocol 7.1 has completeness 1 −µ and soundness µ, where µ is negligible in the size of the instance.Source: §7.1 · p. 45

7.2 Extending the Measurement Protocol

• The extension replaces Protocol 7.3’s qubit-sending and measurement steps with Protocol 5.1, using its basis choice and Hadamard-round results for verification.The verifier derives a basis choice h, runs Protocol 5.1, and applies Protocol 7.3’s acceptance test in Hadamard rounds.Source: §7.2 · p. 46
• Theorem 7.6 states that Protocol 7.5 is a QPIP0 for all languages in BQP, with completeness negligibly close to 1 and soundness negligibly close to 3.Source: §7.2 · pp. 46–48

8.1 Parameters

• Theorem 22 [BCM+21] states that, for any parameters satisfying conditions (186), FLWE is a noisy trapdoor claw-free family under the hardness assumption LWEℓ,q,D.Source: §8.1 · p. 49

8.2 Trapdoor Injective Family from LWE

• Theorem 8.2 establishes GLWE as a trapdoor injective family under the same parameter conditions and LWE assumption.The proof verifies the three properties required by the definition of a trapdoor injective family.Source: §8.2 · p. 49

8.2.1 Efficient Function Generation

• GENGLWE samples a nearly uniform matrix with trapdoor information, enabling inversion of As + e when the error satisfies the required norm bound.The generated matrix distribution is negligibly close to uniform, and the trapdoor supports the INVERT procedure.Source: §8.2.1 · p. 50

8.2.2 Trapdoor Injective Functions

• Using the trapdoor, INVGLWE recovers the unique correct branch for outputs in the function support, while the support intersection is empty under condition (191).The inversion procedure tests whether y or y − u has a valid short-error representation.Source: §8.2.2 · p. 50

8.3 Injective Invariance

• Injective invariance follows because GENFLWE and GENGLWE are computationally indistinguishable under LWE hardness with a binary secret, as established in Lemma 8.3.The binary-secret LWE implication is connected to prior results, [BLP+13], and Theorem B.5 of.Source: §8.3 · pp. 50–51

8.4 Extended Trapdoor Claw-Free Family

• The hardcore-bit condition is proved by reducing any successful predictor of the relevant inner product to a distinguisher contradicting Lemma 8.5.Lemma 8.5 makes the inner product ˆd · s mod 2 computationally indistinguishable from a uniformly random bit, and Lemma 8.6 transfers this to the condition using the binary representation map J; the proof follows ideas from.Source: §8.4 · pp. 51–53