Theorem 10.1 — quantum soundness of the total-degree diagonal line-versus-point test with
OpenDiagLinesLDT.Supplement.theorem_10_1Let be any finite field, let and , and let
be a projective strategy accepted by the degree- total-degree diagonal line-versus-point test with probability at least , where . For every real , put
Then there are projective measurements such that all three of the following disagreement probabilities are at most :
- averaged over , Alice's point outcome disagrees with the value at of Bob's polynomial outcome ;
- averaged over , Bob's point outcome disagrees with the value at of Alice's polynomial outcome ;
- Alice's and Bob's full polynomial labels from and disagree.
Equivalently, in the paper's notation,
and .
This is the paper's soundness theorem for total degree: high acceptance forces both provers' point measurements to be jointly explained, up to the explicit error, by consistent global polynomials of total degree at most .
Formalization Note Finite field types encode all prime powers . The parameter remains real. The literal sampler includes and singleton lines, and no hypothesis such as or is imposed. The three relations are expanded as their probability-style disagreement sums.
Differences from the source:
- generalization: the theorem text leaves as an unspecified universal constant → Lean fixes ; reason: the proof on p.35 supplies this witness, yielding the source theorem with an explicit quantitative constant
- encoding: a prime power and finite-dimensional complex Hilbert spaces → an arbitrary finite field type with and matrix spaces ; reason: every finite field has prime-power cardinality and every finite-dimensional complex Hilbert space admits such coordinates
- encoding: points in , affine-line questions, function answers on a line, and projective measurements → points as
Fin m → F, line questions as point sets, answers as dependent functions on those sets, and PVMs as Hermitian idempotent matrix families; reason: these are coordinate and bundling conventions that preserve exactly the source questions, answers, and strategies - encoding: functions whose unique reduced representatives have total degree at most → functions admitting a multivariate representative of total degree at most ; reason: reduction modulo preserves the function and cannot increase total degree, so the outcome classes coincide
- encoding: the notation → explicit averaged sums of the real parts of over unequal outcomes; reason: tensor products of projectors have real nonnegative expectations, so taking the real part preserves exactly the probability-style consistency convention of §9
import Mathlib import Definitions.Def_DiagLinesLDT_Supplement_TotalDegreeStrategy
namespace DiagLinesLDT.Supplement
set_option autoImplicit false
/-- Theorem 10.1 (Quantum soundness of the total-degree diagonal line-vs-point test), Zhao, Fu,
Yu, *The Role of Diagonal Lines in Quantum Low-Degree Testing*, STOC 2027 submission (PDF of
2026-11-03, sha256 831c30c6…), p.27, with the proof's explicit universal constant `C0 = 2000000`
from p.35.
For every finite field, every normalized projective strategy accepted with probability at least
`1-epsilon`, and every real `k >= m*d`, there are total-degree-at-most-`d` projective polynomial
measurements on both provers whose two cross-prover point-value inconsistency errors and their
polynomial-label inconsistency are at most `soundnessError q m d epsilon k`.
**Formalization Note** Finite fields encode the paper's prime-power `q`. Hilbert spaces are finite
coordinate spaces over `C`, matrices act on them, and Alice's tensor factor is left. `DiagDirection`
retains `v = 0`, so singleton queries occur literally. `TotalDegreeFunction` is the function-level
reduced-polynomial outcome class. The relation is the paper's averaged disagreement probability,
not an operator norm. The theorem keeps `k` real and imposes no `q > m*d` side condition. -/
theorem theorem_10_1 :
∀ (F : Type*) [Field F] [Fintype F] [DecidableEq F]
(m d : ℕ) (hm : 0 < m) (epsilon k : ℝ),
0 ≤ epsilon → epsilon ≤ 1 → (m * d : ℕ) ≤ k →
∀ (iotaA iotaB : Type*) [Fintype iotaA] [DecidableEq iotaA]
[Fintype iotaB] [DecidableEq iotaB]
(S : TotalDegreeStrategy F m d iotaA iotaB),
S.IsProjective → 1 - epsilon ≤ totalDegreeAcc S →
∃ (GA : TotalDegreeFunction F m d → Matrix iotaA iotaA ℂ)
(GB : TotalDegreeFunction F m d → Matrix iotaB iotaB ℂ),
MIPRE.IsPVM GA ∧ MIPRE.IsPVM GB ∧
DiagLinesLDT.uniformAvg (fun u : Fin m → F =>
inconsistency S.state (fun a => S.pointA u a) (fun a => pointValue GB u a)) ≤
soundnessError (Fintype.card F) m d epsilon k ∧
DiagLinesLDT.uniformAvg (fun u : Fin m → F =>
inconsistency S.state (fun a => pointValue GA u a) (fun a => S.pointB u a)) ≤
soundnessError (Fintype.card F) m d epsilon k ∧
inconsistency S.state GA GB ≤ soundnessError (Fintype.card F) m d epsilon k := by sorry
end DiagLinesLDT.Supplement