Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games

1 Introduction

• Classical delegation matters because users are unlikely to own quantum hardware and need to access remote machines they cannot control.Achieving efficient delegation with information-theoretic security remains a major open problem.Source: §1 · p. 3
• Earlier classical verification required O(g^3) resources, while Zhang's linear-time result was for measurement-based computations and left the circuit-model protocol open.Conversion from circuits to measurement-based computation incurs a polynomial factor in circuit size.Source: §1 · p. 3
• The authors use Kalai et al.'s compiler [KLVY23] to turn a nonlocal game into a single-prover argument, enforcing non-communication cryptographically with QFHE and classical ciphertexts.They use this compiled-game paradigm for verifiable random remote state preparation for the first time.Source: §1 · p. 4
• The new computational rigidity result extends the Pauli braiding test [NV17] to the extended Pauli group and certifies a random tensor-product state, up to complex conjugation.The guarantee excludes a coherent superposition of the canonical and conjugate branches, unlike the cited earlier work [GV19].Source: §1 · p. 4
• Under sub-exponential LWE hardness, every BQP language has a single-prover, classical-verifier argument system with total resources ˜O(|Cx|).The self-test's remote-state-preparation guarantee is used to dequantize Broadbent's protocol.Source: §1 · p. 4
• Sub-exponential LWE hardness is needed for quasilinear resources; polynomial hardness still gives almost-linear requirements of O(|Cx|^(1+ε)) for every ε > 0.The sub-exponential assumption is used to set λ = polylog(|Cx|).Source: §1 · p. 4
• The proof reformulates the self-test using approximate group representation theory, which the authors present as the first such rigidity proof beyond the Heisenberg–Weyl group.They hope the perspective will inform constant-robustness rigidity results for larger observable classes.Source: §1 · p. 5
• For certifying n qubits in Broadbent's gateset, the self-test uses O(n) total resources instead of O(n log n) for [CGJV24].The improvement comes from avoiding communication of a qubit permutation in the ParBell subtest.Source: §1 · p. 5

The Broadbent protocol

• Broadbent’s protocol hides test and computation rounds using QOTP encryption, while encrypted magic states let the verifier track key updates through T gates.Successful test rounds constrain a cheating prover, so the verifier can infer correct circuit outcomes in computation rounds.Source: The Broadbent protocol · pp. 6–7
• Prior remote state preparation does not provide the constant overall rigidity needed for Broadbent’s protocol, while Zhang [Zha22] covers only part of its required state set.Naively applying Gheorghiu and Vidick [GV19] per qubit can raise the resource cost to O(g^4); Zhang’s protocol omits computational-basis states.Source: The Broadbent protocol · p. 7

2.1 Background

• The KLVY compiler lets the authors use nonlocal-game rigidity techniques in a cryptographic setting for a single computationally bounded prover.This connects approximate group representation methods from self-testing with computationally nonlocal strategies.Source: §2.2 · p. 7

2.2 Rigidity result

• The authors adapt [CGJV24]’s ideas into a simpler, group-theoretic self-test for observables in the extended Pauli group, with Bell-basis tests detecting inconsistent pairwise G signs and CHSH removing global sign ambiguity.Source: §2.2 · pp. 9–10
• The compiled Clifford test certifies the prover’s measurements and state, up to isometry and complex conjugation, with constant robustness.The QFHE interaction makes coherences between canonical and complex-conjugate cases cryptographically small, strengthening the state characterization relative to [GV19].Source: §2.2 · pp. 10–11

2.3 BQP verification

• The BQP verification protocol encrypts a random basis assignment and uses repeated rigidity tests to certify remote preparation, while interspersed Broadbent rounds ensure soundness.The prover receives only the encrypted basis assignment, and the verification-game probability is chosen so the rigidity guarantee also applies to Broadbent rounds.Source: §2.3 · pp. 11–12

2.4 Technical contributions

