Interactive Proofs for Quantum Computations

1.1 Motivation

• The paper addresses the inability to classically predict large quantum systems by asking whether a classical verifier can test arbitrary quantum computations and delegated results.The motivation includes testing quantum computers, detecting errors or dishonesty in delegated computation, and verifying BQP-complete tasks beyond factoring.Source: §1.1 · pp. 2–3

1.2 Quantum Prover Interactive Proofs (QPIP)

• QPIP models a BQP prover interacting with a BPP verifier that has access to only κ qubits, with completeness c and soundness s separated by a constant.The verifier may perform arbitrary operations on its κ-qubit register, while polynomially many classical bits and κ-qubit quantum messages can be exchanged; the basic definition is asymmetric, with a symmetric variant also given.Source: §1.2 · pp. 3–4

1.3 Main Results

• For Q-CIRCUIT_γ, the main protocol achieves completeness 1−γ and soundness γ+ϵ using QPIP protocols requiring O(log(1/ϵ)) qubits.Q-CIRCUIT_γ is BQP-complete when 1−2γ exceeds 1/poly(n), and the theorem applies for 0<ϵ<1 and γ<1−ϵ.Source: §1.3 · p. 4
• Theorem 1.2 establishes that BQP = QPIP_c for some constant c, with soundness against an unbounded prover and a symmetric-version equality as well.The result is obtained through Q-CIRCUIT, a BQP-complete problem, and constant-parameter instantiation of Theorem 1.1.Source: §1.3 · pp. 4–5

1.3.1 Clifford QAS based QPIP

• The Clifford QAS authenticates n qubits with e auxiliary zeros and security ϵ=2^-e, yielding a QPIP in which the verifier repeatedly decodes, applies gates, reauthenticates, and communicates quantumly in both directions.This construction is simple but requires two-way quantum communication.Source: §1.3.1 · p. 5

1.3.2 Polynomial code QAS based QPIP

• The polynomial-code QAS has security ϵ=2^-d and enables universal computation through authenticated magic states, Clifford operations, measurements, and verifier-assisted corrections.The prover receives authenticated inputs and magic states initially; after the first round, further interaction is classical, and the resulting protocol has completeness 1−γ and soundness γ+ϵ.Source: §1.3.2 · pp. 5–6

1.3.3 Blindness

• Both QPIP constructions are blind: throughout the protocol, the prover’s state remains independent of the delegated circuit and input.Blindness is achieved using a fixed universal quantum circuit; the polynomial-code proof is more involved because of classical interaction.Source: §1.3.3 · pp. 6–7

1.3.4 Interpretation

• Acceptance implies closeness to the correct final state only when the verifier’s non-abort probability is high, while under a hardness-distribution assumption, passing the test can show that the prover is not simulable by BPP.For both schemes the conditional trace-distance bound is at most ϵ, with the polynomial-code statement restricted to standard-basis final states; Corollary 1.13 gives the computational-power conclusion under its stated β, γ, and ϵ condition.Source: §1.3.4 · pp. 7–8

1.4.1 Clifford QAS

• The Clifford QAS uses operator decoherence: random Clifford encoding maps every nonidentity attack to a uniform mixture of nonidentity Paulis, which auxiliary-state checks detect with high probability.This security argument underlies the Clifford QAS theorem.Source: §1.4.1 · p. 8

1.4.3 Polynomial based QAS

• The polynomial QAS combines Pauli decoherence with signed-polynomial-code security, because Pauli-key randomization reduces general attacks to Pauli mixtures but does not make them uniform.The sign key prevents nonidentity Pauli attacks from preserving the code for more than two sign keys, while omitting the Pauli key leaves general attacks insecure.Source: §1.4.3 · pp. 8–9

1.4.4 Polynomial based QPIP

• The polynomial QPIP cannot directly reduce soundness to QAS security: transcript fixing and final projection partition the prover’s space so attack shifting becomes possible despite adaptive classical interaction.The proof uses Pauli decoherence and sign-key security within each fixed-transcript partition, rather than treating the polynomial QAS theorem as a black box.Source: §1.4.4 · p. 9

1.4.5 Blindness

