Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§7, unnumbered: column reduction operation count

Open
QAlgorithms.Papers.Independent.Intakethird100.P85.columnOperation_bound

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Count each one-/two-level X,H,T,ωX,H,T,\omegaX,H,T,ω as one operation. There is an absolute constant C>0C>0C>0 with all the following properties. For every pair satisfying Lemma 4 at a valid exponent k>0k>0k>0, the selected row word lowers the exponent and has at most CCC letters. For every unit column u∈D[ω]du\in\mathbb D[\omega]^du∈D[ω]d, d>0d>0d>0, at a valid exponent k>0k>0k>0, there are a single-pass word PPP and a complete-reduction word WWW, recorded by the column proof's traces, such that

(2)k−1Pu∈Z[ω]d,∣P∣≤Cd,Wu=e1,∣W∣≤Cdk.(\sqrt2)^{k-1}Pu\in\mathbb Z[\omega]^d,\quad |P|\le Cd, \qquad Wu=e_1,\quad |W|\le Cdk.(2​)k−1Pu∈Z[ω]d,∣P∣≤Cd,Wu=e1​,∣W∣≤Cdk.

The same constant works for all dimensions, exponents and input columns. Word lengths are actual output counts; the statement makes no arithmetic runtime claim. It quantifies the size of the column reduction used in synthesis.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P85

open scoped Classical BigOperators

open QAlgorithms

open QAlgorithms.Papers.Independent.Gap48.P10
  (InZomega InDomega Residue bits residue residueMultiply Reducible)

open QAlgorithms.Papers.Independent.Support21.P13
  (synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)

local notation "omega" => QAlgorithms.gateT true true

local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)

/-- Section 7, PDF p.6: uniform row, one-pass, and complete-column output bounds.
The positive-exponent domain excludes the nontrivial exponent-zero base-case cost. -/
theorem columnOperation_bound :
    ∃ C : ℕ, 0 < C ∧
    (∀ (u : Bool → ℂ) (k : ℕ), (∀ b, InDomega (u b)) → 0 < k →
      VectorExponent u k →
      residueNorm (kResidue (u false) k) = residueNorm (kResidue (u true) k) →
      VectorExponent ((htWordMatrix (rowWord u k)).mulVec u) (k - 1) ∧
        (rowWord u k).length ≤ C) ∧
    (∀ (d : ℕ) (u : Fin d → ℂ) (k : ℕ), 0 < d → 0 < k →
      (∀ i, InDomega (u i)) → vectorNormSq u = 1 → VectorExponent u k →
      ∃ w : List (LevelOp d), PassTrace k u w ∧
        VectorExponent ((levelWordMatrix w).mulVec u) (k - 1) ∧ w.length ≤ C * d) ∧
    (∀ (d : ℕ) (hd : 0 < d) (u : Fin d → ℂ) (k : ℕ), 0 < k →
      (∀ i, InDomega (u i)) → vectorNormSq u = 1 → VectorExponent u k →
      ∃ w : List (LevelOp d), ColumnTrace ⟨0, hd⟩ u k w ∧
        (levelWordMatrix w).mulVec u = (fun i => if i = (⟨0, hd⟩ : Fin d) then 1 else 0) ∧
        w.length ≤ C * d * k) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P85

end
Source
Exact synthesis of multiqubit Clifford+T circuits, arXiv:1212.0506v3, PDF p. 6, §7, unnumbered: column reduction operation count
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

