Definitions for A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits
DefinitionQAlgorithms_Papers_Independent_Intakenext100_P82The objects the formalized statements of A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits (arXiv:1206.3223) are stated in. Each was checked against the paper by a blind read-back and a moderator.
SameGate: Equality in PSU(2), using unitary representatives; §II, PDF p.2.Syllable: The two distinct syntax letters TH and SH; §II, PDF p.2.syllableMatrix: Matrices of the two syllables, modulo the source's scalar phases; p.2.syllableValue: Printed-order evaluation, including the empty identity word; p.2.BsNormalized: Empty or ending in TH, with no two consecutive SH letters; p.2.BsCanonical: No SH earlier than syllable five, counting from the left; p.2.bsTCount: Charged non-Clifford cost: SH contributes zero, TH contributes one; p.2.BsCliffordLetter: Clifford spelling alphabet, used only for a fixed table; Appendix A, p.8.bsCliffordLetterMatrix: U(2) representatives of the projective Clifford generators; pp.2,8.cliffordWords: All 24 projective Clifford representatives, in the source's G0,...,G23 order; Appendix A, PDF p.8. A terminal is a table index, not an arbitrary spelling.cliffordMatrix: Matrix of the actual retained Clifford terminal; Appendix A, p.8.BsHTLetter: Literal source input alphabet for Propositions 1--4; p.2.htValue: Evaluation of an input gate list, in printed order; pp.2,8.CTLetter: The cost model of §IV: an arbitrary Clifford is free, T costs one; pp.1--3.ctValue: Evaluation of a competing Clifford/T presentation; pp.2--3,6.chargedT: Actual count of non-Clifford T tokens, without expanding S; pp.1--3,6.NormalOutput: Returned leading-H flag, syllable body and Clifford terminal; Proposition 1, p.2.bsNormalValue: Exact value of a normalized presentation; Proposition 1, p.2.CanonicalOutput: Returned left Clifford, canonical core and right Clifford; Proposition 2, p.2.canonicalValue: The full presentation is evaluated, but is not claimed unique; pp.2--3.BsStackSymbol: Fixed machine alphabet: 0=H, 1=T, 2=S, 3=TH, 4=SH, 5..28=G0..G23, 29/30=false/true flags, 31=separator; Appendices C,D.cliffordSymbol: One table entry is a constant-size symbol; Appendix A, p.8.syllableSymbols: Serialization retains syllable syntax, not its gate expansion; p.2.htSymbols: Input encoding is a single list scan; Appendix C, p.8.normalSymbols: Actual normalized output encoding, with both flag and terminal retained; p.8.canonicalSymbols: Actual canonical output encoding, with both Clifford terminals retained; p.9.StackAction: Primitive unit-cost stack actions: unchanged tail is shared; Appendix C, p.8.Instruction: Each instruction tests only four heads and the finite control state; p.8.Program: A fixed finite symbolic procedure, chosen before all inputs; pp.8--9.BsConfiguration: Configuration with four finite stacks; none means halted; pp.8--9.applyAction: Constant-cost action, including pop on an empty work stack; p.8.lookup: Fully scanned fixed lookup table, with first matching instruction selected; all comparisons concern finite control and four finite symbols, not matrices.bsMachineStep: One actual transition; a missing row halts without silently changing output.bsMachineRun: Fuel counts transitions of this concrete procedure; pp.8--9.bsInitial: Initial state 0, input on stack 0 and three empty work stacks.BsExecutes: Operational execution and charge: full finite-table scan at each step, constant head/stack work, input setup, and the complete retained output. The factor 20 pays for four head inspections, tests and stack actions. Fuel beyond early halting is charged too, so it cannot undercount execution.LinearNormalizes: Uniform operational linear normalization, including the empty input; Propositions 1,3 and Appendix C, pp.2,3,8.QuadraticReduces: Quadratic phase starts from an already retained normalized presentation; Proposition 4, Appendix D, pp.3,8--9.gateDistance: Phase-insensitive trace distance, with division outside the square root; §IV, p.4.hUnit: A U(2) representative of H as an invertible matrix; §II, p.2.sUnit: A U(2) representative of S as an invertible matrix; §II, p.2.ProjectiveMatrices: Ambient projective matrix group. On the unitary subgroup generated here, quotienting by the center identifies precisely one unit scalar phase; p.2.cliffordSubgroup: The source's projective subgroup generated by H and S; §II, p.2.BsSphereVector: Cartesian coordinates for the trace-level sphere; §IV, pp.4--5.unitSphere: The unit two-sphere, before its positive-trace SU(2) parametrization; p.4.bsPauli: Fixed ordered Pauli basis X,Y,Z, matching the source's axes; pp.4,9.sphereGate: Unique positive-trace representative at 0<t<2, in the source's sphere coordinates; §IV, p.4. Degenerate endpoints are deliberately excluded by the theorem.bsCliffordRotation: Matrix of Clifford conjugation in the ordered Pauli basis; §IV p.4, Appendix E p.9.octahedronVertices: Six vertices of the source's octahedron; p.4.octahedronRotations: Rotational octahedral group as concrete matrices, excluding all reflections; p.4.fundamentalTile: Closed spherical triangle with vertices +X,+Z,+(1,1,1)/sqrt(3); p.4.fundamentalInterior: Interior relative to the two-sphere, not the ambient three-space; p.4.tile: The 24 tile images under conjugation; p.4.tileInterior: Images of the relative interiors; p.4.initialVertices: Vertices of the initial triangle, with the positive diagonal normalized; p.4.tileVertices: All tile vertices, as the union of images of the three initial vertices; p.5.RecursionTree: A supplied tree of the auxiliary choices in Eq.(1), §V, PDF p.5. Each node composes V W V-dagger W-dagger U. No approximation property of the auxiliary choices is assumed or claimed here.recursionValue: Exact five-factor gate at each node of Eq.(1); p.5.LeavesBounded: Every leaf is an actual canonical database entry of T-count at most t; p.5.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Gates
/-!
Bocharov--Svore, arXiv:1206.3223v1. Products are in printed order,
acting right to left. Frozen H,T,S matrices are U(2) representatives of
exactly the source's projective gates: source H = i H_frozen and source
T = exp(-i*pi/8) T_frozen. Every gate equality below discards one unit
scalar phase. No state, measurement, ancilla or literal S=TT cost is used.
The local finite four-stack machine gives operational meaning to symbolic
runtime. Its transitions inspect four heads and use a fixed finite table;
only push/pop/keep operations are allowed. Setup and the actual returned
serialization are charged. No matrix arithmetic is assigned unit cost.
-/
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P82
open scoped BigOperators
local notation "Mat" => Matrix Bool Bool ℂ
/-- Equality in PSU(2), using unitary representatives; §II, PDF p.2. -/
def SameGate (U V : Mat) : Prop := ∃ z : ℂ, ‖z‖ = 1 ∧ U = z • V
/-- The two distinct syntax letters TH and SH; §II, PDF p.2. -/
inductive Syllable where
| th | sh
deriving DecidableEq
/-- Matrices of the two syllables, modulo the source's scalar phases; p.2. -/
def syllableMatrix : Syllable → Mat
| .th => QAlgorithms.gateT * QAlgorithms.hadamard
| .sh => QAlgorithms.phaseS * QAlgorithms.hadamard
/-- Printed-order evaluation, including the empty identity word; p.2. -/
def syllableValue (w : List Syllable) : Mat := (w.map syllableMatrix).prod
/-- Empty or ending in TH, with no two consecutive SH letters; p.2. -/
def BsNormalized : List Syllable → Prop
| [] => True
| [.th] => True
| [.sh] => False
| a :: b :: w => (a ≠ .sh ∨ b ≠ .sh) ∧ BsNormalized (b :: w)
/-- No SH earlier than syllable five, counting from the left; p.2. -/
def BsCanonical (w : List Syllable) : Prop :=
BsNormalized w ∧ ∀ a ∈ w.take 4, a = .th
/-- Charged non-Clifford cost: SH contributes zero, TH contributes one; p.2. -/
def bsTCount (w : List Syllable) : ℕ :=
(w.filter fun a => decide (a = .th)).length
/-- Clifford spelling alphabet, used only for a fixed table; Appendix A, p.8. -/
inductive BsCliffordLetter where
| h | s
deriving DecidableEq
/-- U(2) representatives of the projective Clifford generators; pp.2,8. -/
def bsCliffordLetterMatrix : BsCliffordLetter → Mat
| .h => QAlgorithms.hadamard
| .s => QAlgorithms.phaseS
/-- All 24 projective Clifford representatives, in the source's G0,...,G23 order;
Appendix A, PDF p.8. A terminal is a table index, not an arbitrary spelling. -/
def cliffordWords : Fin 24 → List BsCliffordLetter := ![
[], [.h], [.h,.s,.s,.h], [.s,.s], [.s], [.s,.s,.s],
[.h,.s,.s], [.s,.s,.h], [.s,.h], [.s,.s,.s,.h],
[.s,.s,.h,.s,.s,.h], [.s,.h,.s,.s,.h], [.s,.s,.s,.h,.s,.s,.h],
[.h,.s], [.h,.s,.s,.s], [.s,.s,.h,.s,.s], [.s,.h,.s,.s],
[.s,.s,.s,.h,.s,.s], [.h,.s,.h], [.h,.s,.s,.s,.h],
[.h,.s,.h,.s,.s,.h], [.h,.s,.s,.s,.h,.s,.s,.h],
[.s,.s,.s,.h,.s], [.s,.h,.s,.s,.s]]
/-- Matrix of the actual retained Clifford terminal; Appendix A, p.8. -/
def cliffordMatrix (g : Fin 24) : Mat :=
((cliffordWords g).map bsCliffordLetterMatrix).prod
/-- Literal source input alphabet for Propositions 1--4; p.2. -/
inductive BsHTLetter where
| h | t
deriving DecidableEq
/-- Evaluation of an input gate list, in printed order; pp.2,8. -/
def htValue (w : List BsHTLetter) : Mat :=
(w.map fun a => match a with
| .h => QAlgorithms.hadamard
| .t => QAlgorithms.gateT).prod
/-- The cost model of §IV: an arbitrary Clifford is free, T costs one; pp.1--3. -/
inductive CTLetter where
| clifford (g : Fin 24)
| t
deriving DecidableEq
/-- Evaluation of a competing Clifford/T presentation; pp.2--3,6. -/
def ctValue (w : List CTLetter) : Mat :=
(w.map fun a => match a with
| .clifford g => cliffordMatrix g
| .t => QAlgorithms.gateT).prod
/-- Actual count of non-Clifford T tokens, without expanding S; pp.1--3,6. -/
def chargedT (w : List CTLetter) : ℕ :=
(w.filter fun a => match a with | .t => true | .clifford _ => false).length
/-- Returned leading-H flag, syllable body and Clifford terminal; Proposition 1, p.2. -/
structure NormalOutput where
leadingH : Bool
body : List Syllable
terminal : Fin 24
/-- Exact value of a normalized presentation; Proposition 1, p.2. -/
def bsNormalValue (o : NormalOutput) : Mat :=
(if o.leadingH then QAlgorithms.hadamard else 1) *
syllableValue o.body * cliffordMatrix o.terminal
/-- Returned left Clifford, canonical core and right Clifford; Proposition 2, p.2. -/
structure CanonicalOutput where
left : Fin 24
body : List Syllable
right : Fin 24
/-- The full presentation is evaluated, but is not claimed unique; pp.2--3. -/
def canonicalValue (o : CanonicalOutput) : Mat :=
cliffordMatrix o.left * syllableValue o.body * cliffordMatrix o.right
/-- Fixed machine alphabet: 0=H, 1=T, 2=S, 3=TH, 4=SH,
5..28=G0..G23, 29/30=false/true flags, 31=separator; Appendices C,D. -/
abbrev BsStackSymbol := Fin 32
/-- One table entry is a constant-size symbol; Appendix A, p.8. -/
def cliffordSymbol (g : Fin 24) : BsStackSymbol := ⟨5 + g.val, by omega⟩
/-- Serialization retains syllable syntax, not its gate expansion; p.2. -/
def syllableSymbols (w : List Syllable) : List BsStackSymbol :=
w.map fun a => match a with | .th => 3 | .sh => 4
/-- Input encoding is a single list scan; Appendix C, p.8. -/
def htSymbols (w : List BsHTLetter) : List BsStackSymbol :=
w.map fun a => match a with | .h => 0 | .t => 1
/-- Actual normalized output encoding, with both flag and terminal retained; p.8. -/
def normalSymbols (o : NormalOutput) : List BsStackSymbol :=
[if o.leadingH then 30 else 29] ++ syllableSymbols o.body ++ [cliffordSymbol o.terminal]
/-- Actual canonical output encoding, with both Clifford terminals retained; p.9. -/
def canonicalSymbols (o : CanonicalOutput) : List BsStackSymbol :=
[cliffordSymbol o.left] ++ syllableSymbols o.body ++ [cliffordSymbol o.right]
/-- Primitive unit-cost stack actions: unchanged tail is shared; Appendix C, p.8. -/
inductive StackAction where
| keep | pop | push (a : BsStackSymbol)
/-- Each instruction tests only four heads and the finite control state; p.8. -/
structure Instruction where
state : ℕ
heads : Fin 4 → Option BsStackSymbol
actions : Fin 4 → StackAction
next : Option ℕ
/-- A fixed finite symbolic procedure, chosen before all inputs; pp.8--9. -/
abbrev Program := List Instruction
/-- Configuration with four finite stacks; none means halted; pp.8--9. -/
structure BsConfiguration where
control : Option ℕ
workStacks : Fin 4 → List BsStackSymbol
/-- Constant-cost action, including pop on an empty work stack; p.8. -/
def applyAction : StackAction → List BsStackSymbol → List BsStackSymbol
| .keep, s => s
| .pop, s => s.tail
| .push a, s => a :: s
/-- Fully scanned fixed lookup table, with first matching instruction selected;
all comparisons concern finite control and four finite symbols, not matrices. -/
def lookup (p : Program) (c : BsConfiguration) : Option Instruction :=
p.foldr (fun row rest =>
if c.control = some row.state ∧ (fun j => (c.workStacks j).head?) = row.heads
then some row else rest) none
/-- One actual transition; a missing row halts without silently changing output. -/
def bsMachineStep (p : Program) (c : BsConfiguration) : BsConfiguration :=
if c.control = none then c else
match lookup p c with
| none => { c with control := none }
| some row => ⟨row.next, fun j => applyAction (row.actions j) (c.workStacks j)⟩
/-- Fuel counts transitions of this concrete procedure; pp.8--9. -/
def bsMachineRun (p : Program) : ℕ → BsConfiguration → BsConfiguration
| 0, c => c
| k + 1, c => bsMachineRun p k (bsMachineStep p c)
/-- Initial state 0, input on stack 0 and three empty work stacks. -/
def bsInitial (input : List BsStackSymbol) : BsConfiguration :=
⟨some 0, fun j => if j = 0 then input else []⟩
/-- Operational execution and charge: full finite-table scan at each step,
constant head/stack work, input setup, and the complete retained output.
The factor 20 pays for four head inspections, tests and stack actions.
Fuel beyond early halting is charged too, so it cannot undercount execution. -/
def BsExecutes (p : Program) (input output : List BsStackSymbol) (cost : ℕ) : Prop :=
∃ steps : ℕ,
(bsMachineRun p steps (bsInitial input)).control = none ∧
(bsMachineRun p steps (bsInitial input)).workStacks 0 = output ∧
cost = input.length + output.length + 1 + 20 * (p.length + 1) * steps
/-- Uniform operational linear normalization, including the empty input;
Propositions 1,3 and Appendix C, pp.2,3,8. -/
def LinearNormalizes (p : Program) (K : ℕ) : Prop :=
∀ w : List BsHTLetter, ∃ o : NormalOutput, ∃ cost : ℕ,
BsNormalized o.body ∧ SameGate (bsNormalValue o) (htValue w) ∧
BsExecutes p (htSymbols w) (normalSymbols o) cost ∧ cost ≤ K * (w.length + 1)
/-- Quadratic phase starts from an already retained normalized presentation;
Proposition 4, Appendix D, pp.3,8--9. -/
def QuadraticReduces (p : Program) (K : ℕ) : Prop :=
∀ o : NormalOutput, BsNormalized o.body → ∃ c : CanonicalOutput, ∃ cost : ℕ,
BsCanonical c.body ∧ SameGate (canonicalValue c) (bsNormalValue o) ∧
BsExecutes p (normalSymbols o) (canonicalSymbols c) cost ∧
cost ≤ K * (bsTCount o.body + 1) ^ 2
/-- Phase-insensitive trace distance, with division outside the square root; §IV, p.4. -/
def gateDistance (U V : Mat) : ℝ :=
Real.sqrt (2 - ‖Matrix.trace (U * star V)‖) / 2
/-- A U(2) representative of H as an invertible matrix; §II, p.2. -/
def hUnit : Matˣ where
val := QAlgorithms.hadamard
inv := QAlgorithms.hadamard
val_inv := QAlgorithms.hadamard_mul_self
inv_val := QAlgorithms.hadamard_mul_self
/-- A U(2) representative of S as an invertible matrix; §II, p.2. -/
def sUnit : Matˣ where
val := QAlgorithms.phaseS
inv := QAlgorithms.phaseS ^ 3
val_inv := by
ext a b
cases a <;> cases b <;>
simp [QAlgorithms.phaseS, pow_succ, Matrix.mul_apply, Fintype.sum_bool]
inv_val := by
ext a b
cases a <;> cases b <;>
simp [QAlgorithms.phaseS, pow_succ, Matrix.mul_apply, Fintype.sum_bool]
/-- Ambient projective matrix group. On the unitary subgroup generated here,
quotienting by the center identifies precisely one unit scalar phase; p.2. -/
abbrev ProjectiveMatrices := Matˣ ⧸ Subgroup.center Matˣ
/-- The source's projective subgroup generated by H and S; §II, p.2. -/
def cliffordSubgroup : Subgroup ProjectiveMatrices :=
Subgroup.closure {QuotientGroup.mk hUnit, QuotientGroup.mk sUnit}
example : syllableValue [] = 1 := rfl
example : BsNormalized [] ∧ BsCanonical [] ∧ bsTCount [] = 0 := by
simp [BsNormalized, BsCanonical, bsTCount]
example : BsCanonical [.th, .th, .th, .th, .sh, .th] ∧
bsTCount [.th, .th, .th, .th, .sh, .th] = 5 := by
simp [BsCanonical, BsNormalized, bsTCount]
example : ¬ BsNormalized [.sh, .sh, .th] := by simp [BsNormalized]
example : chargedT [.clifford 4] = 0 ∧ cliffordMatrix 4 = QAlgorithms.phaseS := by
simp [chargedT, cliffordMatrix, cliffordWords, bsCliffordLetterMatrix]
example : SameGate (1 : Mat) 1 := ⟨1, by simp, by simp⟩
example : (bsMachineRun [] 1 (bsInitial [])).control = none := by
simp [bsMachineRun, bsMachineStep, lookup, bsInitial]
example : normalSymbols ⟨false, [], 0⟩ = [29, 5] := rfl
example : canonicalSymbols ⟨0, [], 0⟩ = [5, 5] := rfl
example : QuotientGroup.mk hUnit ∈ cliffordSubgroup := by
exact Subgroup.subset_closure (by simp)
example : gateDistance (1 : Mat) 1 = 0 := by
norm_num [gateDistance, Matrix.trace, Fintype.sum_bool]
/-- Cartesian coordinates for the trace-level sphere; §IV, pp.4--5. -/
abbrev BsSphereVector := Fin 3 → ℝ
/-- The unit two-sphere, before its positive-trace SU(2) parametrization; p.4. -/
def unitSphere : Set BsSphereVector := {v | ∑ j, (v j) ^ 2 = 1}
/-- Fixed ordered Pauli basis X,Y,Z, matching the source's axes; pp.4,9. -/
def bsPauli : Fin 3 → Mat := ![QAlgorithms.pauliX, QAlgorithms.pauliY, QAlgorithms.pauliZ]
/-- Unique positive-trace representative at 0<t<2, in the source's sphere coordinates;
§IV, p.4. Degenerate endpoints are deliberately excluded by the theorem. -/
def sphereGate (t : ℝ) (v : BsSphereVector) : Mat :=
((t / 2 : ℝ) : ℂ) • (1 : Mat) +
(Complex.I * (Real.sqrt (1 - t ^ 2 / 4) : ℂ)) •
(∑ j, (v j : ℂ) • bsPauli j)
/-- Matrix of Clifford conjugation in the ordered Pauli basis; §IV p.4, Appendix E p.9. -/
def bsCliffordRotation (g : Fin 24) : Matrix (Fin 3) (Fin 3) ℝ :=
fun i j => (Matrix.trace
(bsPauli i * cliffordMatrix g * bsPauli j * star (cliffordMatrix g))).re / 2
/-- Six vertices of the source's octahedron; p.4. -/
def octahedronVertices : Set BsSphereVector :=
{v | ∃ j : Fin 3,
v = (fun k => if k = j then 1 else 0) ∨
v = (fun k => if k = j then -1 else 0)}
/-- Rotational octahedral group as concrete matrices, excluding all reflections; p.4. -/
def octahedronRotations : Set (Matrix (Fin 3) (Fin 3) ℝ) :=
{R | R.transpose * R = 1 ∧ R.det = 1 ∧
(fun v => R.mulVec v) '' octahedronVertices = octahedronVertices}
/-- Closed spherical triangle with vertices +X,+Z,+(1,1,1)/sqrt(3); p.4. -/
def fundamentalTile : Set BsSphereVector :=
{v | v ∈ unitSphere ∧ 0 ≤ v 1 ∧ v 1 ≤ v 0 ∧ v 1 ≤ v 2}
/-- Interior relative to the two-sphere, not the ambient three-space; p.4. -/
def fundamentalInterior : Set BsSphereVector :=
{v | v ∈ unitSphere ∧ 0 < v 1 ∧ v 1 < v 0 ∧ v 1 < v 2}
/-- The 24 tile images under conjugation; p.4. -/
def tile (g : Fin 24) : Set BsSphereVector := (fun v => (bsCliffordRotation g).mulVec v) '' fundamentalTile
/-- Images of the relative interiors; p.4. -/
def tileInterior (g : Fin 24) : Set BsSphereVector :=
(fun v => (bsCliffordRotation g).mulVec v) '' fundamentalInterior
/-- Vertices of the initial triangle, with the positive diagonal normalized; p.4. -/
def initialVertices : Set BsSphereVector :=
{v | v = (fun k => if k = 0 then 1 else 0) ∨
v = (fun k => if k = 2 then 1 else 0) ∨
v = (fun _ => (Real.sqrt 3)⁻¹)}
/-- All tile vertices, as the union of images of the three initial vertices; p.5. -/
def tileVertices : Set BsSphereVector :=
{v | ∃ g : Fin 24, ∃ w ∈ initialVertices, v = (bsCliffordRotation g).mulVec w}
example : (![1, 0, 0] : BsSphereVector) ∈ fundamentalTile := by
have hthird : (![1, 0, 0] : BsSphereVector) 2 = 0 := rfl
norm_num [fundamentalTile, unitSphere, Fin.sum_univ_three, hthird]
example : sphereGate 2 (fun _ => 0) = 1 := by
norm_num [sphereGate]
/-- A supplied tree of the auxiliary choices in Eq.(1), §V, PDF p.5.
Each node composes V W V-dagger W-dagger U. No approximation property
of the auxiliary choices is assumed or claimed here. -/
inductive RecursionTree : ℕ → Type where
| base (c : CanonicalOutput) : RecursionTree 0
| step {n : ℕ} (v w u : RecursionTree n) : RecursionTree (n + 1)
/-- Exact five-factor gate at each node of Eq.(1); p.5. -/
def recursionValue : {n : ℕ} → RecursionTree n → Mat
| _, .base c => canonicalValue c
| _, .step v w u => recursionValue v * recursionValue w * star (recursionValue v) *
star (recursionValue w) * recursionValue u
/-- Every leaf is an actual canonical database entry of T-count at most t; p.5. -/
def LeavesBounded (t : ℕ) : {n : ℕ} → RecursionTree n → Prop
| _, .base c => BsCanonical c.body ∧ bsTCount c.body ≤ t
| _, .step v w u => LeavesBounded t v ∧ LeavesBounded t w ∧ LeavesBounded t u
example (c : CanonicalOutput) : recursionValue (.base c) = canonicalValue c := rfl
end QAlgorithms.Papers.Independent.Intakenext100.P82
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Intakenext100.P82.BsCanonical
For every finite list of the symbols and , means that is empty or ends in , has no two consecutive occurrences of , and every entry among its first four entries is . If has fewer than four entries, this last requirement applies to all its entries. The empty list satisfies the property.
QAlgorithms.Papers.Independent.Intakenext100.P82.BsCliffordLetter
is a type with exactly two distinct elements, denoted and . Equality between its elements is decidable.
QAlgorithms.Papers.Independent.Intakenext100.P82.BsConfiguration
A configuration is a record consisting of a control field containing either no natural number or a natural number, and a function assigning to each index a finite list of symbols from . These four lists are the work stacks and may independently be empty; the declaration imposes no relation between the control field and the stacks.
QAlgorithms.Papers.Independent.Intakenext100.P82.BsExecutes
For every program , input and output lists over , and natural-number cost , this predicate holds exactly when there exists a natural number such that, after transitions from control , input on stack , and empty stacks , control is absent, stack equals the output, and , where vertical bars denote list length. Here is a finite ordered list of instructions, each containing a natural-number state, four optional symbol heads, four actions, and an optional natural-number next state. Each transition leaves absent control unchanged; otherwise it selects the first instruction whose state matches control and whose four optional heads exactly match the stacks' optional first symbols. If no instruction matches, control becomes absent and the stacks stay unchanged; if one matches, control becomes its next field and its actions simultaneously keep, pop, or push a symbol on each respective stack, with popping an empty stack leaving it empty. No condition is imposed on the final stacks , and need not be the first time control becomes absent. Although the existential quantifier includes , that value cannot satisfy the absent-control requirement because initial control contains .
QAlgorithms.Papers.Independent.Intakenext100.P82.BsHTLetter
is a type with exactly two distinct elements, denoted and . Equality between its elements is decidable.
QAlgorithms.Papers.Independent.Intakenext100.P82.BsNormalized
For a finite list of the two symbols and , is the following recursively defined property: the empty list satisfies it; the singleton list satisfies it; the singleton list does not; and a list beginning with , followed by a remaining list , satisfies it exactly when and the tail beginning with , followed by , satisfies it. Equivalently, the list is empty, or it ends in and has no two consecutive occurrences of .
QAlgorithms.Papers.Independent.Intakenext100.P82.BsSphereVector
The notation abbreviates the type of all functions from to , equivalently all real triples ; it imposes no condition on their coordinates or norm.
QAlgorithms.Papers.Independent.Intakenext100.P82.BsStackSymbol
is an abbreviation for the type of natural numbers strictly less than , so its possible values are exactly .
QAlgorithms.Papers.Independent.Intakenext100.P82.CTLetter
is a type whose elements are either a letter carrying an integer index , or the letter . These constructors are distinct, two Clifford letters are equal exactly when their indices are equal, and equality of letters is decidable.
QAlgorithms.Papers.Independent.Intakenext100.P82.CanonicalOutput
is the type of records consisting of a field that is an integer in , a field that is an arbitrary finite list over the two-symbol alphabet , and a field that is an integer in . The body may be empty, and the record imposes no further conditions on these fields.
QAlgorithms.Papers.Independent.Intakenext100.P82.Instruction
An instruction is a record with four fields: a natural-number state; a function assigning to each stack index either no symbol or a symbol from ; a function assigning to each such an action, which is either , , or for a symbol ; and a next field containing either no natural number or a natural number. There are no additional constraints relating these fields.
QAlgorithms.Papers.Independent.Intakenext100.P82.LeavesBounded
For every natural number , including , and every tree of any natural-number index , this defines a predicate recursively as follows. A tree of index zero is a leaf carrying a triple , where and is a finite list over ; the predicate holds at this leaf exactly when is empty or ends in , no two consecutive entries of are both , every entry among the first entries is , and the number of occurrences of in is at most . At a node of index with three ordered children of index , the predicate holds exactly when it holds for each of the three children with the same bound . The empty leaf list satisfies the conditions for every , including zero; the two indices are unrestricted within .
QAlgorithms.Papers.Independent.Intakenext100.P82.LinearNormalizes
For a finite program and a natural number , this predicate means the following. Write , , and , with rows and columns ordered as false, true. A syllable is either , with matrix , or , with matrix ; let be the product of the matrices of a syllable list , in list order, with empty product . Call normalized when it is empty or ends in and has no two consecutive syllables. For indices , define by the indexed tuple
Every finite input word in the letters , including the empty word, must admit a Boolean , a normalized syllable list , an index , a natural cost , and a complex number of modulus one such that
where replaces by and multiplies in list order. The program must execute from the encoding of , obtained by replacing by , to the list , where replaces by and denotes concatenation. Precisely, a program is an ordered finite list of instructions for four stacks over ; each instruction specifies a natural control state, the exact four stack heads, an action on each stack, and either a next natural state or a halt. An action keeps the stack, removes its head, or pushes one symbol; removing from an empty stack leaves it empty. Execution starts in state , with the input on stack and the other three stacks empty. At each step the first instruction matching the current state and all four heads is applied, with all stack actions using the current stacks; no matching instruction causes a halt without changing the stacks, and a halted configuration stays fixed. There must be a natural number of steps after which the machine is halted and stack is exactly the prescribed output , with no restriction on the other stacks, and
where is the input encoding. The definition allows , although its positive execution cost makes the predicate unsatisfiable for that value.
QAlgorithms.Papers.Independent.Intakenext100.P82.NormalOutput
is the type of records consisting of a Boolean field , a field that is an arbitrary finite list over the two-symbol alphabet , and a field that is an integer in . The body may be empty, and the record imposes no further conditions on these fields.
QAlgorithms.Papers.Independent.Intakenext100.P82.Program
A program is an abbreviation for a finite ordered list of instructions. Each instruction consists of a natural-number state, four optional symbols from indexed by , four actions indexed in the same way, and an optional natural-number next state; each action is , , or for a symbol . The list may be empty and may contain repeated instructions or multiple instructions with the same state and optional symbols.
QAlgorithms.Papers.Independent.Intakenext100.P82.ProjectiveMatrices
This is an abbreviation for the quotient of the group of invertible complex matrices by its center, where the center consists of the invertible matrices commuting with every invertible matrix. Thus two invertible matrices represent the same quotient element exactly when belongs to that center; equivalently, they differ by multiplication by an arbitrary nonzero complex scalar.
QAlgorithms.Papers.Independent.Intakenext100.P82.QuadraticReduces
For a finite program and a natural number , this predicate means the following. Put , , and , with Boolean indices ordered false, true. A syllable represents , a syllable represents , and is the product for a syllable list , with . A list is normalized if it is empty or ends in and contains no consecutive syllables; it is canonical if it is normalized and its first syllables are all . Thus the empty list is canonical, and a canonical list of length less than four consists entirely of . Define the matrices , indexed from to , by
For every Boolean , normalized syllable list , and index , there must exist indices , a canonical syllable list , a natural cost , and a complex number of modulus one such that
where counts occurrences of . The program must execute from to , where replaces by . Here a program is an ordered finite list of instructions on four stacks over , each instruction specifying a natural state, all four exact heads, four actions, and a next natural state or halt. Actions keep, pop, or push one symbol; popping an empty stack leaves it empty. The machine starts in state , with on stack and the other stacks empty, and applies the first instruction matching its state and four heads, updating the stacks simultaneously. If no instruction matches, it halts with its stacks unchanged; halted configurations stay fixed. For some natural number of steps it must be halted with stack equal to , without conditions on the other stacks, and the cost must be exactly
The quantification includes empty normalized bodies. Although is permitted as an argument, it cannot satisfy this predicate because the required execution costs are positive.
QAlgorithms.Papers.Independent.Intakenext100.P82.RecursionTree
This defines a family of types of trees indexed by a natural number , including . A tree of index is constructed from a triple , where and is any finite list over the two symbols and . For every natural number , three ordered trees of the same index construct a tree of index . These are the constructors of the family; the leaf triples have no normalization or other predicate imposed on them.
QAlgorithms.Papers.Independent.Intakenext100.P82.SameGate
For complex matrices and , means that there exists a complex number with such that , where multiplication by scales every matrix entry. No invertibility, unitarity, or nonzero assumption is imposed on or ; in particular, both may be zero.
QAlgorithms.Papers.Independent.Intakenext100.P82.StackAction
This defines a type whose values are exactly the two distinct constructors and , together with a constructor for each symbol . Different symbols give different push values, and no push value equals either of the other two constructors. This declaration itself assigns no operation on stacks to these constructors.
QAlgorithms.Papers.Independent.Intakenext100.P82.Syllable
is a type with exactly two distinct elements, denoted and . Equality between its elements is decidable.
QAlgorithms.Papers.Independent.Intakenext100.P82.applyAction
For every action and every finite list of symbols from , this defines the resulting list as follows: returns ; returns the tail of , deleting its first symbol when one exists and returning the empty list when is empty; and , for any symbol , returns the list with prepended to .
QAlgorithms.Papers.Independent.Intakenext100.P82.bsCliffordLetterMatrix
The function assigns a complex matrix to each of the two symbols and . With rows and columns ordered as , its values are
where is the imaginary unit.
QAlgorithms.Papers.Independent.Intakenext100.P82.bsCliffordRotation
Let , , and define , in order, by
Put
For every , the real matrix is defined entrywise, for all , by
where denotes conjugate transpose.
QAlgorithms.Papers.Independent.Intakenext100.P82.bsInitial
For every finite input list of symbols from , including the empty list, this defines a configuration whose control contains the natural number , whose stack at index is exactly the input list, and whose stacks at indices are empty.
QAlgorithms.Papers.Independent.Intakenext100.P82.bsMachineRun
For every program , every natural number , and every configuration , this defines the configuration obtained by applying the following transition exactly times, with returning . A configuration has optional natural-number control and four finite stacks over . A program is a finite ordered list of instructions, each specifying a natural-number state, four optional stack heads, four actions, and an optional natural-number next state. A transition leaves a configuration with absent control unchanged; otherwise it chooses the first instruction matching the control and all four optional heads, where an empty stack has no head. If none matches, it makes control absent without changing the stacks. If one matches, it sets control to that instruction's next field and simultaneously applies its four actions: keep preserves a stack, pop removes its first symbol or leaves an empty stack empty, and push prepends its specified symbol. Thus transitions after control becomes absent leave the configuration unchanged.
QAlgorithms.Papers.Independent.Intakenext100.P82.bsMachineStep
For every program , a finite ordered list of instructions, and every configuration , consisting of optional natural-number control and four finite stacks of symbols from , this defines one transition. If control is absent, the configuration is returned unchanged. Otherwise, select the first instruction whose natural-number state equals the present control value and whose four specified optional symbols exactly equal the four optional stack heads, with absence matching an empty stack. If there is no such instruction, control becomes absent and the stacks remain unchanged. If there is such an instruction, control becomes its optional natural-number next state, and each stack is updated using that instruction's corresponding action: keep leaves it unchanged, pop removes its first symbol and leaves an empty stack empty, and push of a symbol prepends that symbol. All four stack updates use the original stacks.
QAlgorithms.Papers.Independent.Intakenext100.P82.bsNormalValue
For any record consisting of a Boolean , a finite list over , and an index , , where , , and is the product in list order obtained by replacing by and by , with . Here , , and , with rows and columns ordered as false, true, and . This definition applies to every such body list without a normalization hypothesis.
QAlgorithms.Papers.Independent.Intakenext100.P82.bsPauli
The function assigns to each index in a complex matrix, with rows and columns ordered as false, true, according to
QAlgorithms.Papers.Independent.Intakenext100.P82.bsTCount
For every finite list of the two symbols and , is the natural number of entries of equal to , counting repeated occurrences separately. Entries equal to contribute nothing, and the empty list has count zero.
QAlgorithms.Papers.Independent.Intakenext100.P82.canonicalSymbols
For any record consisting of integers and a finite list of syllables and , this defines a list of symbols from : first , then the body with each replaced by and each replaced by , and finally . The body may be empty, giving a two-symbol list; no canonicality condition is imposed on the body.
QAlgorithms.Papers.Independent.Intakenext100.P82.canonicalValue
For any record consisting of indices and a finite list over , , where is the product in list order obtained by replacing by and by , with . Here , , and , with rows and columns ordered as false, true, and . This definition applies to every such body list without a canonicality hypothesis.
QAlgorithms.Papers.Independent.Intakenext100.P82.chargedT
For any finite list whose letters are or with , is the natural number of occurrences of the letter in . Every Clifford letter contributes zero, regardless of its index; the empty list has count zero.
QAlgorithms.Papers.Independent.Intakenext100.P82.cliffordMatrix
For every integer index with , is obtained by taking the word at position in the following sequence, whose positions start at zero, replacing each by and each by , and multiplying the resulting matrices in the order written:
Here words are lists of the two symbols , is the imaginary unit, and the complex matrices use the coordinate order . The empty word gives the identity matrix.
QAlgorithms.Papers.Independent.Intakenext100.P82.cliffordSubgroup
This defines the smallest subgroup containing the classes of
in the group of invertible complex matrices modulo its center, with Boolean indices ordered false, true. The center consists of invertible matrices commuting with every invertible matrix, equivalently the nonzero scalar matrices. The subgroup therefore consists of all finite products of the quotient classes of and their inverses, including the empty product.
QAlgorithms.Papers.Independent.Intakenext100.P82.cliffordSymbol
For every integer index , is the stack symbol , viewed as a natural number less than . Thus its values range from through .
QAlgorithms.Papers.Independent.Intakenext100.P82.cliffordWords
The function assigns a finite list of the two symbols to each integer index with . Writing juxtaposition for a list of successive symbols and for the empty list, its values at indices , in that order, are
QAlgorithms.Papers.Independent.Intakenext100.P82.ctValue
For any finite list whose letters are or with , is the matrix product in list order, replacing by and by . Here and , with rows and columns ordered as false, true, and the indexed matrices are . The empty list has value .
QAlgorithms.Papers.Independent.Intakenext100.P82.fundamentalInterior
The fundamental interior is the set of all vectors satisfying
QAlgorithms.Papers.Independent.Intakenext100.P82.fundamentalTile
The fundamental tile is the set of all vectors satisfying
All three inequalities are non-strict, so equality is allowed in each.
QAlgorithms.Papers.Independent.Intakenext100.P82.gateDistance
For any two complex matrices , define their gate distance by
where is the conjugate transpose of and the absolute value is the complex modulus. No unitarity assumption is required. The real square root is defined to be zero on negative inputs, so this distance equals zero whenever .
QAlgorithms.Papers.Independent.Intakenext100.P82.hUnit
This defines an element of the group of invertible complex matrices whose underlying matrix and specified inverse are both
with rows and columns ordered false, true. The two required inverse identities are , once for the product of the matrix with its specified inverse and once for the reverse product.
QAlgorithms.Papers.Independent.Intakenext100.P82.htSymbols
For any finite list over the two-symbol alphabet , is the list of stack symbols in obtained by replacing every by and every by , preserving order and length. The empty list maps to the empty list.
QAlgorithms.Papers.Independent.Intakenext100.P82.htValue
For any finite list of letters from , is the product, in list order, obtained by replacing each by and each by , with matrix rows and columns ordered as false, true. The empty list has value the identity matrix.
QAlgorithms.Papers.Independent.Intakenext100.P82.initialVertices
The initial vertices form the subset of consisting exactly of the three vectors
QAlgorithms.Papers.Independent.Intakenext100.P82.lookup
For every finite ordered list of instructions and every configuration with optional natural-number control and four finite symbol stacks indexed by , this returns the first instruction in satisfying both of the following conditions: 's control contains that instruction's natural-number state, and, at each of the four indices, the stack's optional first symbol equals the instruction's specified optional symbol. An empty stack has no first symbol, so a specified absence matches exactly an empty stack. Each instruction also carries four actions, each either keep, pop, or push of a symbol from , and an optional natural-number next state; these fields do not affect matching. If no instruction matches, including when is empty or 's control is absent, the result is no instruction. All stack symbols belong to .
QAlgorithms.Papers.Independent.Intakenext100.P82.normalSymbols
For any record consisting of a Boolean , a finite list of syllables and , and an integer , this defines a list of symbols from : first if is true and otherwise, then the body with each replaced by and each replaced by , and finally . The body may be empty, in which case the resulting list has two symbols; no normalization condition is imposed on the body.
QAlgorithms.Papers.Independent.Intakenext100.P82.octahedronRotations
The set of octahedron rotations consists of all real matrices satisfying , , and , where and is the th coordinate vector. The last condition is equality of sets: the image of these six vectors under multiplication by is exactly the same set of six vectors.
QAlgorithms.Papers.Independent.Intakenext100.P82.octahedronVertices
The set of octahedron vertices consists of the vectors for which there is an index such that either and every other coordinate is zero, or and every other coordinate is zero. Thus this set is exactly , where is the th coordinate vector.
QAlgorithms.Papers.Independent.Intakenext100.P82.recursionValue
For every natural number , including zero, this defines a complex matrix for each tree of index : trees of index zero are leaves carrying triples with and a finite list over , and a tree of index has three ordered children of index . Set
and define
For a leaf carrying , its value is , where , , and ; the product for an empty list is . For a node with children , its value is
where denotes conjugate transpose. No normalization condition is imposed on the leaf lists by this definition.
QAlgorithms.Papers.Independent.Intakenext100.P82.sUnit
This defines an element of the group of invertible complex matrices whose underlying matrix is , with Boolean indices ordered false, true, and whose specified inverse is . Its inverse identities are and .
QAlgorithms.Papers.Independent.Intakenext100.P82.sphereGate
For every real number and every real triple , the complex matrix is defined by
Real scalars are viewed as complex scalars in this formula. There is no assumption that , and no restriction on . The square root is the real square root, which is zero for negative arguments; consequently, when , this definition gives .
QAlgorithms.Papers.Independent.Intakenext100.P82.syllableMatrix
The function assigns a complex matrix to each of the two symbols and . With rows and columns ordered as , and with the imaginary unit, its values are
QAlgorithms.Papers.Independent.Intakenext100.P82.syllableSymbols
For any finite list over the two-symbol alphabet , is the list of stack symbols in obtained by replacing every by and every by , preserving order and length. The empty list maps to the empty list.
QAlgorithms.Papers.Independent.Intakenext100.P82.syllableValue
For every finite list whose entries are the symbols or , is the complex matrix product , in the order of the list, where, in the coordinate order ,
and is the imaginary unit. For the empty list, the product is the identity matrix.
QAlgorithms.Papers.Independent.Intakenext100.P82.tile
For each integer , the tile indexed by is , where for , and denotes conjugate transpose. Here
and the matrices , in index order, are
QAlgorithms.Papers.Independent.Intakenext100.P82.tileInterior
For each integer , the tile interior indexed by is , where for , and denotes conjugate transpose. Here
and the matrices , in index order, are
QAlgorithms.Papers.Independent.Intakenext100.P82.tileVertices
The set of tile vertices consists of all vectors for which there exist an integer and a vector among , , and such that . Here for , denotes conjugate transpose,
and the matrices , in index order, are
QAlgorithms.Papers.Independent.Intakenext100.P82.unitSphere
The set consists exactly of the real triples satisfying
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.