Generalized quaternion groups: a polylogarithmic ideal QFT for all n
OpenQAlgorithms.Papers.Independent.Intakenext100.P78.quaternion_qftFor each integer , let , the actual finite group represented by Mathlib's QuaternionGroup. Encode by and by , for . Fix the cyclic-subgroup-adapted dual. It contains four one-dimensional characters: , with the two choices of square root for whose square is . For each , the two-dimensional sector has
There exist absolute and such that, for every , one ideal one- and two-qubit circuit of at most
gates maps every normalized input to the clean Fourier state with amplitudes . The output labels are the four characters and the row/column entries of the two-dimensional sectors, in a fixed binary ordering. This preserves the source's general- application, beyond the power-of-two case cited there. No precision or measurement probability is asserted.
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.10, unnumbered quaternionic application: a polylog(4n)-size ideal
QFT for every finite generalized quaternion/dicyclic group with n>=2,
not just the power-of-two subfamily cited in [21]. Constants precede n,
and the circuit precedes every normalized amplitude function. -/
theorem quaternion_qft :
∃ C : ℝ, 0 < C ∧ ∃ k : ℕ, ∀ n : ℕ, ∀ hn : 2 ≤ n,
letI : NeZero n := ⟨by omega⟩
∃ q : ℕ, Nat.clog 2 (4 * n) ≤ q ∧ ∃ c : Circuit oneTwoQubitGateSet q,
(c.size : ℝ) ≤ C * ((1 + Nat.clog 2 (4 * n) : ℕ) : ℝ) ^ k ∧
realizesEncodedTransform c (quaternionInputCode n q) (quaternionOutputCode n q)
quaternionFourier := 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 circuit on qubits satisfying
Here is a finite list of gate applications, each using an arbitrary unitary matrix on either one or two distinct selected wires, acting as the identity on the other wires; is the length of that list, and its matrix applies the listed gates in order. For every function with , the following vector equality holds:
The vector has amplitude at the -bit string and zero elsewhere. The input encodings of and are the most-significant-bit-first -bit encodings, modulo , of and , respectively. Frequency labels are the disjoint union of Boolean pairs and triples with ; their output encodings are those of and , respectively, where Boolean brackets denote or . The transformed amplitudes are
with on the first summand and on the second. Explicitly, writing , for one has and multiplied by precisely when is true and is odd. For , put , , and for even , otherwise; then
The constants are independent of , the exponent may be zero, and the statement imposes no upper bound on .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.