Let ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4, O={a0ω3+a1ω2+a2ω+a3:aj∈Z}\mathcal O=\{a_0\omega^3+a_1\omega^2+a_2\omega+a_3:a_j\in\mathbb Z\}O={a0​ω3+a1​ω2+a2​ω+a3​:aj​∈Z}, and D={z∈C:∃h∈N, 2hz∈O}\mathcal D=\{z\in\mathbb C:\exists h\in\mathbb N,\ 2^h z\in\mathcal O\}D={z∈C:∃h∈N, 2hz∈O}. Let sss denote the supplied complex constant sqrtTwo, whose defining equation is not supplied, and say that a vector vvv has exponent q∈Nq\in\mathbb Nq∈N when sqvi∈Os^qv_i\in\mathcal Osqvi​∈O for every coordinate iii. For z∈Oz\in\mathcal Oz∈O, let ρ(z)\rho(z)ρ(z) be its chosen coefficient quadruple modulo 222, and put ρ(z)=0\rho(z)=0ρ(z)=0 for z∉Oz\notin\mathcal Oz∈/O. For quadruples over F2\mathbb F_2F2​, define B(n)j=⌊n/23−j⌋ mod 2B(n)_j=\lfloor n/2^{3-j}\rfloor\bmod2B(n)j​=⌊n/23−j⌋mod2, (a∗b)ℓ=∑i+j≡ℓ+3(mod4)aibj(a*b)_\ell=\sum_{i+j\equiv\ell+3\pmod4}a_i b_j(a∗b)ℓ​=∑i+j≡ℓ+3(mod4)​ai​bj​, with 0≤i,j<40\le i,j<40≤i,j<4, and N(x)=(x2,x1,x0,x3)∗xN(x)=(x_2,x_1,x_0,x_3)*xN(x)=(x2​,x1​,x0​,x3​)∗x; call xxx reducible when B(10)∗y=xB(10)*y=xB(10)∗y=x for some quadruple yyy. Set X=(0110)X=\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)X=(01​10​), H=2−1/2(111−1)H=2^{-1/2}\left(\begin{smallmatrix}1&1\\1&-1\end{smallmatrix}\right)H=2−1/2(11​1−1​), and T=diag⁡(1,ω)T=\operatorname{diag}(1,\omega)T=diag(1,ω), and let WWW of any operation word be its matrix product in reverse word order, with the empty word giving III. Define R(v,q)R(v,q)R(v,q) for a two-component vector vvv to be the first H,TH,TH,T-word in the ordered candidate list consisting of the empty word, then TmHT^mHTmH as words for m=0,…,7m=0,\ldots,7m=0,…,7, then all concatenations of two such words in nested increasing order of their indices, whose matrix sends vvv to a vector of exponent q−1q-1q−1; use the empty word if no candidate succeeds. Here the notation TmHT^mHTmH describes mmm successive TTT letters followed by one HHH letter, so its matrix is HTmHT^mHTm, and subtraction of natural numbers is truncated at zero. On ddd coordinates, permitted level operations apply X,H,TX,H,TX,H,T to an ordered pair of distinct coordinates, identically elsewhere, or multiply a single coordinate by ω\omegaω; lifting an H,TH,TH,T-word to j,ℓj,\ellj,ℓ uses those two coordinates in that order. A pass trace at exponent qqq starts from a vector vvv and is any finite derivation using these rules: it may stop with the empty word if every ρ(sqvi)\rho(s^qv_i)ρ(sqvi​) is reducible; otherwise it may choose distinct j,ℓj,\ellj,ℓ with ρ(sqvj)\rho(s^qv_j)ρ(sqvj​) not reducible and N(ρ(sqvj))=N(ρ(sqvℓ))N(\rho(s^qv_j))=N(\rho(s^qv_\ell))N(ρ(sqvj​))=N(ρ(sqvℓ​)), apply the lift of R((vj,vℓ),q)R((v_j,v_\ell),q)R((vj​,vℓ​),q), and continue with a pass trace at the same exponent from the resulting vector, concatenating the words. A column trace with target coordinate fff has the following recursive rules: at exponent zero its input must be vi=ω8−mv_i=\omega^{8-m}vi​=ω8−m for i=ji=ji=j and zero otherwise, for some coordinate jjj and m∈{0,…,7}m\in\{0,\ldots,7\}m∈{0,…,7}, and its word swaps f,jf,jf,j using XXX if they differ and then applies mmm single-coordinate ω\omegaω-phases at fff; at exponent q+1q+1q+1, it concatenates a pass trace at exponent q+1q+1q+1 with a column trace at exponent qqq from the resulting vector. There exists a positive natural number CCC, common to all the following assertions: for every u∈C2u\in\mathbb C^2u∈C2 with components in D\mathcal DD, and every positive kkk for which uuu has exponent kkk and N(ρ(skufalse))=N(ρ(skutrue))N(\rho(s^ku_{\mathrm{false}}))=N(\rho(s^ku_{\mathrm{true}}))N(ρ(skufalse​))=N(ρ(skutrue​)), the vector W(R(u,k))uW(R(u,k))uW(R(u,k))u has exponent k−1k-1k−1 and ∣R(u,k)∣≤C|R(u,k)|\le C∣R(u,k)∣≤C; for every positive d,kd,kd,k and every u∈Ddu\in\mathcal D^du∈Dd with ∑i∣ui∣2=1\sum_i|u_i|^2=1∑i​∣ui​∣2=1 and exponent kkk, there exists a level-operation word www with a pass trace at exponent kkk from uuu, such that W(w)uW(w)uW(w)u has exponent k−1k-1k−1 and ∣w∣≤Cd|w|\le Cd∣w∣≤Cd; and for every positive d,kd,kd,k and every such normalized vector uuu of exponent kkk, there exists a word www with a column trace targeting coordinate zero from uuu at exponent kkk, such that W(w)u=e0W(w)u=e_0W(w)u=e0​ and ∣w∣≤Cdk|w|\le Cdk∣w∣≤Cdk, where (e0)i=1(e_0)_i=1(e0​)i​=1 at i=0i=0i=0 and is zero otherwise. The first assertion imposes no normalization assumption; all three assertions exclude k=0k=0k=0, and the latter two exclude d=0d=0d=0.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me