Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite signed Clifford monomial groups: a polylogarithmic ideal QFT

Open
QAlgorithms.Papers.Independent.Intakenext100.P78.clifford_qft

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let n≥2n\ge2n≥2 and let CLn\mathrm{CL}_nCLn​ be the finite group of signed monomials in involutions x1,…,xnx_1,\ldots,x_nx1​,…,xn​, with central sign −1-1−1 and xixj=−xjxix_ix_j=-x_jx_ixi​xj​=−xj​xi​ for i≠ji\ne ji=j. Its order is 2n+12^{n+1}2n+1. Encode a group element as (−1)sxnun⋯x1u1(-1)^s x_n^{u_n}\cdots x_1^{u_1}(−1)sxnun​​⋯x1u1​​. Fix the explicit adapted representation coordinates: all 2n2^n2n linear characters, together with one nonlinear representation of dimension 2n/22^{n/2}2n/2 at even rank, or two of dimension 2(n−1)/22^{(n-1)/2}2(n−1)/2 at odd rank. In the nonlinear sectors the successive generators have tensor forms Y⊗r⊗ZY^{\otimes r}\otimes ZY⊗r⊗Z and Y⊗r⊗XY^{\otimes r}\otimes XY⊗r⊗X, with identity factors after the indicated position; at odd rank the last generator is ±Y⊗⌊n/2⌋\pm Y^{\otimes\lfloor n/2\rfloor}±Y⊗⌊n/2⌋.

There exist absolute C>0C>0C>0 and k∈Nk\in\mathbb Nk∈N such that, for every n≥2n\ge2n≥2, a single clean ideal one- and two-qubit circuit has at most

C(n+2)kC(n+2)^kC(n+2)k

gates and, for every fff satisfying ∑g∣f(g)∣2=1\sum_g|f(g)|^2=1∑g​∣f(g)∣2=1, outputs the Fourier amplitudes

f^(ρ)i,j=dρ2n+1∑gf(g)ρ(g)i,j.\widehat f(\rho)_{i,j}=\sqrt{\frac{d_\rho}{2^{n+1}}}\sum_g f(g)\rho(g)_{i,j}.f​(ρ)i,j​=2n+1dρ​​​g∑​f(g)ρ(g)i,j​.

The circuit is independent of fff. Since n+2=1+log⁡2∣CLn∣n+2=1+\log_2|\mathrm{CL}_n|n+2=1+log2​∣CLn​∣, this is the source's polylogarithmic gate bound. The central-sign level is present in the encoding; no exact maximum-index assertion at the abbreviated bottom of the printed tower is used.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P78
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P78

open QAlgorithms

attribute [local instance] Classical.propDecidable

/-- PDF p.8, unnumbered finite-Clifford-group application: a family-wide
polylogarithmic ideal QFT bound, since log2|CL_n|=n+1.
Source correction: the printed relation x_i x_j=-x_i x_j is read as
x_i x_j=-x_j x_i, as required by the cited Clifford group and the proof's
centralization of the earlier generators. The central-sign tower level is
included; no literal bottom-index-2 assertion is made. Independent moderation
of this correction is required. -/
theorem clifford_qft :
    ∃ C : ℝ, 0 < C ∧ ∃ k : ℕ, ∀ n : ℕ, 2 ≤ n →
      ∃ q : ℕ, n + 1 ≤ q ∧ ∃ c : Circuit oneTwoQubitGateSet q,
        (c.size : ℝ) ≤ C * ((n + 2 : ℕ) : ℝ) ^ k ∧
        realizesEncodedTransform c (cliffordInputCode n q) (cliffordOutputCode n q)
          cliffordFourier := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P78

end
Source
Generic Quantum Fourier Transforms, arXiv:quant-ph/0304064v1, PDF p. 8, Unnumbered application: finite Clifford monomial groups
Read-back

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

There exist a real constant C>0C>0C>0 and a natural number kkk such that, for every natural number n≥2n\ge2n≥2, there exist a natural number q≥n+1q\ge n+1q≥n+1 and a finite circuit ccc on qqq Boolean wires, using arbitrary unitary gates of arity one or two applied to injectively selected wires, whose number of gate applications satisfies ∣c∣≤C(n+2)k|c|\le C(n+2)^k∣c∣≤C(n+2)k, and which has the following exact action. Put m=⌊n/2⌋m=\lfloor n/2\rfloorm=⌊n/2⌋, let ϵ(t)=1\epsilon(t)=1ϵ(t)=1 for false and −1-1−1 for true, and write Bℓ(z)=∑i=0ℓ−11zi=true2ℓ−1−iB_\ell(z)=\sum_{i=0}^{\ell-1}\mathbf 1_{z_i=\mathrm{true}}2^{\ell-1-i}Bℓ​(z)=∑i=0ℓ−1​1zi​=true​2ℓ−1−i. The input labels are all pairs g=(η,u)g=(\eta,u)g=(η,u) of a Boolean and a length-nnn Boolean string. The output labels form the disjoint union of length-nnn Boolean strings vvv and triples (b,r,s)(b,r,s)(b,r,s), where r,sr,sr,s have length mmm and bbb satisfies n mod 2=1n\bmod2=1nmod2=1 or b=falseb=\mathrm{false}b=false. Let bin⁡q(a)\operatorname{bin}_q(a)binq​(a) denote the most-significant-bit-first qqq-bit encoding of a mod 2qa\bmod2^qamod2q, and set