• An explicit, efficient Gowers–Hatami isometry enables tighter error bounds when analyzing products of operators.The modified dilation-based proof gives an explicit isometry and an efficient Fourier-transform circuit over the extended Pauli group; the improved bounds also rely on this explicit expression [MNZ24].Source: §2.4 · p. 12
• The work achieves constant-robustness random remote state preparation beyond BB84 and parallel self-testing of multiple EPR pairs.It reproduces the multiple-EPR-pair result of [MV21], improving on the similar result without constant robustness in [FWZ23], and extends [GV19] [GMP23] to random verifiable RSP beyond BB84. Retaining an expectation over random basis assignments avoids the prepared-qubit dependence that a hybrid argument would introduce; the random notion suffices for the Broadbent protocol [GMP23].Source: §2.4 · pp. 12–13
• The analysis shows an efficient prover cannot coherently superpose the canonical strategy and its complex conjugate, so the prepared state is computationally indistinguishable from their classical mixture.The phase ambiguity cannot be completely removed; the result extends computational self-testing from operator to state self-testing and from the Heisenberg–Weyl group to the extended Pauli group [NZ23] [MNZ24].Source: §2.4 · p. 13

2.5 Open questions

• The work has limited inter-prover state self-testing guarantees and shows only that the post-interaction state, marginalized over encrypted responses, is computationally indistinguishable from maximally mixed.Whether compiled tests admit strategies with far less entropy than the canonical EPR-pair strategy remains open; such pseudo-entanglement could constrain rounding-based approaches to quantum soundness. Merkulov and Arnon [MA25] prove entropy lower bounds for cryptographic strategies with anticommuting observables.Source: §2.4 · p. 13, §2.5 · p. 13
• Open directions include extending compiled verification to QMA, preserving witnesses, and achieving a near-ideal QMA argument with few rounds and one witness copy.The authors have not carried out the entanglement-based QMA route because of state-certification obstructions; they suggest delegating a Marriott–Watrous amplified circuit gate-by-gate for witness preservation. The long-term goal also calls for completeness and soundness negligibly close to 1 and 0, respectively, and succinctness.Source: §2.5 · pp. 13–14
• Near-perfect completeness, blindness, succinctness, and reduced round complexity remain protocol-improvement directions.The proposed routes include parallelizing the CHSH test with multi-qubit observables, delegating a universal circuit for blindness at additional logarithmic resource overhead, and using black-box compilation [BLM26] or group-self-test sparsification [MNZ24] [dlS25].Source: §2.5 · p. 14

2.6 Paper outline

• The paper develops background and the Clifford rigidity test, then applies its state-characterization result to prove an efficient CVQC protocol and an argument system for every language in BQP.Section 4 proves the state-characterization theorem for remote preparation of Broadbent-protocol states; Section 5 establishes completeness and soundness for Q-CIRCUIT, with constant sequential repetitions yielding bounds of 2/3 and 1/3.Source: §2.6 · p. 14

Sets and bitstrings

• Bitstrings use [n] for indices, Hamming weight for the number of ones, and restriction or projection to specify selected coordinates.The paper also uses element-wise complement and the unit string e_i for position i.Source: Sets and bitstrings · p. 15

Hilbert spaces, states, and operators

• The paper works with finite-dimensional complex Hilbert spaces, represents pure states by kets and density matrices, and uses the operator norm as its default.Observables are binary unless stated otherwise; the computational-basis transpose is denoted M^T.Source: Hilbert spaces, states, and operators · pp. 15–16

Fourier transform; Measurements and observable families; Expectations and probability distributions

• The notation defines Walsh–Hadamard transforms, question-indexed projectors and associated observables, and expectations that are uniform when their sampling set is specified.Non-uniform expectations identify their distribution explicitly.Source: Fourier transform · p. 16, Measurements and observable families · p. 17, Expectations and probability… · p. 17

Pauli group; Extended Pauli group

• The extended Pauli group C_n is generated by a central phase and single-qubit generators, has a unique normal form, and contains 2^(3n+2) elements.The paper distinguishes the true Pauli matrices from untrusted prover operators.Source: Extended Pauli group · pp. 19–20, Pauli group · p. 19

Extended Pauli group

