QPBT definitions: Combining / Lines / SubLineBlocks
DefinitionQPBT_QPBT_Combining_Lines_SubLineBlocksqpbt
This bundle decomposes an ambient low-degree vector into point and seed-direction blocks for restricted-line sampling. It defines the coordinate-index events, fresh diagonal directions, decoder readouts, and the uniform positive mass of every coordinate fiber.
Principal definitions:
MIPStarRE.QPBT.ldSpaceBlockEquiv: splits an ambient low-degree vector into its point block and seed-direction block.MIPStarRE.QPBT.ldSeedDirEvent: defines the coordinate-index event on the seed-direction block.MIPStarRE.QPBT.ldSeedDirEvent_decidablePred: proves decidability of the seed-direction coordinate-index event.MIPStarRE.QPBT.freshDiagonalPairDist: defines the fresh diagonal direction pair at a coordinate index using a uniform scalar seed and a uniformly sampled direction block.MIPStarRE.QPBT.aLineDescOfBlock: defines the axis-line decoder read on the block decomposition.MIPStarRE.QPBT.dLineDescOfBlock: defines the diagonal-line decoder read on the block decomposition.MIPStarRE.QPBT.ldSeedDirEvent_mass: states that each seed-direction coordinate-index event has mass one over the point dimension under the uniform law.MIPStarRE.QPBT.ldSeedDirEvent_positive: states that every seed-direction coordinate-index event has positive mass.
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/Combining/Lines/SubLineBlocks.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_Distribution
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_Games_DistributionAux
import Definitions.Def_QPBT_QPBT_Observables_LineDefs
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGameMeasurements
import Mathlib
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-!
# Independent blocks of the restricted line-point laws
This module isolates the independent generating blocks of the restricted
line-point laws used by the sampling procedure of the sub-line lemma. A
uniformly sampled low-degree vector splits into a point block and a
seed-direction block; the coordinate-index event constrains only the second
block, so conditioning on it leaves the point block uniform and independent.
The conditioned seed-direction block is the fresh diagonal direction pair of
the sub-line construction, and the uniform mixture of those pairs over the
coordinate index is the unconditioned law.
## References
The generating descriptions support `lem:qld-sublines` in
blueprint `lem:qld-sublines`, whose source is
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:1063-1116`.
The restricted laws themselves are `def:ith-restricted-line`, blueprint lines
1209--1228, paper lines 1038--1048.
-/
@[expose] public section
open scoped BigOperators
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT
noncomputable section
/-! ## The block decomposition of an ambient low-degree vector -/
/-- Split an ambient low-degree vector into its point block and its
seed-direction block. Blueprint `lem:qld-sublines`, paper
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-391`. -/
def ldSpaceBlockEquiv (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 := (_root_.MIPStarRE.QPBT.LdSpace.point z, _root_.MIPStarRE.QPBT.LdSpace.seed z, _root_.MIPStarRE.QPBT.LdSpace.direction z)
invFun w := fun i =>
match i with
| .inl (.inl j) => w.1 j
| .inl (.inr _) => w.2.1
| .inr j => w.2.2 j
left_inv z := by
funext i
rcases i with (j | u) | j <;> rfl
right_inv w := rfl
/-- The coordinate-index event of `def:ith-restricted-line` read on the
seed-direction block of an ambient low-degree vector. Blueprint
`def:ith-restricted-line`, paper
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:1038-1048`. -/
def ldSeedDirEvent (L : _root_.MIPStarRE.QPBT.LdParams) (i : Fin L.m)
(sw : _root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) : Prop :=
_root_.MIPStarRE.QPBT.chiIndex L sw.1 = i
/-- Decidability of the coordinate-index event on the seed-direction block. -/
instance ldSeedDirEvent_decidablePred (L : _root_.MIPStarRE.QPBT.LdParams) (i : Fin L.m) :
DecidablePred (_root_.MIPStarRE.QPBT.ldSeedDirEvent L i) := by
intro sw
unfold _root_.MIPStarRE.QPBT.ldSeedDirEvent
infer_instance
/-- Each coordinate-index event of the seed-direction block carries mass
`1 / m` under the uniform law, because the retained seed is uniform and its
`m` coordinate-index fibers are equal. Blueprint
`lem:restricted-line-mixture-bounds`, paper
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:1049-1051`. -/
theorem ldSeedDirEvent_mass (L : _root_.MIPStarRE.QPBT.LdParams) (i : Fin L.m) :
∑ sw ∈ (_root_.LIDT.MIPStarRE.LDT.uniformDistribution
(_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L))).support.filter
(_root_.MIPStarRE.QPBT.ldSeedDirEvent L i),
(_root_.LIDT.MIPStarRE.LDT.uniformDistribution
(_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L))).weight sw =
1 / (L.m : ℝ) := by
classical
have hmap : (_root_.LIDT.MIPStarRE.LDT.uniformDistribution
(_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L))).map
(fun sw => _root_.MIPStarRE.QPBT.chiIndex L sw.1) = _root_.LIDT.MIPStarRE.LDT.uniformDistribution (Fin L.m) := by
rw [← _root_.MIPStarRE.QPBT.Distribution.map_map _ Prod.fst (_root_.MIPStarRE.QPBT.chiIndex L),
_root_.MIPStarRE.QPBT.uniformDistribution_map_fst, _root_.MIPStarRE.QPBT.uniformDistribution_map_chiIndex]
rw [_root_.MIPStarRE.QPBT.Distribution.sum_filter_weight_eq_avgOver,
show (fun sw : _root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) =>
if _root_.MIPStarRE.QPBT.ldSeedDirEvent L i sw then (1 : ℝ) else 0) =
fun sw => (fun j : Fin L.m => if j = i then (1 : ℝ) else 0)
(_root_.MIPStarRE.QPBT.chiIndex L sw.1) from rfl,
← _root_.LIDT.MIPStarRE.LDT.Distribution.avgOver_map
(_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)))
(fun sw => _root_.MIPStarRE.QPBT.chiIndex L sw.1)
(fun j : Fin L.m => if j = i then (1 : ℝ) else 0), hmap]
unfold _root_.LIDT.MIPStarRE.LDT.avgOver
simp [_root_.MIPStarRE.QPBT.uniformDistribution_weight_apply, mul_ite]
/-- Every coordinate-index event of the seed-direction block has positive
mass. Blueprint `def:ith-restricted-line`, paper
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:1038-1048`. -/
theorem ldSeedDirEvent_positive (L : _root_.MIPStarRE.QPBT.LdParams) (i : Fin L.m) :
0 < ∑ sw ∈ (_root_.LIDT.MIPStarRE.LDT.uniformDistribution
(_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L))).support.filter
(_root_.MIPStarRE.QPBT.ldSeedDirEvent L i),
(_root_.LIDT.MIPStarRE.LDT.uniformDistribution
(_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L))).weight sw := by
rw [_root_.MIPStarRE.QPBT.ldSeedDirEvent_mass]
have hm : (0 : ℝ) < (L.m : ℝ) := by
exact_mod_cast lt_of_lt_of_le Nat.zero_lt_one L.hm
positivity
/-! ## Fresh diagonal direction pairs -/
/-- The fresh diagonal direction pair at coordinate index `i`: a scalar seed
uniform in the fiber of `i` together with a direction block uniform on the
whole space. This is the auxiliary randomness of the sampling procedure of
blueprint `lem:qld-sublines`, paper
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:1063-1116`. -/
noncomputable def freshDiagonalPairDist (L : _root_.MIPStarRE.QPBT.LdParams) (i : Fin L.m) :
_root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) :=
_root_.MIPStarRE.QPBT.Distribution.restrict
(_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)))
(_root_.MIPStarRE.QPBT.ldSeedDirEvent L i) (_root_.MIPStarRE.QPBT.ldSeedDirEvent_positive L i)
/-! ## Independence of the point block under the coordinate-index event -/
/-! ## Generating form of the restricted line-point laws -/
/-- The axis-line decoder read on the block decomposition. -/
def aLineDescOfBlock (L : _root_.MIPStarRE.QPBT.LdParams)
(w : (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) × (_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L))) :
_root_.MIPStarRE.QPBT.LineDesc L :=
_root_.MIPStarRE.QPBT.aLineDescOf L ((_root_.MIPStarRE.QPBT.ldSpaceBlockEquiv L).symm w)
/-- The diagonal-line decoder read on the block decomposition. -/
def dLineDescOfBlock (L : _root_.MIPStarRE.QPBT.LdParams)
(w : (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) × (_root_.MIPStarRE.QPBT.ScalarQ L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L))) :
_root_.MIPStarRE.QPBT.LineDesc L :=
_root_.MIPStarRE.QPBT.dLineDescOf L ((_root_.MIPStarRE.QPBT.ldSpaceBlockEquiv L).symm w)
end
end MIPStarRE.QPBT
Source