§1: finite-index stabilizer and polynomial-size lattice basis
OpenQAlgorithms.Papers.Independent.Intakethird100.P03.stabilizer_latticeLet , let have unique encodings, let be a action on , and let . No membership test for is required, and the black box is unrestricted off . Write . There is a single polynomial independent of all these data such that
for some integer basis of . Size uses a fixed signed binary, self-delimiting coordinate coding. In particular, the index is finite and nonzero.
This bounds the output size of the stabilizer problem without assuming a basis as input.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
noncomputable section
open scoped Matrix ComplexConjugate Kronecker
namespace QAlgorithms.Papers.Independent.Intakethird100.P03
open QAlgorithms.Papers.Independent.Renew46.P01 (cleanVector)
attribute [local instance] Classical.propDecidable
/-- PDF pp.3–4, §1: finite-index, full-rank stabilizer and a polynomial-bit-size basis.
The polynomial precedes every size, action and encoded point. -/
theorem stabilizer_lattice :
∃ p : Polynomial ℕ, ∀ (k n : ℕ), 0 < k → 0 < n →
∀ (M : Set (Qubits n)) (A : ASPAction k n M) (a : Qubits n) (ha : a ∈ M),
(stabilizer A a ha).FiniteIndex ∧
(stabilizer A a ha).index ≤ Nat.card M ∧ Nat.card M ≤ 2 ^ n ∧
∃ b : (Fin k → ℤ) ≃+ stabilizer A a ha, latticeBasisBits b ≤ p.eval (n + k) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exists a single polynomial with natural-number coefficients such that, for every pair of positive natural numbers , every set , every total map satisfying preservation of , , and for all and , and every point , the subgroup has finite index and satisfies . Moreover, there exists an additive group isomorphism such that , where is the th standard coordinate vector. The polynomial is independent of , the action, and ; no cases with or are asserted, and the hypothesis makes nonempty.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.