• C_n has classical irreducible representations that collapse certain generators to commuting operators and quantum irreducible representations of dimension 2^n; its defining representation is injective.The classical representations have dimensions 2^k, while the quantum representations map the central phase to i or -i.Source: Extended Pauli group · p. 20

3.3 Quantum Fourier transform

• The quantum Fourier transform over C_n is shown to be unitary and to block-diagonalize the group’s left regular representation.The argument uses orthogonality of irreducible representations and character identities.Source: §3.3 · pp. 21–22

Explicit QFT circuit

• An explicit circuit implements the quantum Fourier transform over C_n using the chosen irreducible-representation basis and the unique bit encoding of group elements.The circuit is shown in Figure 3, with parallel gates interpreted as simultaneous operations.Source: Explicit QFT circuit · pp. 22–23, Figure 3 · p. 23

3.4 Bell states

• The four Bell states form an orthonormal basis of maximally entangled states, are simultaneous eigenstates of σ_X⊗σ_X and σ_Z⊗σ_Z, and support a transpose identity for the EPR state.Twirling by the single-qubit Pauli group dephases a two-qubit state into the Bell basis.Source: §3.4 · pp. 23–24

This induces the state-dependent (semi) norm

• The state-dependent distance uses an isometry to compare operators on different spaces, while δ-equivalence compares operators on the same space and is reflexive and transitive.The isometry relation is transitive but not reflexive; the paper uses δ-equivalence as its main distance notion.Source: This induces the state-dependent… · p. 25

3.6 Nonlocal games

• A nonlocal game specifies question and answer sets, a question distribution, and a verifier; its local and entangled values are optimal classical and quantum winning probabilities.Classical strategies map each player’s questions to answers, while quantum strategies use projective measurements on separate systems.Source: §3.6 · p. 26

3.7 Cryptography

• Under polynomial hardness, λ must scale as n^Ω(1), while sub-exponential hardness permits λ = (log n)^Θ(1/δ), yielding quasilinear poly(λ)·n overhead.The paper defines polynomial hardness using nuQPT adversaries and negligible advantages, and sub-exponential hardness using circuits of size 2^O(λ^δ) and advantages 2^-Ω(λ^δ).Source: §3.7 · p. 27
• The paper instantiates QFHE with Brakerski’s leveled scheme, whose security reduces through classical FHE to LWE with polynomial loss.Its hybrid ciphertext combines a quantum-one-time-pad-encrypted state with classical FHE encryptions of the pad keys.Source: §3.7 · p. 28

3.7.1 The KLVY transform

• The KLVY transform [KLVY23] encrypts Alice’s question, has the prover return an encrypted response and then a response to Bob’s clear question, and accepts after decryption and verification.The verifier decrypts α and checks whether V(x, y, a, b) = 1.Source: §3.7.1 · p. 29

3.7.2 Modeling prover strategies in a compiled game

• In a compiled game, one prover acts on the same state across rounds, so the model absorbs first-round actions into an initial pure state and represents each round with projective measurements, following [NZ23] [MNZ24].The first measurement defines a sub-normalized post-Alice state; the later measurement models the prover’s response to the clear question.Source: §3.7.2 · pp. 29–30

3.7.3 Security of the cryptography

• IND-CPA security makes post-encryption prover states for different questions computationally indistinguishable even when the distinguishing measurement depends on the first-round outcome α, up to a cryptographically small η(λ).The comparison allows expectation over different questions, and η(λ) depends on the encryption security parameter, prover, and distinguishing procedure.Source: §3.7.3 · pp. 30–31
• Under IND-CPA security, efficient provers’ bounded-outcome measurements differ by a cryptographically small amount across efficiently sampleable question distributions with identical parameter marginals.The measurement family is uniformly efficient in the shared parameter and question, and its outcomes satisfy |beta| = O(1).Source: §3.7.3 · p. 32
• The distribution-switching guarantee extends to uniformly efficient linear combinations of unitaries, allowing their state arguments to be switched between the same distributions.A further isometry version applies the switching argument to norms involving unitaries on the input and output spaces of a QPT-implementable isometry.Source: §3.7.3 · pp. 35–36