• Blindness follows from random Clifford encodings or Pauli keys and uniformly distributed measurement results, which prevent the prover from learning the input state.For the polynomial scheme, maliciously altered measurement results remain uniformly distributed because attacks reduce to Pauli mixtures.Source: §1.4.5 · pp. 9–10

1.4.2 Clifford QPIP

• The Clifford QPIP shifts prover attacks to the final round using Clifford decoherence, but correctness must be checked only at the end; each-round checks make the original protocol unsound.The conference protocol permitted small deviations to accumulate across polynomially many rounds, while the corrected protocol requires two-way quantum communication in every round.Source: §1.4.2 · p. 8, §1.5.1 · p. 10

1.5.2 Fault Tolerance

• The journal version retracts the claimed fault-tolerance result because purification can leak the sign key, leaving blind verifiable QPIPs fault tolerant even with polylogarithmic verifier space unresolved.Several alternative approaches also fail or lack security proofs, including repeated correction checks, prover-generated authenticated states, and noisy-to-ideal reductions.Source: §1.5.2 · p. 11, §1.7 · pp. 12–13

1.6 Related Work / 1.8 Conclusion and Open Questions

• Related protocols expanded blind and verifiable quantum computation, but achieving fault-tolerant blind verification with O(1) verifier qubits and eliminating the verifier’s quantum register remain open.The work also raises broader questions about interactive experiments, quantum fully homomorphic encryption, and rigorous delegated-quantum-computation security.Source: §1.6 · pp. 11–12, §1.8 · pp. 13–14

1.8 Conclusion and Open Questions

• BQP computations can be verified and delegated through interactive protocols between a BQP prover and a BPP verifier holding O(1) qubits.The journal version supplies rigorous proofs of the two QPIPs introduced in [ABOE08].Source: §1.8 · p. 13

2.1 Quantum Authentication

• Quantum authentication requires unchanged states to be accepted while interventions should cause rejection or preserve the sent state except with small probability.The formal security definition is stated for pure states and extends to mixed or entangled states.Source: §2.1.1 · p. 14

2.1.1 Quantum Security

• A QAS encodes l qubits into m = l + e qubits using a random key, then decodes and checks whether the e auxiliary qubits remain in |0⟩.The encoder appends |0⟩⊗e before applying a keyed unitary, while the decoder accepts only the corresponding valid subspace.Source: §2.1.1 · pp. 14–15

2.2 Pauli and Clifford Gates in F2

• Pauli operators form a matrix basis, while Clifford operators conjugate Pauli operators to Pauli operators up to phase and can be sampled efficiently.These properties support decompositions and randomization arguments in the authentication proofs.Source: §2.2 · p. 15

2.3 Generalized Gates over Fq

• Generalized Pauli operators over Fq satisfy ZX = ωqXZ, and the background defines Fourier, SUM, Toffoli, multiplication, and controlled-phase gates.The generalized gates provide the operations used for polynomial-code computation.Source: §2.3 · p. 16, Definition 2.4 Generalized Gates · p. 16

2.3.1 Toffoli Gate by Teleportation

• A generalized Toffoli gate can be implemented using a resource state, Clifford entangling operations, measurements, and a correction that is itself Clifford by conjugation.The procedure applies the desired transformation to three registers while measuring auxiliary registers and correcting the outcomes.Source: §2.3.1 · p. 17

2.5 Signed Polynomial Codes

• Signed polynomial codes use m = 2d + 1 registers, detect up to d errors, and are self-dual; their encoding circuit interpolates polynomial values using SUM and multiplication gates.The encoding maps an input a with f(0) = a to signed evaluations k_if(α_i) across the registers.Source: §2.5 · p. 18, §2.5.2 · pp. 19–20

2.5.1 Signed Polynomial Code Logical Gates

• Logical X, Z, Fourier, and SUM operations are defined for signed polynomial codes, with SUM applied transversally between corresponding registers.The encoding operator D_k constructs the full signed codeword from the input and the first d + 1 evaluations.Source: §2.5 · p. 18, §2.5.1 · pp. 18–19

3 Clifford Authentication Scheme

