Definitions for Generic Quantum Fourier Transforms
DefinitionQAlgorithms_Papers_Independent_Intakenext100_P78The objects the formalized statements of Generic Quantum Fourier Transforms (arXiv:quant-ph/0304064) are stated in. Each was checked against the paper by a blind read-back and a moderator.
packDigits: Fixed-length digit packing; no data-dependent choice of binary encoding. Source: PDF p.6, product-coset and path registers.encodedWave: Linear embedding of amplitudes into explicitly named computational codes. Unused wires are zero because every code is a padded binary integer. Source: PDF pp.1–3,6.normalizedAmplitudes: The source's normalization of the entire input, not of each coset piece. Source: PDF pp.1–2 and equation (4), p.6.realizesEncodedTransform: A fixed clean-input/clean-output implementation on every normalized input; the circuit is chosen outside the quantifier over f. Invalid binary strings are unconstrained. Source: Definition 1, p.3, and equations (4)–(5), p.6.SymmetricCosetDigits: The transversal digit at level i+1 specifies the position to which the new letter is moved. This is the point-stabilizer tower of PDF pp.4–5,8.nextIndex: Next letter, with a total harmless value at the unused last position.BoundedYoungPath: A standard tableau is an injective sequence of boxes whose every prefix is a lower ideal. Coordinates are bounded by n; no tableau with n boxes is lost. Source: Bratteli paths, p.4, and Young orthogonal basis, pp.5,8. The concrete convention follows accepted Support21.P07/ Renew46.P26; these paper modules are not imported.youngPathEndpoint: The actual endpoint Young diagram, computed from the path.YoungEndpointPaths: Paths with a fixed endpoint. Unoccupied shapes contribute no rows.SymmetricFrequency: Fourier labels are pairs of paths with the same endpoint, including all diagonal pairs; the endpoint itself is recorded once. Source: PDF pp.4–6.boundedBoxContent: Column minus row, fixing the sign of Young's orthogonal coefficients.youngAdjacent: The Young orthogonal matrix of the adjacent transposition (i,i+1), with row U and column T. Same-row/column cases precede division; the mixed case has positive square root and r=content(i+1)-content(i). Source: named Young orthogonal realization, PDF pp.5,8; coefficient convention is the accepted Support21.P07.youngActionCoefficient, written out locally.symmetricWord: The chosen coset product, largest subgroup first: the level-i factor is s_digit ... s_(i-1). Source: input encoding p.6 and point stabilizers p.8.symmetricElement: The actual permutation specified by the source transversal digits.symmetricMatrix: The representation matrix is computed from that same word, in the fixed Young orthogonal basis, before any implementation is quantified.symmetricFourier: Normalized plus-sign Fourier transform: no conjugation or inverse g. The representation dimension is the number of tableaux of its shape. Source: Definition 1, PDF p.3; symmetric application, pp.5,8.symmetricInputCode: Binary encoding of the chosen transversal digits.tableauDigits: Each tableau is encoded by its successive row/column coordinates. The shape is recoverable from either tableau and is not independently chosen.symmetricOutputCode: Fixed output encoding of the two paths. Extra wires are zero.CliffordElement: Coordinates (-1)^s x_n^u_n ... x_1^u_1, including the central sign. Source: finite Clifford monomial groups, PDF p.8.cliffordCross: The crossing sign for descending monomials: a left x_i crosses a right x_j exactly when i<j. This fixes the actual group law, including -1.cliffordMul: Multiplication of signed ordered monomials.centralSignScalar: Scalar corresponding to a central sign bit.matrixX: Pauli matrices used only to specify the based irreducibles explicitly.matrixY: The Y sign fixes the phase convention of the adapted Clifford rows.matrixZ: The first Clifford generator is diagonal in its adapted row basis.CliffordSector: Even rank has one nonlinear irrep; odd rank has two.cliffordGenerator: The explicit adapted irreducible generators are Y^r Z and Y^r X on successive tensor factors; at odd rank the last is either sign of Y^(tensor m). Thus restriction to the earlier even level repeats literally equal blocks, while the next odd level is selected by the last row bit. Source: p.8.CliffordFrequency: All 2^n linear characters, and all matrix entries of the nonlinear irrep(s). No multiplicity edge is identified with another. Source: p.8.cliffordCoefficient: The based matrix element at an actual signed monomial. The sign acts trivially in the linear characters and as -I in the nonlinear sectors.cliffordDimension: Definition 1's dimension factor for each Clifford Fourier row.cliffordFourier: The source's normalized plus Fourier transform of the signed monomial coordinates, whose group order is 2^(n+1). Source: PDF pp.3,8.cliffordInputCode: Top-down monomial tower coordinates with the central sign at the bottom.cliffordOutputCode: Character sectors followed by nonlinear block/row/column sectors.QuaternionFrequency: All four one-dimensional characters, and the row/column entries of the n-1 two-dimensional induced irreducibles. Source: cyclic subgroup, p.10.quaternionCyclicPhase: The plus-sign cyclic character phase, not its complex conjugate. Used only with N=2n>0 in the quaternion theorem. Source: Definition 1, p.3.quaternionCharacterX: Scalar of gamma in the character whose a-value is (-1)^e. Its square is (-1)^(ne), including odd n; the second bit chooses the root.quaternionTwiddle: The source square root C(gamma), before the separate orbit permutation.quaternionCoefficient: Complete fixed cyclic-subgroup-adapted matrix coefficients. For the 2D sector k=1,...,n-1, a is diag(z,z^-1) and gamma is C_k times the swap, where C_k=1 for even k and C_k=i for odd k, as on source p.10. The orbit permutation and the nonsplit square gamma^2=a^n are retained; the scalar C(gamma) is not substituted for the whole induced matrix. Source: PDF p.10; QuaternionGroup uses constructors a(j), xa(j)=gamma*a^j.quaternionDimension: The irreducible dimension entering the square-root normalization.quaternionFourier: The normalized plus QFT of the actual Mathlib QuaternionGroup. Source: Definition 1 p.3 and the general-n application p.10.quaternionInputCode: Source cyclic-coset encoding: a(j) has code j, gamma*a(j) code 2n+j.quaternionOutputCode: Fixed character/block/row/column ordering, with no arbitrary relabeling.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_SpectralFilter
/-!
Generic Quantum Fourier Transforms, arXiv:quant-ph/0304064v1.
The three concrete targets below are defined independently of their circuits.
Only the literal ideal one/two-qubit gate-count claim is stated. Other planned
nodes are accounted for in HARD.md and GAPS.json, without replacement lemmas.
-/
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P78
open QAlgorithms
attribute [local instance] Classical.propDecidable
/-- Fixed-length digit packing; no data-dependent choice of binary encoding.
Source: PDF p.6, product-coset and path registers. -/
def packDigits (width : ℕ) (digits : List ℕ) : ℕ :=
digits.foldr (fun digit rest => digit + 2 ^ width * rest) 0
/-- Linear embedding of amplitudes into explicitly named computational codes.
Unused wires are zero because every code is a padded binary integer.
Source: PDF pp.1–3,6. -/
def encodedWave {X : Type*} [Fintype X] {q : ℕ}
(code : X → Qubits q) (f : X → ℂ) : EuclideanSpace ℂ (Qubits q) :=
∑ x, f x • ket (code x)
/-- The source's normalization of the entire input, not of each coset piece.
Source: PDF pp.1–2 and equation (4), p.6. -/
def normalizedAmplitudes {X : Type*} [Fintype X] (f : X → ℂ) : Prop :=
∑ x, Complex.normSq (f x) = 1
/-- A fixed clean-input/clean-output implementation on every normalized input;
the circuit is chosen outside the quantifier over f. Invalid binary strings
are unconstrained. Source: Definition 1, p.3, and equations (4)–(5), p.6. -/
def realizesEncodedTransform {X Y : Type*} [Fintype X] [Fintype Y] {q : ℕ}
(c : Circuit oneTwoQubitGateSet q) (input : X → Qubits q)
(output : Y → Qubits q) (F : (X → ℂ) → (Y → ℂ)) : Prop :=
∀ f, normalizedAmplitudes f →
act c.unitary (encodedWave input f) = encodedWave output (F f)
/-- Empty digit strings have the zero code. -/
example (width : ℕ) : packDigits width [] = 0 := rfl
/-- The zero amplitude function is not a normalized state. -/
example {X : Type*} [Fintype X] : ¬ normalizedAmplitudes (fun _ : X => (0 : ℂ)) := by
simp [normalizedAmplitudes]
/-- The transversal digit at level i+1 specifies the position to which the
new letter is moved. This is the point-stabilizer tower of PDF pp.4–5,8. -/
abbrev SymmetricCosetDigits (n : ℕ) := (i : Fin n) → Fin (i.val + 1)
/-- Next letter, with a total harmless value at the unused last position. -/
def nextIndex {n : ℕ} (i : Fin n) : Fin n :=
if h : i.val + 1 < n then ⟨i.val + 1, h⟩ else i
/-- A standard tableau is an injective sequence of boxes whose every prefix
is a lower ideal. Coordinates are bounded by n; no tableau with n boxes is
lost. Source: Bratteli paths, p.4, and Young orthogonal basis, pp.5,8.
The concrete convention follows accepted Support21.P07/ Renew46.P26;
these paper modules are not imported. -/
abbrev BoundedYoungPath (n : ℕ) :=
{t : Fin n → Fin n × Fin n // Function.Injective t ∧
∀ m : ℕ, m ≤ n → IsLowerSet {b | ∃ i : Fin n, i.val < m ∧ t i = b}}
/-- The actual endpoint Young diagram, computed from the path. -/
def youngPathEndpoint {n : ℕ} (T : BoundedYoungPath n) : Finset (Fin n × Fin n) :=
Finset.univ.image T.val
/-- Paths with a fixed endpoint. Unoccupied shapes contribute no rows. -/
abbrev YoungEndpointPaths (n : ℕ) (shape : Finset (Fin n × Fin n)) :=
{T : BoundedYoungPath n // youngPathEndpoint T = shape}
/-- Fourier labels are pairs of paths with the same endpoint,
including all diagonal pairs; the endpoint itself is recorded once.
Source: PDF pp.4–6. -/
abbrev SymmetricFrequency (n : ℕ) :=
(shape : Finset (Fin n × Fin n)) × (YoungEndpointPaths n shape × YoungEndpointPaths n shape)
/-- Column minus row, fixing the sign of Young's orthogonal coefficients. -/
def boundedBoxContent {n : ℕ} (b : Fin n × Fin n) : ℤ :=
(b.2.val : ℤ) - (b.1.val : ℤ)
/-- The Young orthogonal matrix of the adjacent transposition (i,i+1), with
row U and column T. Same-row/column cases precede division; the mixed case
has positive square root and r=content(i+1)-content(i).
Source: named Young orthogonal realization, PDF pp.5,8; coefficient convention
is the accepted Support21.P07.youngActionCoefficient, written out locally. -/
def youngAdjacent {n : ℕ} (shape : Finset (Fin n × Fin n)) (i : Fin n) :
Matrix (YoungEndpointPaths n shape) (YoungEndpointPaths n shape) ℂ := fun U T =>
let a := T.val.val i
let b := T.val.val (nextIndex i)
let r : ℝ := ((boundedBoxContent b - boundedBoxContent a : ℤ) : ℝ)
if a.1 = b.1 then (if U = T then 1 else 0)
else if a.2 = b.2 then (if U = T then -1 else 0)
else if U = T then (r⁻¹ : ℝ)
else if U.val.val = T.val.val ∘ Equiv.swap i (nextIndex i) then
(Real.sqrt (1 - r⁻¹ ^ 2) : ℝ)
else 0
/-- The chosen coset product, largest subgroup first: the level-i factor is
s_digit ... s_(i-1). Source: input encoding p.6 and point stabilizers p.8. -/
def symmetricWord {n : ℕ} (x : SymmetricCosetDigits n) : List (Fin n) :=
(List.finRange n).reverse.flatMap fun level =>
(List.finRange n).filter fun j => decide ((x level).val ≤ j.val ∧ j.val < level.val)
/-- The actual permutation specified by the source transversal digits. -/
def symmetricElement {n : ℕ} (x : SymmetricCosetDigits n) : Equiv.Perm (Fin n) :=
((symmetricWord x).map fun i => Equiv.swap i (nextIndex i)).prod
/-- The representation matrix is computed from that same word, in the fixed
Young orthogonal basis, before any implementation is quantified. -/
def symmetricMatrix {n : ℕ} (x : SymmetricCosetDigits n)
(shape : Finset (Fin n × Fin n)) :
Matrix (YoungEndpointPaths n shape) (YoungEndpointPaths n shape) ℂ :=
((symmetricWord x).map (youngAdjacent shape)).prod
/-- Normalized plus-sign Fourier transform: no conjugation or inverse g.
The representation dimension is the number of tableaux of its shape.
Source: Definition 1, PDF p.3; symmetric application, pp.5,8. -/
def symmetricFourier {n : ℕ} (f : SymmetricCosetDigits n → ℂ)
(y : SymmetricFrequency n) : ℂ :=
(Real.sqrt ((Fintype.card (YoungEndpointPaths n y.1) : ℝ) / (n.factorial : ℝ)) : ℂ) *
∑ x, f x * symmetricMatrix x y.1 y.2.1 y.2.2
/-- Binary encoding of the chosen transversal digits. -/
def symmetricInputCode (n q : ℕ) (x : SymmetricCosetDigits n) : Qubits q :=
natToBits q (packDigits (Nat.clog 2 (n + 1)) (List.ofFn fun i => (x i).val))
/-- Each tableau is encoded by its successive row/column coordinates.
The shape is recoverable from either tableau and is not independently chosen. -/
def tableauDigits {n : ℕ} (T : BoundedYoungPath n) : List ℕ :=
(List.ofFn fun i => [((T.val i).1).val, ((T.val i).2).val]).flatten
/-- Fixed output encoding of the two paths. Extra wires are zero. -/
def symmetricOutputCode (n q : ℕ) (y : SymmetricFrequency n) : Qubits q :=
natToBits q (packDigits (Nat.clog 2 (n + 1))
(tableauDigits y.2.1.val ++ tableauDigits y.2.2.val))
/-- A tableau's shape is computed from its boxes, never from a free label. -/
example {n : ℕ} (T : BoundedYoungPath n) :
youngPathEndpoint T = Finset.univ.image T.val := rfl
/-- The empty word evaluates to the identity matrix on every shape sector. -/
example {n : ℕ} (shape : Finset (Fin n × Fin n)) :
(([] : List (Fin n)).map (youngAdjacent shape)).prod = 1 := rfl
/-- Coordinates (-1)^s x_n^u_n ... x_1^u_1, including the central sign.
Source: finite Clifford monomial groups, PDF p.8. -/
abbrev CliffordElement (n : ℕ) := Bool × Qubits n
/-- The crossing sign for descending monomials: a left x_i crosses a right
x_j exactly when i<j. This fixes the actual group law, including -1. -/
def cliffordCross {n : ℕ} (u v : Qubits n) : Bool :=
decide (Odd (∑ i : Fin n, ∑ j : Fin n,
if i < j ∧ u i = true ∧ v j = true then (1 : ℕ) else 0))
/-- Multiplication of signed ordered monomials. -/
def cliffordMul {n : ℕ} (g h : CliffordElement n) : CliffordElement n :=
(Bool.xor (Bool.xor g.1 h.1) (cliffordCross g.2 h.2),
fun i => Bool.xor (g.2 i) (h.2 i))
/-- Scalar corresponding to a central sign bit. -/
def centralSignScalar (b : Bool) : ℂ := if b then -1 else 1
/-- Pauli matrices used only to specify the based irreducibles explicitly. -/
def matrixX : Matrix Bool Bool ℂ := fun r s => if r = s then 0 else 1
/-- The Y sign fixes the phase convention of the adapted Clifford rows. -/
def matrixY : Matrix Bool Bool ℂ := fun r s =>
if r = s then 0 else if r then Complex.I else -Complex.I
/-- The first Clifford generator is diagonal in its adapted row basis. -/
def matrixZ : Matrix Bool Bool ℂ := fun r s =>
if r = s then centralSignScalar r else 0
/-- Even rank has one nonlinear irrep; odd rank has two. -/
abbrev CliffordSector (n : ℕ) := {b : Bool // n % 2 = 1 ∨ b = false}
/-- The explicit adapted irreducible generators are Y^r Z and Y^r X on
successive tensor factors; at odd rank the last is either sign of Y^(tensor m).
Thus restriction to the earlier even level repeats literally equal blocks,
while the next odd level is selected by the last row bit. Source: p.8. -/
def cliffordGenerator {n : ℕ} (sector : CliffordSector n) (i : Fin n) :
Matrix (Qubits (n / 2)) (Qubits (n / 2)) ℂ := fun r s =>
if i.val < 2 * (n / 2) then
∏ a : Fin (n / 2),
if a.val < i.val / 2 then matrixY (r a) (s a)
else if a.val = i.val / 2 then
(if i.val % 2 = 0 then matrixZ else matrixX) (r a) (s a)
else if r a = s a then 1 else 0
else centralSignScalar sector.val * ∏ a : Fin (n / 2), matrixY (r a) (s a)
/-- All 2^n linear characters, and all matrix entries of the nonlinear
irrep(s). No multiplicity edge is identified with another. Source: p.8. -/
abbrev CliffordFrequency (n : ℕ) :=
Qubits n ⊕ (CliffordSector n × Qubits (n / 2) × Qubits (n / 2))
/-- The based matrix element at an actual signed monomial. The sign acts
trivially in the linear characters and as -I in the nonlinear sectors. -/
def cliffordCoefficient {n : ℕ} (y : CliffordFrequency n) (g : CliffordElement n) : ℂ :=
match y with
| .inl v => ∏ i : Fin n, if g.2 i then centralSignScalar (v i) else 1
| .inr t => centralSignScalar g.1 *
((((List.finRange n).reverse.filter fun i => g.2 i).map
(cliffordGenerator t.1)).prod) t.2.1 t.2.2
/-- Definition 1's dimension factor for each Clifford Fourier row. -/
def cliffordDimension {n : ℕ} : CliffordFrequency n → ℕ
| .inl _ => 1
| .inr _ => 2 ^ (n / 2)
/-- The source's normalized plus Fourier transform of the signed monomial
coordinates, whose group order is 2^(n+1). Source: PDF pp.3,8. -/
def cliffordFourier {n : ℕ} (f : CliffordElement n → ℂ) (y : CliffordFrequency n) : ℂ :=
(Real.sqrt ((cliffordDimension y : ℝ) / (2 ^ (n + 1) : ℝ)) : ℂ) *
∑ g, f g * cliffordCoefficient y g
/-- Top-down monomial tower coordinates with the central sign at the bottom. -/
def cliffordInputCode (n q : ℕ) (g : CliffordElement n) : Qubits q :=
natToBits q ((if g.1 then 2 ^ n else 0) + bitsToNat g.2)
/-- Character sectors followed by nonlinear block/row/column sectors. -/
def cliffordOutputCode (n q : ℕ) (y : CliffordFrequency n) : Qubits q :=
natToBits q (match y with
| .inl v => bitsToNat v
| .inr t => 2 ^ n + (if t.1.val then 2 ^ (2 * (n / 2)) else 0) +
bitsToNat t.2.1 * 2 ^ (n / 2) + bitsToNat t.2.2)
/-- The central sign is a nontrivial scalar, even though linear characters
kill it. This distinguishes the source group from its Abelian quotient. -/
example : centralSignScalar true = -1 ∧ centralSignScalar false = 1 := ⟨rfl, rfl⟩
/-- One concrete phase convention in the nonlinear adapted basis. -/
example : matrixY false true = -Complex.I := rfl
/-- All four one-dimensional characters, and the row/column entries of the
n-1 two-dimensional induced irreducibles. Source: cyclic subgroup, p.10. -/
abbrev QuaternionFrequency (n : ℕ) :=
(Bool × Bool) ⊕ (Fin (n - 1) × Bool × Bool)
/-- The plus-sign cyclic character phase, not its complex conjugate.
Used only with N=2n>0 in the quaternion theorem. Source: Definition 1, p.3. -/
def quaternionCyclicPhase (N k j : ℕ) : ℂ :=
Complex.exp (((2 * Real.pi * (k : ℝ) * (j : ℝ) / (N : ℝ)) : ℝ) * Complex.I)
/-- Scalar of gamma in the character whose a-value is (-1)^e.
Its square is (-1)^(ne), including odd n; the second bit chooses the root. -/
def quaternionCharacterX (n : ℕ) (e b : Bool) : ℂ :=
centralSignScalar b * (if e = true ∧ Odd n then Complex.I else 1)
/-- The source square root C(gamma), before the separate orbit permutation. -/
def quaternionTwiddle (k : ℕ) : ℂ := if Even k then 1 else Complex.I
/-- Complete fixed cyclic-subgroup-adapted matrix coefficients. For the
2D sector k=1,...,n-1, a is diag(z,z^-1) and gamma is C_k times the swap,
where C_k=1 for even k and C_k=i for odd k, as on source p.10.
The orbit permutation and the nonsplit square gamma^2=a^n are retained;
the scalar C(gamma) is not substituted for the whole induced matrix.
Source: PDF p.10; QuaternionGroup uses constructors a(j), xa(j)=gamma*a^j. -/
def quaternionCoefficient {n : ℕ} (y : QuaternionFrequency n)
(g : QuaternionGroup n) : ℂ :=
match y with
| .inl eb =>
match g with
| .a j => centralSignScalar eb.1 ^ j.val
| .xa j => quaternionCharacterX n eb.1 eb.2 * centralSignScalar eb.1 ^ j.val
| .inr t =>
let z := quaternionCyclicPhase (2 * n) (t.1.val + 1)
match g with
| .a j => if t.2.1 = t.2.2 then
(if t.2.1 then star (z j.val) else z j.val) else 0
| .xa j => if t.2.1 = t.2.2 then 0 else
quaternionTwiddle (t.1.val + 1) * (if t.2.1 then z j.val else star (z j.val))
/-- The odd character uses the source scalar i, not an entire scalar irrep. -/
example : quaternionTwiddle 1 = Complex.I := by
norm_num [quaternionTwiddle]
/-- The irreducible dimension entering the square-root normalization. -/
def quaternionDimension {n : ℕ} : QuaternionFrequency n → ℕ
| .inl _ => 1
| .inr _ => 2
/-- The normalized plus QFT of the actual Mathlib QuaternionGroup.
Source: Definition 1 p.3 and the general-n application p.10. -/
def quaternionFourier {n : ℕ} [NeZero n] (f : QuaternionGroup n → ℂ)
(y : QuaternionFrequency n) : ℂ :=
(Real.sqrt ((quaternionDimension y : ℝ) / (4 * n : ℝ)) : ℂ) *
∑ g, f g * quaternionCoefficient y g
/-- Source cyclic-coset encoding: a(j) has code j, gamma*a(j) code 2n+j. -/
def quaternionInputCode (n q : ℕ) : QuaternionGroup n → Qubits q
| .a j => natToBits q j.val
| .xa j => natToBits q (2 * n + j.val)
/-- Fixed character/block/row/column ordering, with no arbitrary relabeling. -/
def quaternionOutputCode (n q : ℕ) (y : QuaternionFrequency n) : Qubits q :=
natToBits q (match y with
| .inl eb => (if eb.1 then 2 else 0) + (if eb.2 then 1 else 0)
| .inr t => 4 + 4 * t.1.val + (if t.2.1 then 2 else 0) + (if t.2.2 then 1 else 0))
/-- Q8 has the nonsplit square gamma^2=a^2, not gamma^2=1. -/
example : (QuaternionGroup.xa (0 : ZMod 4) : QuaternionGroup 2) *
QuaternionGroup.xa 0 = QuaternionGroup.a 2 := by
rw [QuaternionGroup.xa_mul_xa]
congr 1
end QAlgorithms.Papers.Independent.Intakenext100.P78
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Intakenext100.P78.BoundedYoungPath
For each natural number , this abbreviates the type of injective maps such that, for every natural number , the prefix set is downward closed in the coordinatewise order on the grid: whenever and , , one has . This includes the empty prefix and the complete prefix . For , the single empty map satisfies these conditions.
QAlgorithms.Papers.Independent.Intakenext100.P78.CliffordElement
For every natural number , this abbreviates the type of pairs , where is a Boolean and is an -bit string. For , the string is uniquely empty, so there are two such pairs. This abbreviation itself specifies no multiplication.
QAlgorithms.Papers.Independent.Intakenext100.P78.CliffordFrequency
For every natural number , this defines a disjoint union of two kinds of labels: a Boolean string of length , or a triple , where are Boolean strings of length and is Boolean with or . The two kinds remain distinct even when their component strings are empty. In particular, at there is one label of each kind.
QAlgorithms.Papers.Independent.Intakenext100.P78.CliffordSector
For every natural number , this defines the type of Boolean values satisfying or . Thus both Boolean values are allowed when is odd, while only is allowed when is even, including .
QAlgorithms.Papers.Independent.Intakenext100.P78.QuaternionFrequency
For every natural number , the frequency-label type is the disjoint union
The first summand consists of four Boolean-pair labels; the second consists of triples , where and are Boolean. Here is natural-number subtraction, so the second summand is empty when or .
QAlgorithms.Papers.Independent.Intakenext100.P78.SymmetricCosetDigits
For each natural number , this abbreviates the type of sequences of natural numbers satisfying , equivalently , for every . In particular, whenever . For , this type has the single empty sequence.
QAlgorithms.Papers.Independent.Intakenext100.P78.SymmetricFrequency
For each natural number , this abbreviates the type of triples , where is a finite subset of , and are two, not necessarily distinct, injective maps from into this grid. Every prefix of each map must be downward closed in the coordinatewise order, and both complete images must equal . Consequently, any triple has a downward-closed shape of cardinality ; shapes admitting no such paths contribute no triples. For , there is a single triple consisting of the empty shape and two empty paths.
QAlgorithms.Papers.Independent.Intakenext100.P78.YoungEndpointPaths
For any natural number and finite subset of the grid , this abbreviates the type of injective maps such that every prefix , for every natural number , is downward closed in the coordinatewise order, and the complete image equals . This type is empty unless is downward closed and has exactly elements. For , the grid and are necessarily empty, and the type contains the single empty path.
QAlgorithms.Papers.Independent.Intakenext100.P78.boundedBoxContent
For any natural number and box , this defines its content to be the integer , using integer subtraction, so negative values are retained. For , there is no box to which the definition can be applied.
QAlgorithms.Papers.Independent.Intakenext100.P78.centralSignScalar
For every Boolean , this defines a complex scalar equal to when and when .
QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordCoefficient
For every natural number , frequency label , and pair consisting of a Boolean and a Boolean string of length , this defines a complex coefficient . Write and for false and for true. A frequency label is either a string of length , in which case , or a triple , where have length and satisfies or , in which case
Here, with , , and in Boolean order false, true, the generator for is
and the generator for is . An empty matrix product is the identity and an empty scalar product is . Thus when is all false the two cases give and , respectively; at , these are and .
QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordCross
For every natural number and every pair of -bit strings , this defines a Boolean that is true exactly when the number of ordered index pairs satisfying , , and is odd. Equivalently, it is the parity of . For or , there are no such pairs, and the result is false.
QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordDimension
For every natural number , this assigns a natural number to each label in the disjoint union of Boolean strings of length and triples , where have length and satisfies or . The assigned number is for a string label and for a triple label, independently of the components of the label. At and , both kinds receive the value .
QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordFourier
For every natural number , every complex-valued function on pairs of a Boolean and a length- Boolean string , and every frequency label , this defines
Here , and is either a length- string , with and , or a triple , with , length- strings , and satisfying or . The sign is for false and for true. For a triple label, , where, in Boolean order false, true,
The decreasing product places the largest selected index on the left; an empty matrix product is the identity and an empty scalar product is . No normalization is required of . These formulas also apply to , when the string label yields and the triple label yields .
QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordGenerator
For every natural number , Boolean sector satisfying or , and index , this defines a complex matrix indexed by Boolean strings of length . Put , , , with Boolean order , and let be for false and for true. For strings , its entries are
The second case can occur only for odd , at . Empty scalar products equal ; consequently for the sole generator is the one-by-one matrix with entry , while for there is no index .
QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordInputCode
For all natural numbers and every pair of a Boolean and a length- Boolean string , this defines a length- Boolean string encoding
in binary with the most significant bit first. There is no lower bound on , so this encoding retains only the residue modulo and may identify different inputs. For it always returns the unique empty string; for , the integer before reduction is or , according to .
QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordMul
For every natural number and every two pairs , , where are Booleans and are -bit strings, this defines the pair
where is Boolean exclusive-or and parity is true for an odd count. When , the second component is the empty string and the first component is .
QAlgorithms.Papers.Independent.Intakenext100.P78.cliffordOutputCode
For all natural numbers , put and define for a length- Boolean string. A frequency label is either a length- string , or a triple with length- strings and Boolean satisfying or . This defines its output code to be the most-significant-bit-first length- binary representation, reduced modulo , of
No lower bound on is imposed, so distinct labels may have the same code; for every code is the empty string. At , the integers before reduction are and for the two respective labels.
QAlgorithms.Papers.Independent.Intakenext100.P78.encodedWave
For any finite type , natural number , encoding map , and function , this defines the vector in the complex Euclidean space indexed by -bit strings, where has coordinate at and elsewhere. Equivalently, its coordinate at is . The encoding need not be injective, so amplitudes with the same encoding are added, possibly cancelling; no normalization is required. If is empty, the vector is zero. The definition also includes , when there is a single bit string.
QAlgorithms.Papers.Independent.Intakenext100.P78.matrixX
This defines a complex matrix whose rows and columns are indexed by Boolean values: for every row and column , if , and otherwise. With the ordering , this is .
QAlgorithms.Papers.Independent.Intakenext100.P78.matrixY
This defines a complex matrix whose rows and columns are indexed by Boolean values: for every row and column , if ; otherwise it is when , and when , where . With the ordering , this is .
QAlgorithms.Papers.Independent.Intakenext100.P78.matrixZ
This defines a complex matrix whose rows and columns are indexed by Boolean values: for every row and column , its entry is zero when , and when its entry is for and for . With the ordering , this is .
QAlgorithms.Papers.Independent.Intakenext100.P78.nextIndex
For any natural number and index , this defines if , and otherwise defines itself. Thus the last index is fixed rather than sent back to zero; when , the sole index is fixed. For , there is no index to which the function can be applied.
QAlgorithms.Papers.Independent.Intakenext100.P78.normalizedAmplitudes
For any finite type and function , this defines the proposition , where . If is empty, the sum is , so the proposition is false.
QAlgorithms.Papers.Independent.Intakenext100.P78.packDigits
For any natural number and any finite list of natural numbers , this defines the natural number . Thus the first list entry occupies the lowest power of . The empty list gives ; when , the result is the sum of the entries. There is no requirement that an entry be less than .
QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionCharacterX
For every natural number and Booleans , identify false with and true with . This defines
Thus the sign is determined by , and the additional factor occurs precisely when is true and is odd. The definition includes , for which that additional factor is .
QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionCoefficient
For every natural number , every frequency label in the disjoint union of Boolean pairs and triples with , and every , this defines a complex coefficient as follows. Write and for the two constructor forms of , and for the natural-number value of their index; identify Booleans with . For a first-summand label , put if is true and is odd, and put otherwise; then
For a second-summand label , put , , and for even , for odd ; then
There is no assumption that is positive; for or , only the first-summand labels exist.
QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionCyclicPhase
For all natural numbers , this defines the complex number
The quotient is computed in the real numbers before multiplication by . There is no positivity assumption on : when , division by zero has value zero, so the result is .
QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionDimension
For every natural number , this assigns the natural number to each Boolean-pair frequency label and the natural number to each triple label with . For or , the triple-label summand is empty, so every existing label receives .
QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionFourier
For every natural number assumed nonzero, every complex-valued function on , and every frequency label , this defines
where for a Boolean-pair label and for a triple label. The coefficients are defined explicitly as follows: identify Booleans with , and for or write . For in the first summand,
For in the second summand, where , put , , and for even , otherwise; then
No normalization condition is imposed on , and the nonzero assumption permits , when there are only the four first-summand labels.
QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionInputCode
For all natural numbers , this assigns a -bit string to each element of : an element is assigned the binary encoding of modulo , and an element is assigned the binary encoding of modulo . Bits are ordered from most significant to least significant, so a string represents , where is for true and for false. No lower bound on or positivity assumption on is imposed; reduction modulo can identify different input integers, and gives the unique empty bit string.
QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionOutputCode
For all natural numbers , this assigns a -bit string to each frequency label by encoding the following integer modulo , with the most significant bit first:
where brackets give the numerical value or of a Boolean. The second summand is empty for or . There is no lower bound on , so reduction modulo can cause collisions; when , every label receives the empty string.
QAlgorithms.Papers.Independent.Intakenext100.P78.quaternionTwiddle
For every natural number , this defines the complex number when is even and otherwise. In particular, its value at is .
QAlgorithms.Papers.Independent.Intakenext100.P78.realizesEncodedTransform
For any finite types , natural number , circuit on bits, maps and , and arbitrary function , this defines the proposition that, for every satisfying , one has . Here is the coordinate basis vector at ; is a finite list of applications of unitary gates of arity either one or two, each with an injective choice of wires. A gate matrix on wires is extended to all bits by assigning its entry the value when agree outside the selected wires, and otherwise; is the product of these extended matrices in reverse list order, so the first listed gate acts first, and an empty circuit gives the identity. Neither encoding is required to be injective, is not required to be linear, and there is no circuit-size bound or approximation tolerance. If is empty, the proposition is vacuous; if is empty, the right-hand vector is zero. The definition includes .
QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricElement
For every natural number and every tuple with , form a list by visiting levels in decreasing order and appending the indices in increasing order. This defines the permutation of , where exchanges with if , and is the identity otherwise; thus the rightmost permutation acts first. An empty list gives the identity permutation, including when .
QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricFourier
For every natural number , every complex function on the tuples satisfying , and every frequency , this defines
Here is a finite subset of ; are injective sequences of boxes whose prefixes are downward closed in the coordinatewise order and whose sets of boxes equal ; and is the number of all such paths with endpoint . To define , visit levels , append in increasing order, obtaining , and take the matrix product , with empty product the identity. For paths , set if and otherwise, , , and . The entry is when and have the same first coordinate, and for other in that case; otherwise it is when and have the same second coordinate, and for other in that case; if neither coordinate agrees, it is for , for with , and otherwise. These real entries are viewed in , with and square root on negative arguments. There is no normalization assumption on . When , the unique frequency consists of the empty endpoint and two empty paths, and the value is evaluated at the empty tuple.
QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricInputCode
For every pair of natural numbers and every tuple with , let be the least nonnegative integer satisfying . This defines the -bit string representing
with the most significant bit first. Thus the digit occupies the least significant block of width ; no lower bound on is imposed, so higher bits may be discarded. When , the encoded integer is ; when , the output is the unique empty bit string.
QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricMatrix
For every natural number , every tuple with , and every finite set , this defines a complex matrix indexed by pairs of paths with endpoint . Here a path is an injective sequence of boxes in that square such that every prefix , for , is downward closed in the coordinatewise order, and its endpoint is . Form by visiting levels in decreasing order and appending the indices in increasing order. The matrix is , in that order. To define , put when , and otherwise; write , , and , interpreted as a real number. Then
with real entries embedded in , real inverse , and the real square root equal to on negative arguments. An empty product is the identity matrix. No condition on is assumed; if there are no paths with that endpoint, the matrix has an empty index set. For , the only endpoint is empty, there is one empty path, and the matrix is the identity.
QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricOutputCode
For every pair of natural numbers and every frequency , where are injective sequences of boxes in , every prefix of either sequence is downward closed in the coordinatewise order, and both endpoint sets equal the finite set , write , , and let be the least nonnegative integer with . This defines the most-significant-bit-first -bit representation, reduced modulo , of
Thus it packs the alternating coordinates of , followed by those of , with the first coordinate in the least significant block; the shape is not separately included in the packed list. No lower bound on is required. For , the integer is ; for , the output is the empty bit string.
QAlgorithms.Papers.Independent.Intakenext100.P78.symmetricWord
For every natural number , including , and every tuple of integers satisfying , this defines a list of indices in . Visit the levels , and at each level append, in increasing order, all indices satisfying . A level with contributes nothing; when , the entire list is empty.
QAlgorithms.Papers.Independent.Intakenext100.P78.tableauDigits
For every natural number and every injective sequence in whose prefix sets are downward closed in the coordinatewise order for every , write . This defines the list of natural numbers , of length . For , it is the empty list.
QAlgorithms.Papers.Independent.Intakenext100.P78.youngAdjacent
For any natural number , finite grid subset , and index , this defines a complex matrix whose rows and columns are injective paths into the grid with complete image and with every prefix downward closed in the coordinatewise order. Write for their underlying maps, put when and otherwise, let , , and let , regarded as a real number after taking these differences in the integers. The entry at row , column is determined by the following ordered cases: if , it is when and otherwise; otherwise, if , it is when and otherwise; otherwise, if , it is ; otherwise, if , where swaps the two indices, it is ; in every other case it is . The real values in these formulas are embedded into , with the total-function conventions and for . At the last index, , so the first case makes the matrix the identity. If there are no paths with endpoint , the matrix has an empty index set; when , there is no admissible index .
QAlgorithms.Papers.Independent.Intakenext100.P78.youngPathEndpoint
For any natural number and injective map whose every prefix , for , is downward closed under decreasing either coordinate, this defines the finite set . This set contains exactly boxes and is downward closed. For , it is empty.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.