3.7.4 QFHE Overhead

• The construction instantiates QFHE with Brakerski’s scheme to estimate total resources; the authors believe [GV24] may also be efficient but did not detail its resource estimate.Brakerski’s scheme improves on Mahadev’s original proposal.Source: §3.7.4 · p. 37
• QFHE encryption adds a multiplicative poly(lambda) overhead in all resources, but requires compiling the evaluated circuit into Clifford + Toffoli gates.The evaluated circuit is the honest Alice strategy: it takes the verifier’s question and Alice’s quantum state as input, then performs the question-dependent measurement.Source: Table 4 · p. 37, §3.7.4 · p. 37
• The honest prover’s rigidity-test measurements comprise large-answer basis measurements, up to three simultaneous compatible binary measurements, and Bell-basis measurements on brick-wall pairings.These measurement types occur across the cited protocols, including the Clifford test for the Bell-basis measurements.Source: §3.7.4 · pp. 37–38
• QFHE costs O(poly(λ)polylog(g)g); under polynomial LWE hardness this is O(g^(1+ε)) for every ε > 0, and under sub-exponential hardness it is eO(g).The bounds follow by substituting circuit size O(g poly(log g)) and classical input size O(g) into the QFHE resource estimate.Source: §3.7.4 · p. 38

3.8 Approximate group representations

• The stability results extend to averages over arbitrary group measures, and the explicit GH isometry yields a tighter anti-symmetric distance bound and a simpler proof.The section describes the proof as relying almost entirely on elementary linear algebra and quantum-information facts.Source: §3.8 · p. 39
• Theorem 3.1 strengthens [MNZ24, Theorem 3.1] using the GH isometry and a representation formed from all irreducible representations of G.The theorem’s stated setup ranges over every g in G and every positive operator ρ.Source: §3.8 · p. 39
• The GH isometry is efficiently implementable when the quantum Fourier transform, group operations, and controlled-f are QPT-implementable in log |G| and λ.Under these conditions, the isometry satisfies the theorem’s representation-approximation guarantee for all g in G and positive operators ρ.Source: §3.8 · p. 41

4.1 Protocols

• Each invoked leaf test is wrapped by a consistency check that compares matching answers on sampled Alice- or Bob-marginal questions.The wrapper preserves perfect honest completeness; its soundness analysis relates wrapped success to test success and question-distribution self-consistency.Source: §4.1 · p. 41
• The commutation test checks Alice’s two-observable answers against Bob’s single-observable answer, while anti-commutation uses a Mermin–Peres Magic Square game.In the anti-commutation game, Alice receives a row or column and Bob receives a cell; their answers must agree at the intersection and satisfy the row or column parity rule.Source: §4.1 · p. 43
• The commutation-relation and product-relation tests combine small/large-answer consistency with commutation or anti-commutation checks and product-parity checks.The product-relation test compares Alice’s paired outcomes with Bob’s answer using the sampled even-weight string and its half-weight parity.Source: §4.1 · pp. 44–45
• The Clifford conjugation test composes conjugation, small/large-answer consistency, and mixed-versus-pure basis tests over its question symbols.Its conjugation component invokes the conjugation test on three selected observable tuples; the other components use SLC and MBT subtests.Source: §4.1 · p. 45
• The full Clifford test samples among six checks: Clifford-group relations, Bell-basis consistency, sign consistency, mixed-versus-pure basis consistency, CHSH, and another basis test.The Clifford-group test combines Pauli and Clifford commutation, product, and conjugation checks; the full test also uses brick-wall pairings for its Bell-basis and sign-consistency checks.Source: §4.1 · pp. 45–46

4.1.1 Honest prover strategy

