QPBT definitions: Observables / WinImplications / LowDegree
DefinitionQPBT_QPBT_Observables_WinImplications_LowDegreeqpbt
This bundle defines the low-degree verifier edges and the decomposition of a Pauli seed used in win-implication arguments. It introduces the canonical line-point enumeration, discarded remainder coordinates, shared tuple split, and the four verifier-edge types.
Principal definitions:
MIPStarRE.QPBT.WinImplications.linePointFintypeCanonical: the finite enumeration of canonical line points.MIPStarRE.QPBT.WinImplications.PauliLdRemainder: the low-degree remainder coordinates.MIPStarRE.QPBT.WinImplications.PauliSharedRemainder: the coordinates discarded by the shared projection.MIPStarRE.QPBT.WinImplications.pauliSharedSplit: splits a Pauli seed into shared and discarded components.MIPStarRE.QPBT.WinImplications.alinePointEdge: the axis-line to point verifier edge.MIPStarRE.QPBT.WinImplications.dlinePointEdge: the diagonal-line to point verifier edge.MIPStarRE.QPBT.WinImplications.pointPauliEdge: the point to Pauli verifier edge.MIPStarRE.QPBT.WinImplications.pairWPairEdge: the Pair-W to Pair verifier edge.
Formalization Credit. This Lean declaration is part of the Quantum Pauli basis test formalization by Ruixuan Deng. The source code was generated by AI agents; Ruixuan Deng is the responsible maintainer.
Mathematical Source. The mathematical source is Ji, Natarajan, Vidick, Wright, and Yuen, MIP*=RE, arXiv:2001.04383v3.
Definition code
-- Generated from QPBT/Observables/WinImplications/LowDegree.lean by skeleton subtraction.
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_AxisParallelLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DiagonalLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LinePolynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LowDegreePolynomial
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OpFamily
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersBase
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersFiniteAnswers
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_QuantumState
import Definitions.Def_LIDT_MIPStarRE_LDT_CommutativityPoints_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_ExpansionHypercubeGraph_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Families
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Interpolation
import Definitions.Def_LIDT_MIPStarRE_LDT_Tactic_AvgCongr
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_Pauli
import Definitions.Def_QPBT_QPBT_Games_Defs
import Definitions.Def_QPBT_QPBT_Observables_Anticommuting
import Definitions.Def_QPBT_QPBT_Observables_Defs
import Definitions.Def_QPBT_QPBT_Observables_LineDefs
import Definitions.Def_QPBT_QPBT_Observables_WinImplications_Setup
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Definitions.Def_QPBT_QPBT_Test_MagicSquare
import Definitions.Def_QPBT_QPBT_Test_PauliBasisTest
import Mathlib
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.Quantum
end LIDT.MIPStarRE.Quantum
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
namespace MIPStarRE.QPBT.WinImplications
end MIPStarRE.QPBT.WinImplications
/-!
# Low-degree winning implications
This module proves the exact line-point and Pauli-basis consistency bounds.
## References
The line-point and Pauli-basis consistency theorems prove items 2 and 3
of `lem:qld-win-implications`
from `references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:192-267`
and blueprint `lem:qld-win-implications` and `lem:qld-win-implications-obs`.
-/
@[expose] public section
open scoped BigOperators Matrix ComplexOrder
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT hiding Measurement
open LIDT.MIPStarRE.Quantum
noncomputable section
namespace WinImplications
local instance (priority := 10) instDecidableRel_qPBT {α β : Type*} (r : α → β → Prop) :
DecidableRel r :=
fun a b => Classical.propDecidable (r a b)
local instance linePointFintypeCanonical (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :
Fintype (_root_.MIPStarRE.QPBT.LineDesc P.toLdParams ×
(Fin P.toLdParams.m → _root_.MIPStarRE.QPBT.ScalarQ P.toLdParams)) :=
_root_.MIPStarRE.QPBT.linePointFintype P
/-- Coordinates outside one low-degree register in the Pauli seed. -/
abbrev PauliLdRemainder (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :=
(Fin P.m → _root_.MIPStarRE.QPBT.PauliScalar P) × _root_.MIPStarRE.QPBT.PauliScalar P × _root_.MIPStarRE.QPBT.PauliScalar P
/-- Split a Pauli seed into a basis-selected low-degree seed and unused coordinates. -/
def pauliLdSplit (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind) :
_root_.MIPStarRE.QPBT.PauliSpace P ≃ _root_.MIPStarRE.QPBT.LdSpace P.toLdParams × _root_.MIPStarRE.QPBT.WinImplications.PauliLdRemainder P where
toFun z :=
(_root_.MIPStarRE.QPBT.pauliToLd P W z,
(match W with | .X => _root_.MIPStarRE.QPBT.pauliZBlock z | .Z => _root_.MIPStarRE.QPBT.pauliXBlock z,
_root_.MIPStarRE.QPBT.pauliRXBlock z, _root_.MIPStarRE.QPBT.pauliRZBlock z))
invFun zr := fun i =>
match i with
| .inl (.inl (.inl (.inl (.inl j)))) =>
match W with
| .X => zr.1 (.inl (.inl j))
| .Z => zr.2.1 j
| .inl (.inl (.inl (.inl (.inr j)))) =>
match W with
| .X => zr.2.1 j
| .Z => zr.1 (.inl (.inl j))
| .inl (.inl (.inl (.inr _))) => zr.1 (.inl (.inr ()))
| .inl (.inl (.inr j)) => zr.1 (.inr j)
| .inl (.inr _) => zr.2.2.1
| .inr _ => zr.2.2.2
left_inv z := by
funext i
rcases i with ((((j | j) | u) | j) | u) | u <;> cases W <;> rfl
right_inv zr := by
rcases zr with ⟨z, other, rX, rZ⟩
apply Prod.ext
· funext i
rcases i with (j | u) | j <;> cases W <;> rfl
· cases W <;> rfl
/-- Coordinates discarded by the shared Pair and Magic Square projection. -/
abbrev PauliSharedRemainder (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :=
_root_.MIPStarRE.QPBT.PauliScalar P × (Fin P.m → _root_.MIPStarRE.QPBT.PauliScalar P)
/-- Split a Pauli seed into its shared tuple and discarded scalar/direction blocks. -/
def pauliSharedSplit (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :
_root_.MIPStarRE.QPBT.PauliSpace P ≃ _root_.MIPStarRE.QPBT.PauliTuple P × _root_.MIPStarRE.QPBT.WinImplications.PauliSharedRemainder P where
toFun z :=
((_root_.MIPStarRE.QPBT.pauliXBlock z, _root_.MIPStarRE.QPBT.pauliZBlock z, _root_.MIPStarRE.QPBT.pauliRXBlock z, _root_.MIPStarRE.QPBT.pauliRZBlock z),
_root_.MIPStarRE.QPBT.pauliScalarBlock z, _root_.MIPStarRE.QPBT.pauliDirectionBlock z)
invFun zr := fun i =>
match i with
| .inl (.inl (.inl (.inl (.inl j)))) => zr.1.1 j
| .inl (.inl (.inl (.inl (.inr j)))) => zr.1.2.1 j
| .inl (.inl (.inl (.inr _))) => zr.2.1
| .inl (.inl (.inr j)) => zr.2.2 j
| .inl (.inr _) => zr.1.2.2.1
| .inr _ => zr.1.2.2.2
left_inv z := by
funext i
rcases i with ((((j | j) | u) | j) | u) | u <;> rfl
right_inv zr := by
rcases zr with ⟨⟨uX, uZ, rX, rZ⟩, scalar, direction⟩
rfl
/-- Split a low-degree seed into its point and unused scalar/direction blocks. -/
def ldPointSplit (L : _root_.MIPStarRE.QPBT.LdParams) :
_root_.MIPStarRE.QPBT.LdSpace L ≃ (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) × (_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) where
toFun z := (z.point, z.seed, z.direction)
invFun zr := fun i =>
match i with
| .inl (.inl j) => zr.1 j
| .inl (.inr _) => zr.2.1
| .inr j => zr.2.2 j
left_inv z := by
funext i
rcases i with (j | u) | j <;> rfl
right_inv zr := by
rcases zr with ⟨point, seed, direction⟩
rfl
/-- The axis-line/point verifier edge in one Pauli basis. -/
def alinePointEdge (W : _root_.MIPStarRE.QPBT.PauliKind) : _root_.MIPStarRE.QPBT.PauliEdge :=
⟨(.aline W, .point W), by simp [_root_.MIPStarRE.QPBT.pauliEdges]⟩
/-- The diagonal-line/point verifier edge in one Pauli basis. -/
def dlinePointEdge (W : _root_.MIPStarRE.QPBT.PauliKind) : _root_.MIPStarRE.QPBT.PauliEdge :=
⟨(.dline W, .point W), by simp [_root_.MIPStarRE.QPBT.pauliEdges]⟩
/-- The point/Pauli verifier edge in one Pauli basis. -/
def pointPauliEdge (W : _root_.MIPStarRE.QPBT.PauliKind) : _root_.MIPStarRE.QPBT.PauliEdge :=
⟨(.point W, .pauli W), by simp [_root_.MIPStarRE.QPBT.pauliEdges]⟩
/-- The Pair-W/Pair verifier edge in one Pauli basis. -/
def pairWPairEdge (W : _root_.MIPStarRE.QPBT.PauliKind) : _root_.MIPStarRE.QPBT.PauliEdge :=
⟨(.pairW W, .pair), by simp [_root_.MIPStarRE.QPBT.pauliEdges]⟩
/-- The point/Pair-W verifier edge in one Pauli basis. -/
def pointPairWEdge (W : _root_.MIPStarRE.QPBT.PauliKind) : _root_.MIPStarRE.QPBT.PauliEdge :=
⟨(.point W, .pairW W), by simp [_root_.MIPStarRE.QPBT.pauliEdges]⟩
/-- Source-answer mismatch mass for the completed line and point readouts. -/
noncomputable def lowDegreeMismatchMass {P : _root_.MIPStarRE.QPBT.AdmissibleParams} {ε : ℝ}
(S : _root_.MIPStarRE.QPBT.ProjectiveSetting P ε) (W : _root_.MIPStarRE.QPBT.PauliKind)
(sample : _root_.MIPStarRE.QPBT.LineDesc P.toLdParams × (Fin P.m → _root_.MIPStarRE.QPBT.PauliScalar P)) : ℝ :=
_root_.MIPStarRE.QPBT.outcomeEventWeight S.toStrategy
(_root_.MIPStarRE.QPBT.ProjectiveSetting.lineQuestion P W sample.1)
(_root_.MIPStarRE.QPBT.ProjectiveSetting.pointQuestion P W sample.2)
(fun A B =>
_root_.MIPStarRE.QPBT.evalOpt sample.1 sample.2
(_root_.MIPStarRE.QPBT.ProjectiveSetting.lineAnswerOrZero P sample.1 A) ≠
some (_root_.MIPStarRE.QPBT.ProjectiveSetting.pointAnswerOrZero B))
end WinImplications
end
end MIPStarRE.QPBT
Source