QPBT definitions: Algebra / LowDegreeCodeTheorems
DefinitionQPBT_QPBT_Algebra_LowDegreeCodeTheoremsqpbt
This bundle defines the Boolean-cube embedding and decoding map for low-degree encodings. It embeds Boolean coordinates into the fixed field, evaluates indicator polynomials on the cube, and proves that decoding an embedded point recovers the corresponding coefficient.
Principal definitions:
MIPStarRE.QPBT.boolToScalar: embeds a Boolean coordinate into the scalar field.MIPStarRE.QPBT.cubeEmbed: embeds a Boolean cube point coordinatewise.MIPStarRE.QPBT.decodeAt: evaluates the low-degree decoding map at a point.MIPStarRE.QPBT.decodeAt_lowDegreeEnc: the decoding identity for a low-degree encoding.MIPStarRE.QPBT.eval_indicatorPoly_cubeEmbed: evaluates an indicator polynomial as a Kronecker on the Boolean cube.MIPStarRE.QPBT.lowDegreeEnc_cubeEmbed: recovers the encoding coefficient at an embedded Boolean point.
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/Algebra/LowDegreeCodeTheorems.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_LowDegreeCode
import Mathlib
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.LDT.Preliminaries
end LIDT.MIPStarRE.LDT.Preliminaries
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-! # Decoding maps for the low-degree code
This file supplies `def:decoding-map` and the Boolean cube embedding from
`def:decoding-map`, paper
`references/qpbt-paper/04_preliminaries.tex:917-924`. The specialization to
polynomial representatives is `decodeFqRep`; its restriction to the bounded
class `Poly` is defined in `Algebra/Decoding`.
-/
@[expose] public section
open scoped BigOperators
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT LIDT.MIPStarRE.LDT.Preliminaries
/-- The formalization-only embedding of Boolean coordinates into a field used by
blueprint `def:decoding-map`, paper
`04_preliminaries.tex:917-924`. -/
def boolToScalar {K : Type*} [Field K] : Bool → K
| false => 0
| true => 1
/-- The coordinatewise Boolean-cube embedding used by
blueprint `def:decoding-map`, paper
`04_preliminaries.tex:917-924`. -/
def cubeEmbed {K : Type*} [Field K] {m : ℕ} : _root_.MIPStarRE.QPBT.Cube m → (Fin m → K) :=
fun y i => _root_.MIPStarRE.QPBT.boolToScalar (y i)
/-- On the Boolean cube, an indicator polynomial evaluates to the corresponding
Kronecker delta. This is the interpolation observation at paper lines 880-891. -/
private theorem eval_indicatorPoly_cubeEmbed {K : Type*} [Field K] {m : ℕ}
(y z : _root_.MIPStarRE.QPBT.Cube m) :
MvPolynomial.eval (_root_.MIPStarRE.QPBT.cubeEmbed (K := K) z) (_root_.MIPStarRE.QPBT.indicatorPoly (K := K) y) =
if y = z then 1 else 0 := by
classical
rw [_root_.MIPStarRE.QPBT.indicatorPoly, MvPolynomial.eval_prod]
simp only [apply_ite, MvPolynomial.eval_X, MvPolynomial.eval_sub, map_one]
have hfactor (i : Fin m) :
(if y i then _root_.MIPStarRE.QPBT.cubeEmbed (K := K) z i else 1 - _root_.MIPStarRE.QPBT.cubeEmbed (K := K) z i) =
if y i = z i then 1 else 0 := by
cases hy : y i <;> cases hz : z i <;> simp_all [_root_.MIPStarRE.QPBT.cubeEmbed, _root_.MIPStarRE.QPBT.boolToScalar]
simp_rw [hfactor]
rw [Fintype.prod_boole]
split_ifs <;> simp_all [funext_iff]
/-- Evaluating a low-degree encoding at an embedded Boolean point recovers its
coefficient at that point, as stated at paper line 891. -/
private theorem lowDegreeEnc_cubeEmbed {K : Type*} [Field K] {m : ℕ}
(a : _root_.MIPStarRE.QPBT.Cube m → K) (z : _root_.MIPStarRE.QPBT.Cube m) :
_root_.MIPStarRE.QPBT.lowDegreeEnc a (_root_.MIPStarRE.QPBT.cubeEmbed z) = a z := by
rw [_root_.MIPStarRE.QPBT.lowDegreeEnc_eq_dotProduct]
simp [dotProduct, _root_.MIPStarRE.QPBT.indicatorVec, eval_indicatorPoly_cubeEmbed]
/-- The decoding map blueprint
`def:decoding-map`, paper `04_preliminaries.tex:917-924`. -/
noncomputable def decodeAt {K : Type*} [Field K] [DecidableEq K] {m : ℕ}
(H : Finset K) (g : (Fin m → K) → K) : _root_.MIPStarRE.QPBT.Cube m → K :=
fun y => if g (_root_.MIPStarRE.QPBT.cubeEmbed y) ∈ H then g (_root_.MIPStarRE.QPBT.cubeEmbed y) else 0
/-- The restricted decoding identity in blueprint
`def:decoding-map`, paper `04_preliminaries.tex:917-924`. -/
theorem decodeAt_lowDegreeEnc {K : Type*} [Field K] [DecidableEq K] {m : ℕ}
(H : Finset K) (a : _root_.MIPStarRE.QPBT.Cube m → K) (ha : ∀ y, a y ∈ H) :
_root_.MIPStarRE.QPBT.decodeAt H (_root_.MIPStarRE.QPBT.lowDegreeEnc a) = a := by
funext y
simp [_root_.MIPStarRE.QPBT.decodeAt, lowDegreeEnc_cubeEmbed, ha y]
end MIPStarRE.QPBT
Source