• The Clifford QAS encodes |ψ⟩ with e zero qubits using a keyed Clifford operator and decodes by applying its inverse before measuring the auxiliary registers.Bob accepts only when all e auxiliary measurements are zero.Source: §3 · p. 20
• Theorem 1.4 establishes security ϵ = 2^-e for the Clifford authentication scheme.The security decreases exponentially with the number of auxiliary qubits.Source: §3 · p. 20

3.1 The Overall Proof of Theorem 1.4

• The soundness proof decomposes an adversarial attack into Pauli components and uses random Clifford conjugation to make every non-identity Pauli uniformly distributed.The remaining undetected Pauli operators are those that do not flip auxiliary qubits, yielding a projection bound of 2^-e.Source: §3.1 · p. 21, §3.3.1 · p. 22
• Interventions close to the identity are even more likely to preserve the valid authenticated-state subspace.This is a stronger consequence of the authentication proof than the basic security bound.Source: §3.1 · p. 21

3.2 Proof of Claim 3.1

• The technical proof uses Pauli and Clifford twirling plus a trace-out lemma to characterize the decoded state despite an adversary’s additional environment.These lemmas establish the decoherence and averaging steps required by Claim 3.1.Source: §3.2 · pp. 21–22, §3.3.1 · pp. 22–23

4 Quantum Interactive Proofs with Clifford Authentication

• Protocol 4.1 authenticates each input qubit, returns requested qubits to the verifier gate by gate, and reauthenticates them before sending them back to the prover.The verifier checks the final auxiliary registers and measures the decoded output qubit in the last round.Source: §4 · p. 24
• Protocol 4.1 has completeness 1 − γ and soundness γ + ϵ for Q-CIRCUITγ, with verifier resources scaling logarithmically in 1/ϵ.The theorem applies when 0 < ϵ < 1 and γ < 1 − ϵ.Source: §1.3.1 · p. 5
• The protocol’s quantum communication is linear in the number of circuit gates.For ϵ = 1/2, the stated implementation uses a four-qubit register, with three qubits sufficient when blocks are handled separately.Source: §4 · p. 24

4.1 Overall Proof of Theorem 1.5

• Completeness follows because an honest prover preserves the correctly authenticated computation, so decoding the output accepts with probability at least 1 − γ.The circuit’s own error probability is bounded by γ.Source: §4.1 · p. 24
• Soundness treats each round as an authentication instance and uses Clifford decoherence to move the prover’s attack through the rounds to the final check.The resulting claim gives soundness γ + ϵ for Q-CIRCUIT.Source: §4.1 · pp. 24–25

4.2 Proof of Claim 4.2

• The induction for Clifford QPIP state evolution combines key averaging, Pauli decomposition, unitary commutation, and fresh authentication keys after each gate.These steps preserve the claimed authenticated form of the prover’s state across successive rounds.Source: §4.1 · p. 24, §4.2 · p. 26

5 Signed Polynomial Code Authentication Scheme

• The protocol encodes a state with a signed quantum polynomial code, applies a random Pauli sign key, and accepts only when inverse decoding restores all auxiliary registers to 0.Alice chooses m = 2d + 1 and a random key k′ = (k, z, x); Bob applies the inverse Pauli and code operations before measuring the auxiliary registers.Source: §5 · p. 28
• The polynomial authentication scheme is a quantum authentication scheme with security ϵ = 2^-d.A q-dimensional system is encoded into dimension q^m = q^(2d+1), retaining exponentially good security despite less favorable parameters than the Clifford scheme.Source: §5 · p. 28, §5.1 · p. 30

5.1 The Overall Proof of Theorem 1.6

• The overall security proof uses Pauli decoherence to reduce arbitrary adversarial interventions to generalized Pauli attacks, then applies sign-key security to bound their acceptance probability.The proof’s central sign-key lemma states that the signed polynomial code is 1/2^(m−1)-secure against nonidentity generalized Pauli attacks.Source: §5.1 · pp. 28–29

5.2 Proof of Lemma 5.1

• Lemma 5.1 establishes the Pauli-decoherence reduction by averaging over Pauli conjugations, eliminating cross terms and enabling termwise analysis of Eve’s attack.The attack is decomposed as U = Σ_P P ⊗ U_P, separating the message-space Pauli operators from Eve’s environment operations.Source: §5.1 · pp. 28–29, §5.2 · p. 30