I(η,u)=bin⁡q ⁣(1η=true2n+Bn(u)),O(y)={bin⁡q(Bn(v)),y=v,bin⁡q ⁣(2n+1b=true22m+Bm(r)2m+Bm(s)),y=(b,r,s).I(\eta,u)=\operatorname{bin}_q\!\left(\mathbf 1_{\eta=\mathrm{true}}2^n+B_n(u)\right),\qquad O(y)= \begin{cases} \operatorname{bin}_q(B_n(v)),&y=v,\\ \operatorname{bin}_q\!\left(2^n+\mathbf 1_{b=\mathrm{true}}2^{2m}+B_m(r)2^m+B_m(s)\right), &y=(b,r,s). \end{cases}I(η,u)=binq​(1η=true​2n+Bn​(u)),O(y)={binq​(Bn​(v)),binq​(2n+1b=true​22m+Bm​(r)2m+Bm​(s)),​y=v,y=(b,r,s).​

For every complex-valued function fff on the input labels satisfying ∑g∣f(g)∣2=1\sum_g|f(g)|^2=1∑g​∣f(g)∣2=1, the circuit matrix UcU_cUc​ satisfies

Uc ⁣(∑gf(g)eI(g))=∑yf^(y)eO(y),f^(y)=dy2n+1∑gf(g)ay(g),U_c\!\left(\sum_g f(g)e_{I(g)}\right) =\sum_y\widehat f(y)e_{O(y)},\qquad \widehat f(y)=\sqrt{\frac{d_y}{2^{n+1}}}\sum_g f(g)a_y(g),Uc​(g∑​f(g)eI(g)​)=y∑​f​(y)eO(y)​,f​(y)=2n+1dy​​​g∑​f(g)ay​(g),

where eze_zez​ has coordinate 111 at zzz and zero elsewhere, dv=1d_v=1dv​=1, d(b,r,s)=2md_{(b,r,s)}=2^md(b,r,s)​=2m, av(η,u)=∏i:ui=trueϵ(vi)a_v(\eta,u)=\prod_{i:u_i=\mathrm{true}}\epsilon(v_i)av​(η,u)=∏i:ui​=true​ϵ(vi​), and

a(b,r,s)(η,u)=ϵ(η)(∏i:ui=truedecreasing iGb,i)r,s.a_{(b,r,s)}(\eta,u)= \epsilon(\eta)\left(\prod_{i:u_i=\mathrm{true}}^{\mathrm{decreasing}\ i}G_{b,i}\right)_{r,s}.a(b,r,s)​(η,u)=ϵ(η)(i:ui​=true∏decreasing i​Gb,i​)r,s​.

In Boolean order false, true, put X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), Y=(0−ii0)Y=\begin{pmatrix}0&-\mathrm{i}\\\mathrm{i}&0\end{pmatrix}Y=(0i​−i0​), and Z=(100−1)Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}Z=(10​0−1​); for i<2mi<2mi<2m, with j=⌊i/2⌋j=\lfloor i/2\rfloorj=⌊i/2⌋, set Gb,i=Y⊗j⊗(Z if i even, else X)⊗I⊗(m−j−1)G_{b,i}=Y^{\otimes j}\otimes(Z\text{ if }i\text{ even, else }X)\otimes I^{\otimes(m-j-1)}Gb,i​=Y⊗j⊗(Z if i even, else X)⊗I⊗(m−j−1), and for i≥2mi\ge2mi≥2m set Gb,i=ϵ(b)Y⊗mG_{b,i}=\epsilon(b)Y^{\otimes m}Gb,i​=ϵ(b)Y⊗m. The decreasing product places the largest selected index on the left, and empty matrix and scalar products are the identity and 111, respectively. Each gate matrix is extended to the qqq wires by giving entry zero between strings differing outside its selected wires, and otherwise using its entry on those wires; UcU_cUc​ is the product of these extended matrices with the last listed gate on the left, or the identity for an empty circuit.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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