• Questions include single symbols W, symbol-and-bitstring pairs (W, a), and length-n mixed-basis strings; the conjugation test also uses auxiliary observables.Here Σ = {X, Y, Z, F, G}; auxiliary symbols are C_AB, X_C, Z_C, and X_R.Source: §4.1.1 · p. 46, Table 5 · p. 47
• By the consistency convention, Alice performs the transpose of the operations specified for each question.Source: §4.1.1 · p. 46
• The prover needs one additional EPR pair for the magic-square test, beyond the control qubit required for the conjugation test.The magic-square test is standard in the self-testing literature; the passage refers readers to [CHTW04] for details.Source: §4.1.1 · p. 47
• The set Q_A includes every Bob question of a wrapped leaf, and every Alice question of a wrapped leaf is also asked of Bob.Source: §4.1.1 · p. 47

4.2 Compiled prover switching

• Cross-consistency is treated as a separate condition on uniformly efficient PVM families, alongside ε-self-consistency of a question distribution.The section’s corollary derives a bound from cross-consistency by applying Lemma 4.2 with a specified function and full bit-string set.Source: §4.2 · pp. 48, 50
• Success 1 − ε in compiled consistency game CON(T) implies success at least 1 − 2ε in T, and ε-self-consistency of every question distribution in T.The compiled execution wraps the leaf test with a consistency check.Source: §4.2 · p. 48
• The switching lemmas use efficient linear combinations of unitaries and self-consistent question distributions to relate state-dependent norm bounds across questions.The section also gives a tighter two-sided bound with square-root dependence on ε.Source: §4.2 · pp. 51, 53
• Self-consistency makes the prover’s state an approximate eigenstate of the corresponding observable, allowing that observable to be introduced or removed on the right of a state-dependent norm.The paper says this switching bound is loose, while retaining the best ε dependence for that purpose.Source: §4.2 · pp. 52–53

4.3.1 Conjugation relation

• Success in the compiled conjugation game certifies RA ≈ε+η(λ) BR and AR ≈ε+η(λ) RB for every q ∈ QA.The test is designed to certify the group relations needed for the extended Pauli group, using auxiliary observables whose structure supports the conjugation test.Source: §4.3.1 · p. 55

4.3.2 Mixed-versus-pure basis

• The mixed-versus-pure basis test compares answers on aligned qubits, extending pure-basis results to mixed bases and allowing the verifier to choose the mixed-basis distribution.Lemma 4.10 states a soundness guarantee for compiled-game success across each W ∈ Σ and any distribution µ′ over {0, 1}^n.Source: §4.3.2 · p. 60

4.3.3 Small/large answer consistency

• Large-answer questions yield exact linearity through Fourier-transformed projectors, but small-answer questions are needed when completeness requires simultaneous measurements across qubits.For example, σX ⊗ σX and σZ ⊗ σZ commute only when the two qubits are measured simultaneously.Source: §4.3.3 · p. 63
• The small/large-answer consistency test equates a small answer with the XOR of the corresponding restricted large answers, and Lemma 4.11 gives a soundness guarantee for efficient prover operators.The verifier sends a small-answer question to Alice and a large-answer question to Bob, accepting when the restricted XOR matches Alice’s answer.Source: §4.3.3 · p. 63
• For the leaf test f(a,b)=a, automatic self-consistency makes every Alice question available to Bob; winning with probability 1−ε implies ε-self-consistency on small-answer questions (W,a).The proof then applies Lemma 4.2 to Bob’s projectors for Q=(W,a).Source: §4.3.3 · p. 63

4.3.4 Commutation relation

• The commutation-relation test combines small-answer commutation and anti-commutation tests with small/large answer consistency to certify the relations at the large-answer level.The resulting guarantees apply for every q in QA, with a cryptographically small error term.Source: §4.3.4 · p. 64

4.3.5 Product relation

• Product-relation tests pin down y and f as products of generators; their phase-dependent relations are tested by pairing an even number of qubits.The single-qubit test is unnecessary because the correct forms of Y and F follow directly from the analysis when n = 1.Source: §4.3.5 · p. 66

4.3.6 Clifford conjugation

• The compiled Clifford conjugation test certifies approximate relationships among the prover’s efficient observables.The guarantees hold for every q in QA, up to a cryptographically small function of λ.Source: §4.3.6 · p. 68

4.3.7 Clifford group relations