5.3.1 k-Correlated Pauli Operators

• A nonidentity Pauli can be k-correlated for at most two sign keys; every remaining attack factors into a correlated component and an uncorrelated component that changes auxiliary qudits and is detected.Thus, for a random sign key, nonidentity Pauli attacks are caught with probability 1/2^(m−1).Source: §5.3.1 · pp. 31, 33, 34
• A nonidentity k-correlated Pauli operator necessarily makes at least one auxiliary qudit nonzero, so the operator is detected.The conjugation analysis shows inverse sum and multiplication operations do not affect the relevant operator, while inverse Fourier operations convert selected Z operators to X operators.Source: §5.3.1 · p. 34

5.3.2 Proof of Lemma 5.2

• For each sign key k, a nonidentity Pauli Q decomposes into k-correlated and uncorrelated parts; the uncorrelated part is always detected and is nonidentity for at most two keys, proving that Q preserves a signed polynomial state for at most two keys.The proof sums only over sign keys for which Q is k-correlated, since all other terms vanish by the detection claim.Source: §5.3.2 · p. 35

6 Quantum Interactive Proofs with Polynomial Authentication

• The polynomial QPIP requires only one-way quantum communication because the prover applies gates directly to authenticated qudits without knowing the encoding.The verifier sends authenticated states initially; subsequent interaction is classical.Source: §6 · p. 35
• The polynomial protocol’s soundness proof is harder than the Clifford protocol’s because Pauli decoherence does not provide the uniform Pauli mixture needed to shift arbitrary attacks to the protocol’s end.Instead, the proof partitions the prover’s Hilbert space by interaction transcript and analyzes each partition using Pauli decoherence and sign-key security.Source: §6 · pp. 35–36

6.1 Application of Quantum Gates

• The logical-circuit conversion uses a universal gate set containing Fourier and Toffoli gates, with each Toffoli measurement producing β_i and a corresponding correction.The circuit is reorganized into logical operations, measurements, and correction operators acting on authenticated qudits.Source: §6.1 · p. 36, §6.1.4 · pp. 37–38
• Pauli X and Z gates are implemented by updating the verifier’s Pauli keys, while Fourier and SUM gates combine prover-applied logical operations with corresponding key updates.For Pauli operations the prover does nothing; for Fourier and SUM, the prover applies the logical gate and the verifier changes the keys according to conjugation rules.Source: §6.1.1 · p. 36, §6.1.2 · p. 37

6.1.3 Measurement

• The prover measures authenticated states and sends outcomes to the verifier, who removes Pauli keys, applies D†, checks auxiliary coordinates, and aborts on invalid results.The verifier need not apply the full decoding circuit because Z deviations do not change standard-basis measurement outcomes, whereas the procedure detects Pauli X deviations.Source: §6.1.3 · p. 37

6.1.4 Conversion to Logical Circuit

• Toffoli gates are realized through authenticated magic states, measurement results, and logical Clifford corrections; matching correction data yields the intended computation.Fact 6.1 characterizes the resulting state, and when the correction β matches the measurement result l, the Toffoli gate is applied to the initial state.Source: §6.1.4 · p. 38

6.2 Protocol Description

• The protocol uses three registers of m qudits per Toffoli round, authenticates inputs and Toffoli states with a shared sign key, and can reduce the verifier’s register to m+2 qudits.For ϵ=1/2, the stated reduction gives m=3 and a verifier register of five qudits of dimension five.Source: §6.2 · p. 39
• Protocol 6.1 has completeness 1−γ and soundness γ+ϵ for Q-CIRCUITγ.The verifier authenticates inputs and Toffoli states, performs sequential rounds of measurement and correction, and accepts according to the final decoded outcome.Source: §6.2 · p. 39

6.3 Assumptions

• The prover’s deviation can be assumed to occur after the requested round operations, represented as a unitary attack applied at the round’s end.Operations before measurement can be shifted to the previous round, so the prover first measures and performs the verifier-requested corrections.Source: §6.3 · p. 40

6.4 Notation

