QPBT definitions: Algebra / Subspaces
DefinitionQPBT_QPBT_Algebra_Subspacesqpbt
This bundle defines coordinate subspaces and canonical complements for finite-dimensional register spaces. It provides prefix restrictions and ranks, characterizes pivot and non-pivot coordinates, and constructs the projector onto the canonical coordinate complement of a subspace.
Principal definitions:
MIPStarRE.QPBT.registerSubmodule: the span of standard coordinate vectors indexed by a set.MIPStarRE.QPBT.prefixMap: restricts a coordinate vector to an initial prefix.MIPStarRE.QPBT.prefixRank: the rank of a prefix restriction.MIPStarRE.QPBT.canonicalComplement: the non-pivot coordinate set determined by rank increase.MIPStarRE.QPBT.canonicalProjOfKernel: the projector onto the canonical complement along the subspace.MIPStarRE.QPBT.registerSubmodule_eq_spanSubset: identifies the register submodule with its standard coordinate span.MIPStarRE.QPBT.prefixRank_mono_succ: monotonicity of prefix rank when coordinates are added.MIPStarRE.QPBT.coordinate_eq_zero_of_prefixRank_eq: vanishing of a non-rank-increasing coordinate after earlier coordinates.
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/Subspaces.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 Mathlib
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-!
# Subspaces for the Pauli basis test
This module supplies the register subspaces, dot-product orthogonals, and the
canonical coordinate complement used by the conditionally linear maps. The
canonical complement is presented through the intrinsic pivot-rank test; the
equivalence with a particular row-reduced-echelon implementation is a later
construction theorem.
## References
The statement-level definitions are blueprint `def:register-subspace`,
`def:dot-product-orthogonal`, `def:canonical-complement`, and
`def:cl-canonical`;
the paper origin is `references/qpbt-paper/04_preliminaries.tex:231-384`.
Note: this module contributes declarations to the comparator statement closure
of the QPBT headline theorems, which must elaborate in the same environment as
the Mathlib-only `ChallengeQPBT.lean`. Keep the full `import Mathlib`; do not
narrow it. See `docs/comparator.md`, "Environment alignment".
-/
@[expose] public section
open scoped BigOperators
namespace MIPStarRE.QPBT
variable {K ι : Type*} [Field K] [Fintype ι] [DecidableEq ι]
/--
`registerSubmodule K S` is the span of the standard coordinate vectors indexed
by `S`. It is the Lean encoding of blueprint `def:register-subspace`, whose
paper origin is
`references/qpbt-paper/04_preliminaries.tex:231-239`.
-/
def registerSubmodule (K : Type*) [Field K] (S : Finset ι) : Submodule K (ι → K) :=
Submodule.span K {v | ∃ i, i ∈ S ∧ v = Pi.single i 1}
/-- Restrict a coordinate vector to the first `k` coordinates. Lean-only rank
infrastructure for blueprint
`def:canonical-complement`, paper `references/qpbt-paper/04_preliminaries.tex:231-384`.
-/
def prefixMap (k n : ℕ) (hk : k ≤ n) :
(Fin n → K) →ₗ[K] (Fin k → K) :=
{ toFun := fun x i => x ⟨i.1, lt_of_lt_of_le i.2 hk⟩
map_add' := by
intro x y
rfl
map_smul' := by
intro c x
rfl }
/-- The rank of a prefix restriction used by the pivot characterization. -/
noncomputable def prefixRank {n : ℕ} (W : Submodule K (Fin n → K))
(k : ℕ) (hk : k ≤ n) : ℕ :=
Module.finrank K (W.map (_root_.MIPStarRE.QPBT.prefixMap k n hk))
/--
The non-pivot coordinate set of `W`, defined by the rank-increase
characterization of pivots. This is the basis-free encoding approved for
blueprint `def:canonical-complement`;
the paper's Gaussian-elimination presentation is
`references/qpbt-paper/04_preliminaries.tex:303-320`.
-/
noncomputable def canonicalComplement {n : ℕ}
(W : Submodule K (Fin n → K)) : Finset (Fin n) :=
Finset.univ.filter fun j =>
_root_.MIPStarRE.QPBT.prefixRank W (j.1 + 1) (Nat.succ_le_of_lt j.2) =
_root_.MIPStarRE.QPBT.prefixRank W j.1 j.2.le
/-- The register submodule is the standard coordinate span on its index set. -/
lemma registerSubmodule_eq_spanSubset (S : Finset ι) :
_root_.MIPStarRE.QPBT.registerSubmodule K S = Pi.spanSubset K (S : Set ι) := by
classical
rw [_root_.MIPStarRE.QPBT.registerSubmodule, Pi.spanSubset]
congr 1
ext v
simp [Pi.basisFun_apply, eq_comm]
/-- Prefix restriction rank is nondecreasing when one coordinate is added. -/
lemma prefixRank_mono_succ {n : ℕ} (W : Submodule K (Fin n → K))
(k : ℕ) (hk : k + 1 ≤ n) :
_root_.MIPStarRE.QPBT.prefixRank W k (Nat.le_trans (Nat.le_succ k) hk) ≤
_root_.MIPStarRE.QPBT.prefixRank W (k + 1) hk := by
let drop := _root_.MIPStarRE.QPBT.prefixMap (K := K) k (k + 1) (Nat.le_succ k)
let large := _root_.MIPStarRE.QPBT.prefixMap (K := K) (k + 1) n hk
have hcomp : drop.comp large =
_root_.MIPStarRE.QPBT.prefixMap (K := K) k n (Nat.le_trans (Nat.le_succ k) hk) := by
ext x i
rfl
rw [_root_.MIPStarRE.QPBT.prefixRank, _root_.MIPStarRE.QPBT.prefixRank, ← hcomp, Submodule.map_comp]
exact Submodule.finrank_map_le drop (W.map large)
/-- If a coordinate does not increase prefix rank, it vanishes after all earlier coordinates do. -/
lemma coordinate_eq_zero_of_prefixRank_eq {n : ℕ}
(W : Submodule K (Fin n → K)) (j : Fin n)
(hrank : _root_.MIPStarRE.QPBT.prefixRank W (j.1 + 1) (Nat.succ_le_of_lt j.2) =
_root_.MIPStarRE.QPBT.prefixRank W j.1 j.2.le) {w : Fin n → K} (hw : w ∈ W)
(hprevious : ∀ i : Fin n, i.1 < j.1 → w i = 0) :
w j = 0 := by
let small : W →ₗ[K] (Fin j.1 → K) :=
(_root_.MIPStarRE.QPBT.prefixMap (K := K) j.1 n j.2.le).domRestrict W
let large : W →ₗ[K] (Fin (j.1 + 1) → K) :=
(_root_.MIPStarRE.QPBT.prefixMap (K := K) (j.1 + 1) n
(Nat.succ_le_of_lt j.2)).domRestrict W
have hker_le : LinearMap.ker large ≤ LinearMap.ker small := by
intro x hx
rw [LinearMap.mem_ker] at hx ⊢
funext i
have hi := congrFun hx (Fin.castSucc i)
simpa [small, large, _root_.MIPStarRE.QPBT.prefixMap] using hi
have hrange : Module.finrank K (LinearMap.range large) =
Module.finrank K (LinearMap.range small) := by
dsimp [small, large]
rw [LinearMap.range_domRestrict, LinearMap.range_domRestrict]
exact hrank
have hlarge := large.finrank_range_add_finrank_ker
have hsmall := small.finrank_range_add_finrank_ker
have hker_rank : Module.finrank K (LinearMap.ker large) =
Module.finrank K (LinearMap.ker small) := by
omega
have hker_eq : LinearMap.ker large = LinearMap.ker small :=
Submodule.eq_of_le_of_finrank_eq hker_le hker_rank
let x : W := ⟨w, hw⟩
have hxsmall : x ∈ LinearMap.ker small := by
rw [LinearMap.mem_ker]
funext i
exact hprevious ⟨i.1, lt_of_lt_of_le i.2 j.2.le⟩ i.2
have hxlarge : x ∈ LinearMap.ker large := by
rw [hker_eq]
exact hxsmall
have hj := congrFun (LinearMap.mem_ker.mp hxlarge) (Fin.last j.1)
simpa [x, large, _root_.MIPStarRE.QPBT.prefixMap] using hj
/-- The number of strict steps in a nondecreasing natural-number sequence is at
most its endpoint. -/
lemma card_strict_steps_le {n : ℕ} (r : ℕ → ℕ)
(hmono : ∀ k, k < n → r k ≤ r (k + 1)) :
((Finset.range n).filter fun k => r (k + 1) ≠ r k).card ≤ r n := by
classical
induction n with
| zero => simp
| succ n ih =>
have hih := ih fun k hk => hmono k (lt_trans hk (Nat.lt_succ_self n))
have hn := hmono n (Nat.lt_succ_self n)
by_cases h : r n = r (n + 1)
· simpa [Finset.range_add_one, Finset.filter_insert, h] using hih.trans hn
· have hstep : r n < r (n + 1) := lt_of_le_of_ne hn h
have h' : r (n + 1) ≠ r n := Ne.symm h
have := Nat.succ_le_of_lt (hih.trans_lt hstep)
simpa [Finset.range_add_one, Finset.filter_insert, h'] using this
/--
The canonical coordinate complement spans a complement of `W`. This is the
proposition blueprint
`lem:canonical-complement`, with paper origin
`references/qpbt-paper/04_preliminaries.tex:342-373`.
The proof uses the intrinsic prefix-rank characterization; equivalence with a
particular reduced-row-echelon algorithm is outside this statement.
-/
theorem isCompl_registerSubmodule_canonicalComplement {n : ℕ}
(W : Submodule K (Fin n → K)) :
IsCompl W (_root_.MIPStarRE.QPBT.registerSubmodule K (_root_.MIPStarRE.QPBT.canonicalComplement W)) := by
classical
let C := _root_.MIPStarRE.QPBT.canonicalComplement W
let T := _root_.MIPStarRE.QPBT.registerSubmodule K C
change IsCompl W T
have hT : T = Pi.spanSubset K (C : Set (Fin n)) :=
_root_.MIPStarRE.QPBT.registerSubmodule_eq_spanSubset C
have hdisjoint : Disjoint W T := by
refine Submodule.disjoint_def.mpr ?_
intro w hwW hwT
rw [hT] at hwT
have hzero : ∀ k (hk : k < n), w ⟨k, hk⟩ = 0 := by
intro k
induction k using Nat.strong_induction_on with
| h k ih =>
intro hk
let j : Fin n := ⟨k, hk⟩
by_cases hj : j ∈ C
· apply _root_.MIPStarRE.QPBT.coordinate_eq_zero_of_prefixRank_eq W j
· simpa [C, _root_.MIPStarRE.QPBT.canonicalComplement] using hj
· exact hwW
· intro i hi
simpa using ih i.1 hi i.2
· exact Pi.mem_spanSubset_iff.mp hwT j hj
funext j
exact hzero j.1 j.2
let P := Cᶜ
let r : ℕ → ℕ := fun k =>
if hk : k ≤ n then _root_.MIPStarRE.QPBT.prefixRank W k hk else 0
have hr_mono : ∀ k, k < n → r k ≤ r (k + 1) := by
intro k hk
simp only [r, dif_pos (Nat.le_of_lt hk), dif_pos (Nat.succ_le_of_lt hk)]
exact _root_.MIPStarRE.QPBT.prefixRank_mono_succ W k (Nat.succ_le_of_lt hk)
have hP_filter : P = Finset.univ.filter fun j =>
_root_.MIPStarRE.QPBT.prefixRank W (j.1 + 1) (Nat.succ_le_of_lt j.2) ≠
_root_.MIPStarRE.QPBT.prefixRank W j.1 j.2.le := by
ext j
simp [P, C, _root_.MIPStarRE.QPBT.canonicalComplement]
have hP_card : P.card =
((Finset.range n).filter fun k => r (k + 1) ≠ r k).card := by
rw [← Finset.card_map Fin.valEmbedding]
congr 1
ext k
simp only [Finset.mem_map, Finset.mem_filter, Finset.mem_range]
constructor
· rintro ⟨j, hj, rfl⟩
rw [hP_filter] at hj
simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hj
refine ⟨j.2, ?_⟩
simpa [r, Nat.le_of_lt j.2, Nat.succ_le_of_lt j.2] using hj
· rintro ⟨hk, hstrict⟩
let j : Fin n := ⟨k, hk⟩
refine ⟨j, ?_, rfl⟩
rw [hP_filter]
simp only [Finset.mem_filter, Finset.mem_univ, true_and]
simpa [j, r, Nat.le_of_lt hk, Nat.succ_le_of_lt hk] using hstrict
have hP_le : P.card ≤ Module.finrank K W := by
calc
P.card ≤ r n := by
rw [hP_card]
exact _root_.MIPStarRE.QPBT.card_strict_steps_le r hr_mono
_ ≤ Module.finrank K W := by
simp only [r, dif_pos le_rfl]
exact Submodule.finrank_map_le (_root_.MIPStarRE.QPBT.prefixMap (K := K) n n le_rfl) W
have hfinrankT : Module.finrank K T = C.card := by
rw [hT, Pi.dim_spanSubset]
simp
have hpartition : C.card + P.card = n := by
simpa only [P, Fintype.card_fin] using Finset.card_add_card_compl C
have hdim : Module.finrank K (Fin n → K) ≤
Module.finrank K W + Module.finrank K T := by
rw [hfinrankT]
simp only [Module.finrank_fin_fun]
omega
exact (Submodule.isCompl_iff_disjoint W T hdim).mpr hdisjoint
/--
The projector onto the canonical coordinate complement along `W`. This is
blueprint `def:cl-canonical`,
originating at `references/qpbt-paper/04_preliminaries.tex:375-384`.
-/
noncomputable def canonicalProjOfKernel {n : ℕ}
(W : Submodule K (Fin n → K)) : (Fin n → K) →ₗ[K] (Fin n → K) := by
let T := _root_.MIPStarRE.QPBT.registerSubmodule K (_root_.MIPStarRE.QPBT.canonicalComplement W)
let p : (Fin n → K) →ₗ[K] T :=
Submodule.projectionOnto T W
(_root_.MIPStarRE.QPBT.isCompl_registerSubmodule_canonicalComplement W).symm
exact T.subtype.comp p
end MIPStarRE.QPBT
Source