• The compiled Clifford group test certifies self-consistency, linearity, commutation, product, and conjugation relations for the observables.These guarantees are used to show that the prover’s operators approximately satisfy the extended Pauli group relations.Source: §4.3.7 · p. 70

4.3.8 Rounding to an exact representation

• After the tests establish approximate group relations, the authors define an approximate representation and use a stability theorem to round it to an exact representation.The representation is defined using the prover’s observables and an operator intended to represent the phase i.Source: §4.3.8 · pp. 72–73, Defining an approximate representation · p. 74

Constructing the phase operator

• The phase operator Δ is constructed from the Y, Z, and X observables, with a corresponding operator constructed from F, Z, and G.The analysis establishes properties of Δ, including approximate commutation with the observables.Source: §4.3.8 · p. 73, Constructing the phase operator · pp. 73–74

Defining an approximate representation

• The function f maps group elements, expressed in generator normal form, to operators built from the prover’s observables and the phase operator.The paper establishes approximate-representation guarantees for f under the compiled Clifford group test.Source: Defining an approximate representation · pp. 74–75

From approximate representation to rigidity

• The Clifford isometry applies the quantum Fourier transform over C_n to an approximate unitary representation built from the prover’s operators.The definition maps H to H′.Source: From approximate representation to… · p. 79
• Winning the compiled Clifford group test with probability 1 − ε yields an efficient isometry into a space of dimension d|C_n|^2, under which the prover’s operators satisfy the lemma’s rigidity guarantee.The guarantee ranges over W ∈ {X, Y, Z, G, F}, distributions on {0, 1}^n, and q ∈ QA.Source: From approximate representation to… · p. 80
• The isometry is efficiently implementable because group elements have efficient encodings and multiplication, the controlled representation uses classical post-processing, and the group Fourier transform is efficient.An element of C_n can be encoded in 3n + 2 qubits.Source: From approximate representation to… · p. 80
• The proof rounds the representation by distinguishing the top classical block from the conjugate block, whose dimensions are each 2^(3n+1).The rounding targets the negative-identity group element, the algebraic property identified as distinguishing classical from fundamental irreducible representations.Source: From approximate representation to… · pp. 80–81
• The proof concludes that the representations are equivalent on the post-isometry state and verifies that the constructed operators match the required X, Y, and Z operators.The argument uses the relations established for the prover’s hidden Y operator and applies a triangle inequality.Source: From approximate representation to… · p. 81

Bell-basis test

• Bell-basis testing uses Bob to check Alice’s requested Bell measurements, converting shared entanglement into entanglement within Bob’s register.For each brick-wall pairing, Lemma 4.22 bounds the deviation of Alice’s post-measurement state from the corresponding Bell-basis projection by O(ε + η(λ)).Source: §4.3.9 · pp. 82, 84

Sign consistency test

• The sign-consistency subtest checks both same-observable G correlations and mixed G–F correlations across paired qubits.Alice’s Bell outcomes determine which pairwise parity constraints Bob’s reported outcomes must satisfy; the mask selects which pairs are checked.Source: §4.3.9 · pp. 84–85

Sign ambiguity characterization

• Entanglement swapping lets the verifier test the expected pairwise correlations, while staggered brick-wall pairings prevent inconsistent G signs across different pairs.The pairings are intended to force one consistent sign choice across all G observables, either all positive or all negative.Source: §4.3.9 · p. 87
• The analysis characterizes accepted outcomes by pairwise parity constraints and combines the Bell-state and consistency guarantees to constrain the prover’s sign choices.It treats same-observable and mixed-observable cases separately before bounding outcomes with mismatched bits across a pairing.Source: §4.3.9 · pp. 87–89

4.3.9 Clifford test