• Only nontrivial Pauli operators need detection because Z and identity operators cannot change standard-basis measurement results, whereas operators containing X can.The notation therefore calls Z and I operators trivial and all other Pauli operators nontrivial.Source: §6.4 · p. 40
• The protocol tracks the prover’s remaining authenticated qudits, previously returned qudits, and the verifier’s key register across rounds, while discarding keys for already decoded qudits.Figure 1 illustrates these registers and the honest prover’s gates during Protocol 6.1.Source: §6.4 · pp. 40–41, Figure 1 · p. 41

Soundness goal

• If the first qudit of U|y⟩^⊗n is 0 with probability 1−γ, the verifier aborts or rejects the final decoded result with probability at least 1−(γ+ϵ).The proof uses this as the soundness criterion for the Q-CIRCUIT instance.Source: §6.5 · p. 41

State evolution

• Claim 6.1 characterizes the shared prover–verifier state at every round as a function of prior measurement results and the prover’s adaptive attack.The state evolution is proved inductively across rounds.Source: §6.5 · pp. 41–42

Final verification

• The verifier decodes the final authenticated qudit and projects the remaining measurement registers onto valid polynomial-code outcomes while checking whether the final qudit decodes to 1.The resulting projection is bounded by γ+ϵ.Source: §6.5 · pp. 42–43

Conclusion

• Combining the trivial and nontrivial deviation bounds gives the required upper bound on the accepting projection and establishes soundness.The proof’s state simplification first mixes the prover-held registers and removes cross terms on the verifier-held registers.Source: §6.5 · p. 44

Deviation analysis

• For trivial Pauli deviations, the decoded final answer is 0 with probability 1−γ, so their contribution to accepting 1 is bounded by γ.Trivial Paulis commute with the relevant decoding and measurement operations.Source: §6.5 · p. 44
• For nontrivial Pauli deviations, the proof uses the signed polynomial code to restrict nonzero contributions to at most two sign keys.This restriction controls the contribution of nontrivial deviations after projection onto the accepting subspace.Source: §6.5 · p. 44

6.6 Proof of Claim 6.1 (Polynomial QPIP State Evolution)

• After measurement, the verifier decodes δi, transfers the measured qudits into its register, and traces out their obsolete Pauli keys.The remaining registers are relabeled for the next round.Source: §6.6 · p. 45
• The prover then applies the correction Cg(δi) and the next Clifford gates, with later attacks allowed to depend on the decoded measurement history.This dependence is represented by Ug(∆i).Source: §6.6 · p. 45
• Updating Pauli keys lets the verifier commute the logical Clifford operation through the authenticated state while preserving signed polynomial encoding.The conjugated Pauli remains a Pauli because the applied operator is Clifford.Source: §6.6 · pp. 45–46
• The induction closes because the prover’s next attack acts only on prover-held registers and can be shifted past operators acting on the verifier’s measurement register.This restores the claimed state form for the next round.Source: §6.6 · pp. 45–46

6.7 Proof of Claim 6.3 (Final State)

• The proof begins from the state after decoding the final register and traces out the key register, Pfinal, and the prover’s environment.Only Vfinal matters for the verifier’s soundness test.Source: §6.7 · pp. 46–47
• Tracing out the final key register permits summation over z and x, which mixes the prover-held register Pfinal by the Pauli mixing lemma.The sign key is kept fixed during this simplification.Source: §6.7 · pp. 46–47
• Averaging over the first Pauli keys decoheres the portion of Ug(∆L) acting on Vfinal by removing its cross terms.This produces a simpler expression for the decoded verifier state.Source: §6.7 · p. 47
• The resulting state includes the normalization factor 1/q^|Pfinal| before the prover-held registers are discarded from the verifier’s analysis.The final trace leaves only the registers relevant to verification.Source: §6.7 · p. 47

6.8.1 Necessary Claims

• The necessary claims relate encoded polynomial-code states, measurement projections, and the conjugation behavior of the encoding circuit.They provide the algebraic facts used in both deviation proofs.Source: §6.8.1 · pp. 47–48

6.8.2 Proof of Claim 6.4 (Trivial Deviation)

