Finite signed Clifford monomial groups: a polylogarithmic ideal QFT
OpenQAlgorithms.Papers.Independent.Intakenext100.P78.clifford_qftLet and let be the finite group of signed monomials in involutions , with central sign and for . Its order is . Encode a group element as . Fix the explicit adapted representation coordinates: all linear characters, together with one nonlinear representation of dimension at even rank, or two of dimension at odd rank. In the nonlinear sectors the successive generators have tensor forms and , with identity factors after the indicated position; at odd rank the last generator is .
There exist absolute and such that, for every , a single clean ideal one- and two-qubit circuit has at most
gates and, for every satisfying , outputs the Fourier amplitudes
The circuit is independent of . Since , 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.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P78
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exist a real constant and a natural number such that, for every natural number , there exist a natural number and a finite circuit on Boolean wires, using arbitrary unitary gates of arity one or two applied to injectively selected wires, whose number of gate applications satisfies , and which has the following exact action. Put , let for false and for true, and write . The input labels are all pairs of a Boolean and a length- Boolean string. The output labels form the disjoint union of length- Boolean strings and triples , where have length and satisfies or . Let denote the most-significant-bit-first -bit encoding of , and set
For every complex-valued function on the input labels satisfying , the circuit matrix satisfies
where has coordinate at and zero elsewhere, , , , and
In Boolean order false, true, put , , and ; for , with , set , and for set . The decreasing product places the largest selected index on the left, and empty matrix and scalar products are the identity and , respectively. Each gate matrix is extended to the wires by giving entry zero between strings differing outside its selected wires, and otherwise using its entry on those wires; is the product of these extended matrices with the last listed gate on the left, or the identity for an empty circuit.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.