• Lemma 4.29 gives an efficient isometry into dimension d|C_n|^2 for the X, Y, Z, F, and G observables, uniformly over input distributions and q in QA.Its guarantee holds for a prover winning Items 1–4 with probability 1 − ε, up to a cryptographically small function.Source: §4.3.9 · pp. 90–91
• The first five test items have optimal winning probability 1/5(4 + cos^2(pi/8)), and their CHSH subtest distinguishes the remaining global sign choice.An honest prover attains the optimum up to cryptographically small loss, and no efficient prover exceeds it by more than a cryptographically small amount.Source: §4.3.9 · p. 91
• The compiled CHSH subtest preserves the Tsirelson bound up to a cryptographically small advantage, while honest provers attain cos^2(pi/8) in that subtest.The other subtests have perfect completeness, so the full five-item test has the stated optimal probability.Source: §4.3.9 · pp. 91–92
• Theorem 4.1 extends the Clifford-observable characterization to mixed bases, with optimal test win probability 1/6(5 + cos^2(pi/8)).The guarantee applies to arbitrary distributions over {0, 1}^n and admits an efficient isometry into dimension d|C_n|^2.Source: §4.3.9 · p. 93

4.4 State characterization

• After an efficient isometry, the post-Alice qubit register is computationally indistinguishable from a fully mixed register.The characterization holds for computationally efficient provers that win Items 1–4 of the compiled Clifford group test with probability 1 − ε.Source: §4.4 · p. 96
• For provers near the optimal Clifford-test winning probability, the post-isometry, post-measurement state lies information-theoretically close to the Bob-projector image for the reported outcome.The optimal winning probability is ω* = 1/6(5 + cos^2(π/8)).Source: §4.4 · p. 98
• Grouping the post-Alice state by decrypted outcome makes it information-theoretically close to the marginalized state projected into the reported measurement outcome’s projector image.Although decryption is inefficient without the secret key, this step uses information-theoretic guarantees.Source: §4.4 · p. 99
• For efficient measurements, the post-Alice state is computationally indistinguishable from its dephased version on the phase-ambiguity flag register.This rules out a coherent superposition of the canonical and complex-conjugate Pauli-Y representations.Source: §4.4 · pp. 96, 100
• Near-optimal Clifford-test provers satisfy a random remote state preparation guarantee with γ = O((ε + η(λ))^1/2), uniform over measurement settings and outcomes.The theorem also specifies orthogonal supports for ρ0 and ρ1 with Tr[ρ0 + ρ1] = 1, and optimal winning probability ω* = 1/6(5 + cos^2(π/8)).Source: §4.4 · p. 102
• The compiled Clifford-group subtest’s 1 − O(ε + η(λ)) winning probability yields an O((ε + η(λ))^1/2) bound for efficient POVMs under the same isometry V.The argument applies a weakened version of Lemma 4.32, ignoring possible α-dependence of the POVM.Source: §4.4 · p. 104
• Inspired by Proposition 4.32 in [GMP23], the proof establishes Eq. (4.70) directly by pinching efficient POVMs and using a telescoping sum with an efficiently implementable POVM.The pinching preserves the traced quantity, and the resulting POVM is efficient given the measurement choice.Source: §4.4 · pp. 104–105
• Combining Eq. (4.70) with Eq. (4.68) by the triangle inequality and substituting the theorem’s state parameters concludes the proof.Because the W register is classical, the efficient POVM in the computational indistinguishability statement can be written in the specified form.Source: §4.4 · p. 105

5.1 Protocol

• For m = Θ(n + t), VERIFY samples a five-symbol string and runs the CLIFF state test with probability p or one of three equally likely delegation runs otherwise.The delegation runs are computation, X-test, and Z-test; each invokes the corresponding part of Broadbent’s protocol.Source: §5.1 · p. 106

5.2 Soundness

• For a no-instance, if 9||Π_0 C|0^n⟩||^2 ≤ 1/3, even a malicious prover’s delegation-game acceptance probability is at most 7/9.Source: §5.2 · p. 107
• If an efficient prover’s state-test acceptance is at least ω* − ε, its delegation-game acceptance on a no-instance is at most 7/9 + γ, where γ = O((ε + η(λ))^1/2).Here ω* = 1/6(5 + cos²(π/8)) is the optimal Clifford-test winning probability.Source: §5.2 · pp. 107–108
• Under LWE hardness for non-uniform quantum adversaries, VERIFY uses O(poly(λ, log|C|)|C|) total resources on yes-instances and has soundness at most pc − Δ on no-instances.The completeness analysis gives at least 8/9 before accounting for symbol-count, homomorphic-evaluation, and gate-synthesis errors.Source: §5.2 · pp. 109–110
• The rigidity test requires O(poly(λ) poly(log m)m) qubits and O(poly(λ)m) communication, with eO(m) resources under sub-exponential LWE hardness.Under polynomial LWE hardness, λ = m^Ω(1) yields O(m^(1+ε)) resources for every ε > 0.Source: §5.2 · p. 112