• For trivial Pauli deviations, decoding reduces the relevant expression to the unauthenticated state, whose final output is 1 with probability at most γ.This follows from U|0⟩^⊗n producing 0 with probability at least 1−γ.Source: §6.8.2 · pp. 48–49
• The trivial-deviation argument relies on trivial Paulis commuting with standard-basis projections and on tracing out auxiliary zero qudits that the projections do not alter.These reductions remove the authentication auxiliaries from the calculation.Source: §6.8.2 · pp. 48–49

6.8.3 Proof of Claim 6.5 (Nontrivial Deviation)

• For a nontrivial Pauli deviation, the signed-code analysis shows that only at most two sign keys can yield a nonzero projected contribution.The admissible keys depend on the deviation’s correlation pattern rather than on the input density matrix.Source: §6.8.3 · pp. 50, 52
• A nontrivial deviation can reach the accepting subspace only if it preserves the authenticated state up to trivial operators on every block.Corollary 6.9 formalizes this restriction through k-correlation.Source: §6.8.3 · p. 50
• The nontrivial-deviation proof decomposes uncorrelated components and shows their overlap with the projected authenticated subspace vanishes.The decisive inner product is zero when the residual X component is nonzero.Source: §6.8.3 · pp. 51–52

6.8.4 Proofs of Necessary Claims

• The auxiliary claims establish that decoding maps trivial operators to trivial operators, while Fourier components can create nontrivial operators only on designated registers.This supports the commutation steps used in the projection argument.Source: §6.8.4 · p. 53
• The final technical reductions use the structure of the projection and cyclicity of trace to replace ZzXx by Xx in the relevant expression.This completes the algebraic preparation for the deviation bounds.Source: §6.8.4 · pp. 53–54

• Blindness means the prover's reduced density matrix is identical across circuits and inputs, while completeness and soundness retain their QAS-style guarantees.Source: §7 · p. 55
• A universal circuit encodes both data and a circuit description, so blind computation reduces to keeping that combined input hidden from the prover.Source: §7 · p. 55
• The Clifford-based QPIP is blind because independently keyed Clifford encodings make every state sent to the prover maximally mixed, regardless of the input.Source: §7 · p. 55
• The polynomial-based QPIP is also blind, although its proof must account for classical interaction and show that decoded Toffoli measurement results are uniformly random.Source: §7 · pp. 56, 58
• For the polynomial scheme, blindness follows after Pauli mixing, decoherence, and basis projection eliminate input-dependent cross terms from the prover's state.Source: §7 · pp. 57, 59

8.1 Clifford QPIP

• The Clifford QPIP's accepted final state is within trace distance ϵ of the correct state when the verifier accepts with probability at least β.Source: §8.1 · pp. 59–60
• The Clifford analysis represents the correct output as the circuit evolution of the initial state, then applies convexity and the Clifford QAS security argument.Source: §8.1 · pp. 59–60

8.2 Polynomial QPIP

• The polynomial QPIP analyzes trace distance after measurement because the verifier performs only classical verification and therefore cannot detect phase attacks before measurement.Source: §8.2 · pp. 60–61
• The polynomial protocol's accepted measured final state is within trace distance at most 2ϵ of the correct measured state.Source: §8.2 · p. 61
• The polynomial proof decomposes the accepted state into a convex sum and treats trivial Pauli operators as preserving the correct first output qudit.Source: §8.2 · p. 62
• Nontrivial Pauli attacks remain bounded because they can pass the verifier's test for only 2 out of 2^m sign keys.Source: §8.2 · p. 62

• QPIP^sym uses the same BQP prover, hybrid verifier, and communication limits as QPIP^κ, but adds three outcomes: 1, 0, and ABORT.Source: A A Symmetric Definition of QPIP · p. 69
• Completeness requires a correct verifier outcome, while soundness bounds the verifier's mistake probability against every prover with the same description.Source: A A Symmetric Definition of QPIP · p. 69
• The paper proves QPIP^sym_c = QPIP^c by converting a QPIP protocol for a language and its complement into a symmetric protocol.Source: A A Symmetric Definition of QPIP · p. 69
• Repeated symmetric protocols with majority voting reduce the error to inverse exponential in n when the verifier's non-abort probability is constant.Source: A A Symmetric Definition of QPIP · pp. 69–70
• Under the stated distributional assumption, the resulting prover cannot be simulated by a BPP machine.Source: A A Symmetric Definition of QPIP · p. 70

