Symmetric groups: a polynomial-size ideal QFT in Young orthogonal coordinates
OpenQAlgorithms.Papers.Independent.Intakenext100.P78.symmetric_qftFor each , use the point-stabilizer tower of and its transversal products. Fix the Young orthogonal realization: the row and column labels are standard tableaux of the same shape , and is the number of such tableaux. The input encoding records the chosen transversal digits, and the output encoding records the two tableau paths. There are absolute and such that, for every , a single circuit of ideal one- and two-qubit unitaries, chosen before the amplitudes, has at most
gates and maps every normalized input to the clean encoded Fourier state with amplitudes
Here normalized means . Additional wires end in zero, and behavior on invalid binary codes is unconstrained. This gives the paper's polylogarithmic ideal gate bound in the named basis. It asserts neither a numerical synthesis algorithm nor a finite-alphabet approximation guarantee.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P78
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P78
open QAlgorithms
attribute [local instance] Classical.propDecidable
/-- PDF pp.5,8, unnumbered symmetric-group application: the normalized QFT
in the Young orthogonal basis has polylog(|S_n|) ideal elementary gate size.
The same circuit works for all normalized amplitudes; n=0,1 are absorbed
by the finite small-rank convention, and no synthesis/runtime/error claim
is added. The input is the explicit point-stabilizer transversal product. -/
theorem symmetric_qft :
∃ C : ℝ, 0 < C ∧ ∃ k : ℕ, ∀ n : ℕ, 2 ≤ n →
∃ q : ℕ, 4 * n * Nat.clog 2 (n + 1) ≤ q ∧
∃ c : Circuit oneTwoQubitGateSet q,
(c.size : ℝ) ≤ C * ((1 + Nat.clog 2 n.factorial : ℕ) : ℝ) ^ k ∧
realizesEncodedTransform c (symmetricInputCode n q) (symmetricOutputCode n q)
symmetricFourier := 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 , possibly , such that for every natural number , there are a natural number , where is the least nonnegative integer satisfying , and a circuit on bits with
The circuit is a finite list of arbitrary complex unitary gates of arity one or two, each assigned injectively to circuit wires; is its list length. A gate acts by its matrix on the assigned wires and leaves all other bits unchanged, and the circuit matrix applies these embedded gates in list order. Its asserted action is the exact equality
Here is the coordinate vector supported at the bit string ; ranges over integer tuples with ; and is the most-significant-bit-first -bit encoding of , reduced modulo . A frequency consists of a finite set and two injective sequences of boxes, each having downward-closed prefixes in the coordinatewise order and endpoint . The output encoding packs the list : a list represents , again encoded modulo . Writing for the number of paths with endpoint , the output coefficient is
To define , visit levels , append in increasing order, and multiply the matrices in the resulting list order, with empty product the identity. For paths , put if , and otherwise; set , , and . If , then ; otherwise, if , it equals ; otherwise it equals when , when and , and in all remaining cases. Real entries are embedded in , with inverse and real square root on negative arguments. The constants work for all ; no assertion is made for , and no upper bound on or algorithm for choosing the circuits is specified.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.