5.3 Sequential repetition

• Constant sequential repetition with independently sampled keys and questions amplifies the positive completeness-soundness gap while preserving the prover’s O(poly(λ, log |C|)|C|) total resource bound.The repetition uses classical advice; leftover states are prepared by restarting the prover rather than supplied as quantum advice.Source: §5.3 · p. 112

5.2 Soundness

• Theorem 5.1’s gap is a positive but small constant, leaving completeness and soundness near the Clifford test value and making the protocol far from practical in its current form.The analysis yields a small constant gap because a large anti-commutation-test constant propagates through the bounds; tighter analysis may reduce constants.Source: §5.3 · p. 112, §5.2 · p. 112

5.3 Sequential repetition

• Under LWE hardness, every BQP language has a single-prover classical-verifier argument with completeness 2/3, soundness 1/3, and quasilinear overhead eO(|Cx|) under sub-exponential hardness.Under polynomial hardness, the overhead is O(|Cx|^(1+ε)) for every ε > 0.Source: §5.3 · p. 114

• The compiled commutation and anti-commutation lemmas consider efficient provers succeeding with probability 1−ε and state guarantees for every q∈QA with cryptographically small η(λ).Source: §A.1 · pp. 115–116
• The commutation proof uses the encrypted tuple check, uniform verifier choice, and approximate ±identity action to derive approximate commutation.Source: §A.1 · p. 115
• Efficient commutator and anti-commutator linear combinations of unitaries let the analysis switch the state used in the guarantee.Source: §A.1 · p. 116
• The extension also holds under sub-exponential LWE hardness, with η(λ):=52η′(λ) cryptographically small.Source: §A.1 · p. 116

• Circuit gate choices replicate the required phases and cross-register correlations represented by delta functions.Source: §A.2 · p. 116
• For the ℓ0=0 branch, the analysis combines controlled gates, a Hadamard, Toffoli, and swaps to specify the first part of the circuit.Source: §A.2 · pp. 116–117
• The ℓ0=1 branch is analyzed after Hadamard, T, S, and CZ gates, with two final CZ gates producing its stated transformation.Source: §A.2 · pp. 117–118
• Combining both halves, the circuit implements the desired operation.Source: §A.2 · p. 118
• A constant number of gates per qubit implements UQFT in O(n), efficiently under the stated relation between n and λ.Source: §A.2 · p. 118

• The section defines the Fourier transform for functions g: Z_2^n→L(H).Source: §A.3 · pp. 118–119
• Lemma A.3 states Parseval’s identity for the defined Fourier transform.Source: §A.3 · p. 118
• Corollary A.1 follows by applying Parseval’s identity and the state-dependent norm definition, using trace linearity.Source: §A.3 · p. 119

A.4 Useful results

• If ∥(VR − SV)|ψ⟩∥₂ ≤ ε, then ∥(R − V†SV)|ψ⟩∥₂ ≤ ε.The lemma assumes R and S are unitaries, V is an isometry, and |ψ⟩ may have squared norm α.Source: §A.4 · p. 119
• For the first implication, the proof shows SV|ψ⟩ lies primarily in V’s image space, then combines the resulting bounds with the triangle inequality.The projection is ΠV = VV†, and the proof uses that R is unitary.Source: §A.4 · p. 119
• For the reverse implication, the proof uses a supremum identity and Cauchy–Schwarz, then the variational definition of the operator norm and Cauchy–Schwarz.The proof concludes the second implication after applying these bounds.Source: §A.4 · p. 120