• Pauli mixing cancels all off-diagonal terms and yields the normalized identity when the Pauli indices match.Source: B Clifford and Pauli Operators · p. 70
• Clifford mixing follows because a random Clifford includes a random Pauli, allowing the Pauli mixing lemma to establish the corresponding identity.Source: B Clifford and Pauli Operators · pp. 70–71

Overview

• The section proves Lemmas 3.4–3.6, which were used to prove Lemma 3.2; Lemma 3.5 was also used to prove Lemma 5.1.Source: C Clifford Technical Details · p. 71

Pauli Partitioning by Cliffords

• Clifford conjugation maps any nonidentity Pauli operator to any other nonidentity Pauli operator.The proof reduces arbitrary Paulis to X⊗I⊗m−1 using SWAP, H, and K operations, then composes Clifford operators.Source: C Clifford Technical Details · p. 71
• The sets A_P′,Q partition C_m into equal-sized classes, so their cardinalities are independent of the nonidentity Pauli labels.Conjugation by a suitable Clifford establishes equalities among class sizes, and the classes are disjoint and exhaustive.Source: C Clifford Technical Details · pp. 71–72

Pauli Twirl

• The Pauli Twirl proof cancels the relevant sum whenever the two generalized Pauli operators differ in at least one exponent.Writing P=X^aZ^b and P′=X^a′Z^b′, one of the resulting sums vanishes because a≠a′ or b≠b′.Source: C Clifford Technical Details · p. 72

Clifford Twirl

• Random Clifford conjugation includes random Pauli conjugation, enabling the Clifford Twirl identity through a change of summation order.The resulting expression is zero when C†PC differs from C†P′C by the Pauli Twirl lemma.Source: C Clifford Technical Details · pp. 72–73

Logical X

• The logical X operator is correct because applying X to the encoded components produces the intended logical operation.The proof groups polynomial terms by fixed evaluations and uses the number of admissible polynomials to simplify the resulting expression.Source: D Logical Gates on Signed Polynomial… · pp. 73–74

Logical SUM

• The logical SUM operator is proved by mapping the target encoded polynomial values to h(α_i)+f(α_i).The displayed encoded-state transformation shows the control values unchanged while the target receives the polynomial addition.Source: D Logical Gates on Signed Polynomial… · p. 73

Logical Fourier Transform

• The logical Fourier transform proof relies on Lagrange interpolation because a degree-≤m−1 polynomial is determined by its values at the evaluation points.The argument represents encoded states through polynomial values, splits sums by g(0), and temporarily restricts g so fg has degree at most m−1.Source: D Logical Gates on Signed Polynomial… · pp. 73–74

Logical Z

• The logical Z operator is verified by shifting polynomial values via f′(α)=f(α)+x.This substitution is the central transformation used in the proof of Claim 2.5.Source: D Logical Gates on Signed Polynomial… · pp. 73–74

Shared notation

• The shared notation covers circuit error γ, security parameter ϵ, circuit size N, gate count L, qubit count n, and the prover environment E.The table also defines the security projections Π0 and Π1 and distinguishes the prover environment from Eve’s environment.Source: E Notation Tables · p. 75

Polynomial protocol notation

• Polynomial-protocol notation includes the sign key k, code length m, degree d, encoding circuits E_k and D_k, and the generalized Pauli group P_m.The same table defines the initial authenticated state ρ_k containing authenticated zero and magic states.Source: E Notation Tables · p. 75

QPIP registers and rounds

• The QPIP register notation tracks prover and verifier qubits across rounds, final authenticated registers, verifier keys, and measurement results.P_i and V_i describe round-dependent holdings, while F, P_final, and V_final describe the final authenticated and transmitted registers.Source: E Notation Tables · p. 75

Protocol operations and acceptance

• Later symbols specify logical Clifford operations, Toffoli corrections, teleportation outcomes, accepting subspaces, and decoded measurement projections.These include ˜Q_i, ˜C_βi, Δ_i, l, Π̂0, and Π_Ga in the polynomial QPIP analysis.Source: E Notation Tables · p. 75