Definitions for Exact synthesis of multiqubit Clifford+T circuits
DefinitionQAlgorithms_Papers_Independent_Intakethird100_P85The objects the formalized statements of Exact synthesis of multiqubit Clifford+T circuits (arXiv:1212.0506) are stated in. Each was checked against the paper by a blind read-back and a moderator.
omegaGate: The scalar generator of equation (1), PDF p.1, acts on zero wires.gateSet: Exactly H,S,CNOT,T and the eighth-root scalar, equation (1), PDF p.1.ScalarExponent: Natural denominator exponents, Definition 3, PDF p.2; also defined at zero.VectorExponent: Componentwise denominator validity, Definition 3, PDF p.2.MatrixExponent: Arbitrary-dimension matrix denominator validity, Definition 3, PDF p.2.LeastScalarExponent: Least natural exponent as a graph, Definition 3, PDF p.2; no off-domain fallback.LeastMatrixExponent: Least natural matrix exponent as a graph, Definition 3, PDF p.2.kResidue: The k-residue; statements always carry denominator validity, PDF p.3.residueConjugate: Conjugation pqrs -> rqps, equation (2) and §3.3, PDF p.2.residueNorm: Multiplication uses the quotient algebra, not pointwise multiplication, PDF p.3.TwiceReducible: Twice reducible means an image of multiplication by the residue of 2, PDF p.3.Dyadic: Real dyadic coefficients, Definition 1, PDF p.2.DyadicCoordinates: Unique omega-power coordinates of a D[omega] scalar, Definition 1, PDF p.2. Using coordinates as data avoids choosing a value outside the coefficient ring.dyadicValue: Dyadic scalar extension of the imported integer-coordinate evaluator, PDF p.2. The frozen evaluator uses ascending powers; Fin.rev supplies the paper's descending order.coordinateWeight: Squared weight, Definition 2, equation (4), PDF p.2.vectorNormSq: Squared vector norm, Definition 2, PDF p.2.twoLevel: Ordered two-coordinate block, §4, PDF p.3; callers provide distinct coordinates.LevelOp: The paper's actual one- and two-level operations, §4, PDF pp.3–4.levelMatrix: Exact operation matrices; omega is one-level, PDF pp.3–4.levelWordMatrix: The head acts first, with identity for the empty word, PDF p.4.inverseOp: An inverse operation expanded in the same alphabet, PDF pp.4–5.inverseWord: Chronological inverse of a reduction word, PDF p.5.liftHT: Lift a chronological H/T word onto distinct ordered rows, Lemma 4, PDF p.4.rowCandidates: Finite candidate words from the three cases of the row proof, PDF p.4. Printed HT^m becomes the chronological word T^m,H. Two such rounds suffice.rowWord: First successful row word in the proof's bounded candidate list, PDF p.4. This exact predicate search counts only output letters; no arithmetic cost is asserted.PassTrace: A single positive-exponent column pass from the inner induction, PDF p.4. Only matched irreducible pairs are processed; stopping means every entry is reducible.baseColumnWord: Swap to the target and correct its eighth-root phase, Lemma 5 base case, PDF p.4.ColumnTrace: The column proof's actual pass sequence and its base case, Lemma 5, PDF p.4.shiftOp: Lift a tail operation, fixing the first coordinate, Lemma 6, PDF p.4.MatrixTrace: Column elimination in the order of Lemma 6, PDF p.4, with §7's 3k tail allowance. The trace records reductions; inverseWord returns the factorization.indexedMatrix: Frozen most-significant-bit indexing, applied to an input operator, PDF p.7.qubitLevelMatrix: A level operation expressed on the qubit register, PDF pp.5,7.CompilationTrace: A gate-by-gate compilation trace with the same trailing clean helper, PDF pp.5,7. Each output segment is an actual elementary circuit, bounded by B*n gates.multiplyControlled: All controls are positive and precede the target wire, §5.2, PDF p.5.boundedOperators: Distinct phase-sensitive unitary operators cleared by k, §8, PDF p.7.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_CircuitResources
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P10
import Definitions.Def_QAlgorithms_Papers_Independent_Support21_P13
/-!
Giles and Selinger, arXiv:1212.0506v3, PDF pp.1–7.
Absolute phase is retained. Words are chronological (head first).
Only the pinned accepted definitions are imported from earlier papers.
The local traces record output operations, not arithmetic running time.
-/
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P85
open scoped Classical BigOperators
open QAlgorithms
open QAlgorithms.Papers.Independent.Gap48.P10
(InZomega InDomega Residue bits residue residueMultiply Reducible)
open QAlgorithms.Papers.Independent.Support21.P13
(synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)
local notation "omega" => QAlgorithms.gateT true true
local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)
/-- The scalar generator of equation (1), PDF p.1, acts on zero wires. -/
def omegaGate : Gate := ⟨0, fun _ _ => omega⟩
/-- Exactly H,S,CNOT,T and the eighth-root scalar, equation (1), PDF p.1. -/
def gateSet : Set Gate := cliffordTLibrary ∪ {omegaGate}
/-- Natural denominator exponents, Definition 3, PDF p.2; also defined at zero. -/
def ScalarExponent (t : ℂ) (k : ℕ) : Prop := InZomega (sqrtTwo ^ k * t)
/-- Componentwise denominator validity, Definition 3, PDF p.2. -/
def VectorExponent {ι : Type*} (u : ι → ℂ) (k : ℕ) : Prop :=
∀ i, ScalarExponent (u i) k
/-- Arbitrary-dimension matrix denominator validity, Definition 3, PDF p.2. -/
def MatrixExponent {ι : Type*} (U : Matrix ι ι ℂ) (k : ℕ) : Prop :=
∀ i j, ScalarExponent (U i j) k
/-- Least natural exponent as a graph, Definition 3, PDF p.2; no off-domain fallback. -/
def LeastScalarExponent (t : ℂ) (k : ℕ) : Prop :=
ScalarExponent t k ∧ ∀ l, ScalarExponent t l → k ≤ l
/-- Least natural matrix exponent as a graph, Definition 3, PDF p.2. -/
def LeastMatrixExponent {ι : Type*} (U : Matrix ι ι ℂ) (k : ℕ) : Prop :=
MatrixExponent U k ∧ ∀ l, MatrixExponent U l → k ≤ l
/-- The k-residue; statements always carry denominator validity, PDF p.3. -/
def kResidue (t : ℂ) (k : ℕ) : Residue := residue (sqrtTwo ^ k * t)
/-- Conjugation pqrs -> rqps, equation (2) and §3.3, PDF p.2. -/
def residueConjugate (x : Residue) : Residue := ![x 2, x 1, x 0, x 3]
/-- Multiplication uses the quotient algebra, not pointwise multiplication, PDF p.3. -/
def residueNorm (x : Residue) : Residue := residueMultiply (residueConjugate x) x
/-- Twice reducible means an image of multiplication by the residue of 2, PDF p.3. -/
def TwiceReducible (x : Residue) : Prop :=
∃ y : Residue, residueMultiply (bits 0) y = x
/-- Real dyadic coefficients, Definition 1, PDF p.2. -/
def Dyadic (a : ℝ) : Prop := ∃ z : ℤ, ∃ k : ℕ, a = (z : ℝ) / 2 ^ k
/-- Unique omega-power coordinates of a D[omega] scalar, Definition 1, PDF p.2.
Using coordinates as data avoids choosing a value outside the coefficient ring. -/
abbrev DyadicCoordinates := {a : Fin 4 → ℝ // ∀ i, Dyadic (a i)}
/-- Dyadic scalar extension of the imported integer-coordinate evaluator, PDF p.2.
The frozen evaluator uses ascending powers; Fin.rev supplies the paper's descending order. -/
def dyadicValue (a : Fin 4 → ℝ) : ℂ :=
∑ j : Fin 4, (a j : ℂ) *
coordinateValue (fun i => if i = Fin.rev j then (1 : ℤ) else 0)
/-- Squared weight, Definition 2, equation (4), PDF p.2. -/
def coordinateWeight (a : Fin 4 → ℝ) : ℝ := ∑ j, a j ^ 2
/-- Squared vector norm, Definition 2, PDF p.2. -/
def vectorNormSq {ι : Type*} [Fintype ι] (u : ι → ℂ) : ℝ :=
∑ i, Complex.normSq (u i)
/-- Ordered two-coordinate block, §4, PDF p.3; callers provide distinct coordinates. -/
def twoLevel {d : ℕ} (M : Matrix Bool Bool ℂ) (j l : Fin d) :
Matrix (Fin d) (Fin d) ℂ :=
fun a b =>
if a = j then (if b = j then M false false else if b = l then M false true else 0)
else if a = l then (if b = j then M true false else if b = l then M true true else 0)
else if a = b then 1 else 0
/-- The paper's actual one- and two-level operations, §4, PDF pp.3–4. -/
inductive LevelOp (d : ℕ) where
| x (j l : Fin d) (distinct : j ≠ l)
| h (j l : Fin d) (distinct : j ≠ l)
| t (j l : Fin d) (distinct : j ≠ l)
| phase (j : Fin d)
/-- Exact operation matrices; omega is one-level, PDF pp.3–4. -/
def levelMatrix {d : ℕ} : LevelOp d → Matrix (Fin d) (Fin d) ℂ
| .x j l _ => twoLevel pauliX j l
| .h j l _ => twoLevel hadamard j l
| .t j l _ => twoLevel gateT j l
| .phase j => Matrix.diagonal (fun i => if i = j then omega else 1)
/-- The head acts first, with identity for the empty word, PDF p.4. -/
def levelWordMatrix {d : ℕ} (w : List (LevelOp d)) : Matrix (Fin d) (Fin d) ℂ :=
(w.map levelMatrix).reverse.prod
/-- An inverse operation expanded in the same alphabet, PDF pp.4–5. -/
def inverseOp {d : ℕ} : LevelOp d → List (LevelOp d)
| .x j l h => [.x j l h]
| .h j l h => [.h j l h]
| .t j l h => List.replicate 7 (.t j l h)
| .phase j => List.replicate 7 (.phase j)
/-- Chronological inverse of a reduction word, PDF p.5. -/
def inverseWord {d : ℕ} (w : List (LevelOp d)) : List (LevelOp d) :=
w.reverse.flatMap inverseOp
/-- Lift a chronological H/T word onto distinct ordered rows, Lemma 4, PDF p.4. -/
def liftHT {d : ℕ} (j l : Fin d) (h : j ≠ l) (w : List HTLetter) : List (LevelOp d) :=
w.map (fun a => match a with | .h => .h j l h | .t => .t j l h)
/-- Finite candidate words from the three cases of the row proof, PDF p.4.
Printed HT^m becomes the chronological word T^m,H. Two such rounds suffice. -/
def rowCandidates : List (List HTLetter) :=
let rounds := (List.range 8).map (fun m => List.replicate m HTLetter.t ++ [.h])
[[]] ++ rounds ++ rounds.flatMap (fun a => rounds.map (fun b => a ++ b))
/-- First successful row word in the proof's bounded candidate list, PDF p.4.
This exact predicate search counts only output letters; no arithmetic cost is asserted. -/
def rowWord (u : Bool → ℂ) (k : ℕ) : List HTLetter :=
((rowCandidates.find? (fun w => decide
(VectorExponent ((htWordMatrix w).mulVec u) (k - 1)))).getD [])
/-- A single positive-exponent column pass from the inner induction, PDF p.4.
Only matched irreducible pairs are processed; stopping means every entry is reducible. -/
inductive PassTrace {d : ℕ} (k : ℕ) :
(Fin d → ℂ) → List (LevelOp d) → Prop where
| done (u : Fin d → ℂ) (stop : ∀ i, Reducible (kResidue (u i) k)) :
PassTrace k u []
| pair (u : Fin d → ℂ) (j l : Fin d) (h : j ≠ l)
(active : ¬ Reducible (kResidue (u j) k))
(matched : residueNorm (kResidue (u j) k) = residueNorm (kResidue (u l) k))
(rest : List (LevelOp d))
(next : PassTrace k
((levelWordMatrix (liftHT j l h (rowWord (fun b => if b then u l else u j) k))).mulVec u)
rest) :
PassTrace k u (liftHT j l h (rowWord (fun b => if b then u l else u j) k) ++ rest)
/-- Swap to the target and correct its eighth-root phase, Lemma 5 base case, PDF p.4. -/
def baseColumnWord {d : ℕ} (first j : Fin d) (m : Fin 8) : List (LevelOp d) :=
(if h : first = j then [] else [.x first j h]) ++ List.replicate m.val (.phase first)
/-- The column proof's actual pass sequence and its base case, Lemma 5, PDF p.4. -/
inductive ColumnTrace {d : ℕ} (first : Fin d) :
(Fin d → ℂ) → ℕ → List (LevelOp d) → Prop where
| base (j : Fin d) (m : Fin 8) :
ColumnTrace first (fun i => if i = j then omega ^ (8 - m.val) else 0) 0
(baseColumnWord first j m)
| step (u : Fin d → ℂ) (k : ℕ) (pass rest : List (LevelOp d))
(onePass : PassTrace (k + 1) u pass)
(next : ColumnTrace first ((levelWordMatrix pass).mulVec u) k rest) :
ColumnTrace first u (k + 1) (pass ++ rest)
/-- Lift a tail operation, fixing the first coordinate, Lemma 6, PDF p.4. -/
def shiftOp {d : ℕ} : LevelOp d → LevelOp (d + 1)
| .x j l h => .x j.succ l.succ (fun e => h (Fin.succ_injective d e))
| .h j l h => .h j.succ l.succ (fun e => h (Fin.succ_injective d e))
| .t j l h => .t j.succ l.succ (fun e => h (Fin.succ_injective d e))
| .phase j => .phase j.succ
/-- Column elimination in the order of Lemma 6, PDF p.4, with §7's 3k tail allowance.
The trace records reductions; inverseWord returns the factorization. -/
inductive MatrixTrace : {d : ℕ} → Matrix (Fin d) (Fin d) ℂ → ℕ →
List (LevelOp d) → Prop where
| empty (U : Matrix (Fin 0) (Fin 0) ℂ) (k : ℕ) : MatrixTrace U k []
| step {d : ℕ} (U : Matrix (Fin (d + 1)) (Fin (d + 1)) ℂ) (k : ℕ)
(pass : List (LevelOp (d + 1))) (rest : List (LevelOp d))
(column : ColumnTrace 0 (fun i => U i 0) k pass)
(tail : MatrixTrace ((levelWordMatrix pass * U).submatrix Fin.succ Fin.succ) (3 * k) rest) :
MatrixTrace U k (pass ++ rest.map shiftOp)
/-- Frozen most-significant-bit indexing, applied to an input operator, PDF p.7. -/
def indexedMatrix {n : ℕ} (U : Matrix (Qubits n) (Qubits n) ℂ) :
Matrix (Fin (2 ^ n)) (Fin (2 ^ n)) ℂ :=
U.submatrix (bitsEquivFin n).symm (bitsEquivFin n).symm
/-- A level operation expressed on the qubit register, PDF pp.5,7. -/
def qubitLevelMatrix {n : ℕ} (g : LevelOp (2 ^ n)) : Matrix (Qubits n) (Qubits n) ℂ :=
(levelMatrix g).submatrix (bitsEquivFin n) (bitsEquivFin n)
/-- A gate-by-gate compilation trace with the same trailing clean helper, PDF pp.5,7.
Each output segment is an actual elementary circuit, bounded by B*n gates. -/
inductive CompilationTrace (B n : ℕ) : List (LevelOp (2 ^ n)) →
Circuit gateSet (n + 1) → Prop where
| nil : CompilationTrace B n [] []
| cons (g : LevelOp (2 ^ n)) (w : List (LevelOp (2 ^ n)))
(segment rest : Circuit gateSet (n + 1))
(exactSegment : ImplementsWithCleanAncillas segment.unitary (qubitLevelMatrix g))
(sizeSegment : segment.size ≤ B * n)
(next : CompilationTrace B n w rest) :
CompilationTrace B n (g :: w) (segment ++ rest)
/-- All controls are positive and precede the target wire, §5.2, PDF p.5. -/
def multiplyControlled (r : ℕ) (M : Matrix Bool Bool ℂ) :
Matrix (Qubits (r + 1)) (Qubits (r + 1)) ℂ :=
fun y z =>
if (∀ i : Fin r, y i.castSucc = z i.castSucc) then
if (∀ i : Fin r, z i.castSucc = true) then M (y (Fin.last r)) (z (Fin.last r))
else if y (Fin.last r) = z (Fin.last r) then 1 else 0
else 0
/-- Distinct phase-sensitive unitary operators cleared by k, §8, PDF p.7. -/
def boundedOperators (n k : ℕ) :=
{U : Matrix (Qubits n) (Qubits n) ℂ //
U ∈ Matrix.unitaryGroup (Qubits n) ℂ ∧ MatrixExponent U k}
example (t : ℂ) : ScalarExponent t 0 ↔ InZomega t := by simp [ScalarExponent]
example : Dyadic 0 := ⟨0, 0, by norm_num⟩
example {d : ℕ} (M : Matrix Bool Bool ℂ) (j l : Fin d) (h : j ≠ l) :
twoLevel M j l j l = M false true := by simp [twoLevel, h, Ne.symm h]
example {d : ℕ} (j : Fin d) : levelMatrix (LevelOp.phase j) j j = omega := by
simp [levelMatrix]
example {d : ℕ} (first : Fin d) (m : Fin 8) :
baseColumnWord first first m = List.replicate m.val (.phase first) := by
simp [baseColumnWord]
example : omegaGate.arity = 0 := rfl
example : levelWordMatrix ([] : List (LevelOp 0)) = 1 := rfl
example : inverseWord ([] : List (LevelOp 0)) = [] := rfl
example : residueConjugate (bits 1) = bits 1 := by
ext i
fin_cases i <;> norm_num [residueConjugate, bits]
example : dyadicValue (fun _ => 0) = 0 := by simp [dyadicValue]
example : coordinateWeight (fun _ => 0) = 0 := by simp [coordinateWeight]
example : vectorNormSq (fun _ : Fin 0 => (0 : ℂ)) = 0 := by simp [vectorNormSq]
example : ([] : List HTLetter) ∈ rowCandidates := by simp [rowCandidates]
example (u : Fin 0 → ℂ) (k : ℕ) : PassTrace k u [] :=
.done u (fun i => Fin.elim0 i)
example (U : Matrix (Fin 0) (Fin 0) ℂ) (k : ℕ) : MatrixTrace U k [] := .empty U k
example (B n : ℕ) : CompilationTrace B n [] [] := .nil
example (M : Matrix Bool Bool ℂ) (y z : Qubits 1) :
multiplyControlled 0 M y z = M (y 0) (z 0) := by simp [multiplyControlled]
end QAlgorithms.Papers.Independent.Intakethird100.P85
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Intakethird100.P85.ColumnTrace
For every natural dimension and distinguished index , this defines a relation between a vector , a natural number , and a finite chronological list of coordinate operations. Write , , and let denote the supplied complex constant sqrtTwo, whose value is not specified here. At index , a trace exists by the base construction for every and : its vector has entry at and zero elsewhere, and its operation list exchanges with if they differ, then applies copies of the phase at . At index , a trace consists of a pass on at exponent , followed by a trace at index for the vector obtained by applying that pass; its list is the concatenation of the pass list and the subsequent list. A pass at exponent means a finite sequence of the following pair steps ending when all coordinate residues are reducible: express an element of in the ordered basis and reduce its integer coefficients modulo , assigning residue to numbers outside ; use the residue of for coordinate of the current vector . On residue vectors put and ; a residue is reducible if it equals for some . A pair step chooses distinct coordinates with the first residue nonreducible and with equal products for their two residues. On , it selects the first word from , the words for , and all their pairwise concatenations in nested order, whose chronological matrix produces coordinates lying in , meaning explicitly that multiplication by puts each coordinate in ; if none qualifies, it selects the empty word. It applies the selected operations on these two coordinates, with the identity elsewhere, and records them. Only traces generated by these base and step rules belong to the relation. In particular, no normalization, least-exponent, or successful-reduction assertion is an additional condition, and supplies no distinguished index.
QAlgorithms.Papers.Independent.Intakethird100.P85.CompilationTrace
For any natural numbers , this defines a relation between a finite list of coordinate operations on coordinates and a circuit on Boolean wires. The permitted circuit gates are Hadamard, , , controlled-NOT, and a zero-wire gate with scalar matrix entry . Each gate application chooses an injective ordered placement of its wires; its embedded matrix agrees with that gate on the selected wires and has zero entries between strings differing on any other wire. Circuit matrices multiply in reverse list order, and an empty circuit has matrix . The empty operation list is related to the empty circuit. A nonempty list is related to a circuit obtained by concatenating a segment and a remaining circuit if the remaining circuit is recursively related to , the segment contains at most gate applications, and, for every vector on wires, the segment sends exactly to . Here is obtained by labeling coordinate with its length- binary expansion: operations act on their distinct selected ordered coordinates and fix the others, while a phase operation multiplies its selected coordinate by . These finite recursive rules are the entire relation; no existence assertion for an arbitrary operation list is included. The extra wire must return to after each segment. If or , the size bound forces every segment to be empty.
QAlgorithms.Papers.Independent.Intakethird100.P85.Dyadic
For a real number , this predicate means that there exist an integer and a natural number such that . The exponent may be , and the numerator may be positive, negative, or zero; no reduced-form condition is imposed.
QAlgorithms.Papers.Independent.Intakethird100.P85.DyadicCoordinates
This is the type of real coordinate vectors such that, for every , there exist an integer and a natural number with . The numerator and exponent may depend on , and is allowed.
QAlgorithms.Papers.Independent.Intakethird100.P85.LeastMatrixExponent
For any type , any complex matrix indexed by , and any natural number , this predicate means that every entry of can be written as with integer coefficients, and that for every natural number , if every entry of has such an expression, then . Here coefficients may vary between entries, , and is the complex constant named sqrtTwo, whose definition is not supplied. There are no finiteness, nonemptiness, or unitarity assumptions on ; if the index type is empty, or if , the predicate holds exactly when .
QAlgorithms.Papers.Independent.Intakethird100.P85.LeastScalarExponent
For a complex number and a natural number , this predicate means that has an expression with integer coefficients, and that for every natural number , if has such an expression, then . Here , and is the complex constant named sqrtTwo, whose definition is not supplied. Thus the minimum is taken over natural exponents, including ; for , this predicate holds exactly when .
QAlgorithms.Papers.Independent.Intakethird100.P85.LevelOp
For each natural number , this defines a type of formal operations with four distinct constructors: an operation, an operation, or a operation, each carrying ordered indices and a proof that ; or a phase operation carrying a single index in the same range. These constructors specify formal data without asserting matrix properties. For there are no such operations; for only the phase constructor can be used.
QAlgorithms.Papers.Independent.Intakethird100.P85.MatrixExponent
For any type , any complex matrix with rows and columns indexed by , and any natural number , this predicate means that for every there exist integers , allowed to depend on , such that , where and is the complex constant named sqrtTwo, whose definition is not supplied. The index type need not be finite or nonempty, and no unitarity assumption is made; for an empty index type the predicate holds for every , including .
QAlgorithms.Papers.Independent.Intakethird100.P85.MatrixTrace
This defines, for every natural dimension , complex matrix , natural number , and finite list of coordinate operations, an inductively generated relation. In dimension , every matrix and every has a trace with list . In dimension , choose a list tracing the first column toward distinguished coordinate at index , and a list tracing the matrix with entries at index , where applies the operations in chronological order. The resulting list is followed by with every coordinate index increased by . Here the required column trace has the following full meaning: at index , its vector must have a single nonzero entry at some coordinate , with and , and its list exchanges with the distinguished coordinate if necessary, then applies phases there; at index , its list is a pass at exponent followed by a column trace at index for the transformed vector. To define a pass, put , let be the supplied complex constant sqrtTwo, whose value is not specified here, and reduce the integer coefficients of an element of in the basis modulo , using residue outside . For residues set , , and call reducible if for some . A pass at exponent repeatedly chooses distinct coordinates whose residues after multiplication by have equal , requiring the first residue to be nonreducible. For that ordered pair, it searches , then for , then all pairwise concatenations of those eight words in nested order, selecting the first word whose chronological matrix makes both coordinates integral after multiplication by , or if none does. It records and applies this word on the pair, fixing other coordinates, and may stop precisely when every coordinate residue is reducible. All passes and recursive constructions must be finite. Coordinate operations are two-level operations on distinct indices or a single-coordinate phase . No unitarity, normalization, or denominator bound on the input matrix is separately required by this relation; is included, and multiplication of that index by still gives .
QAlgorithms.Papers.Independent.Intakethird100.P85.PassTrace
For every natural dimension and natural number , this defines a relation between vectors and finite lists of operations on their coordinates. Here an or operation on distinct ordered indices applies that two-dimensional matrix to coordinates , with corresponding to , and acts as the identity elsewhere; a phase operation at multiplies that coordinate by . A list acts in its listed chronological order. The residue tests used in the relation are defined as follows: let , let be the supplied complex constant sqrtTwo, whose value is not specified here, and let be the coefficients modulo of when , with otherwise. For residue vectors define , define , and call reducible when for some residue vector . Starting from , a trace is built by finitely many pair steps, followed by a stopping step. A pair step chooses distinct such that is not reducible and . It forms the two-coordinate vector , searches the ordered candidate list consisting of , then for , then all concatenations of two such words in nested list order, and selects the first word whose chronological matrix sends this vector to one whose coordinates, multiplied by , lie in ; if none qualifies, it selects . That word is lifted to operations on , appended to the trace, and applied to the current vector; the process then continues at the same . Stopping contributes no operations and is allowed precisely when every coordinate residue is reducible. These are the only ways to construct the relation. No normalization, integrality, or progress condition is imposed beyond these tests; in particular, a selected pair word may be empty. The case uses exponent in the candidate test, and for the stopping condition is vacuous and only the empty operation list is related.
QAlgorithms.Papers.Independent.Intakethird100.P85.ScalarExponent
For a complex number and a natural number , including , this predicate means that there exist integers such that , where and denotes the complex constant named sqrtTwo, whose definition is not included in the supplied code. This requires only such a representation at exponent , without requiring to be least; is allowed.
QAlgorithms.Papers.Independent.Intakethird100.P85.TwiceReducible
For a vector , this predicate means that there exists such that, for every , , where is the reduction modulo of . Every is zero, so this predicate is equivalent to ; when , every vector satisfies the required equation.
QAlgorithms.Papers.Independent.Intakethird100.P85.VectorExponent
For any type , any function , and any natural number , this predicate means that for every there exist integers , allowed to depend on , such that , where and is the complex constant named sqrtTwo, whose definition is not supplied. No finiteness or nonemptiness assumption is imposed on ; if is empty, the predicate holds for every , and is permitted.
QAlgorithms.Papers.Independent.Intakethird100.P85.baseColumnWord
For any natural dimension , indices , and integer , this defines the following list of coordinate operations: if , begin with the empty list; otherwise begin with the single operation that exchanges coordinates and and fixes all other coordinates. Then append exactly phase operations at coordinate , each represented by the diagonal matrix with entry at that coordinate and elsewhere. Thus for no phase operations are appended, and when also the result is empty. There are no choices of the required indices when .
QAlgorithms.Papers.Independent.Intakethird100.P85.boundedOperators
For any natural numbers , this defines the type of complex matrices , with rows and columns indexed by Boolean strings of length , equipped with the two properties and for every pair of strings . Here , membership in means being expressible as for integers , and denotes the complex constant named sqrtTwo, whose value is not specified in the supplied definitions. The exponent need not be the least exponent with this property. The case requires the entries themselves to lie in ; gives a matrix rather than an empty matrix.
QAlgorithms.Papers.Independent.Intakethird100.P85.coordinateWeight
For any real coordinate vector , this defines its coordinate weight to be the real number . No restriction on the coordinates is imposed.
QAlgorithms.Papers.Independent.Intakethird100.P85.dyadicValue
For any real coordinate vector , this defines the complex number
The coordinates are arbitrary real numbers; no dyadic-coordinate hypothesis is imposed.
QAlgorithms.Papers.Independent.Intakethird100.P85.gateSet
This defines the set consisting of the one-qubit gates with matrices , , and , the two-qubit gate sending a basis label to , and the zero-qubit gate with matrix . Here the one-qubit matrix order is false, true, and denotes exclusive or.
QAlgorithms.Papers.Independent.Intakethird100.P85.indexedMatrix
For every natural number and complex matrix indexed in both directions by Boolean strings of length , this defines a matrix by relabeling its rows and columns with the integers . Explicitly, its entry is , where is the unique Boolean string satisfying , and similarly for . No property of is assumed. For , there is one empty Boolean string and one integer index, so the result is still a matrix.
QAlgorithms.Papers.Independent.Intakethird100.P85.inverseOp
For every natural number , this maps a formal operation to a list of formal operations as follows: an operation on distinct ordered indices gives the singleton list containing that same operation; an operation on distinct ordered indices gives the singleton list containing that same operation; a operation on distinct ordered indices gives seven copies of that same operation; and a phase operation at an index gives seven copies of that same phase operation. All indices and the supplied distinctness proofs are retained. For , there are no input operations.
QAlgorithms.Papers.Independent.Intakethird100.P85.inverseWord
For every natural number and every finite list of formal operations on indices, this reverses the list and then replaces each operation by a list: an or operation becomes one copy of itself, while a or phase operation becomes seven copies of itself. An , , or operation carries ordered indices together with a proof that they are distinct, and a phase operation carries one index ; these data are preserved in every copy. The replacement lists are concatenated in the reversed order. The empty input list gives the empty output list, and it is the only possible input list when .
QAlgorithms.Papers.Independent.Intakethird100.P85.kResidue
For a complex number and a natural number , this defines a vector of four elements of as follows: set , where is the complex constant named sqrtTwo, whose definition is not supplied, and let . If there exists an integer tuple satisfying , use a tuple selected by classical choice and return its coordinates reduced modulo ; if no such tuple exists, return the zero vector. The definition applies to every and every , including , without an assumption that the representation exists.
QAlgorithms.Papers.Independent.Intakethird100.P85.levelMatrix
For every natural number , this assigns a complex matrix to each formal operation: an , , or operation on distinct ordered indices receives, respectively, the block
on rows and columns ordered as , with the identity on the remaining indices and zero entries connecting the block to those indices. A phase operation at receives the diagonal matrix whose entry at is and whose other diagonal entries are . When , there is no formal operation to which this assignment can be applied.
QAlgorithms.Papers.Independent.Intakethird100.P85.levelWordMatrix
For every natural number and every finite list of formal operations on indices, this defines the matrix product . Here an , , or operation carries distinct ordered indices and places, respectively,
on those indices, with the identity elsewhere and zero connecting entries; for a phase operation at , is diagonal with entry at and elsewhere. The empty list gives the identity matrix, including when .
QAlgorithms.Papers.Independent.Intakethird100.P85.liftHT
For every natural number , every pair of indices , every supplied proof that , and every finite word over the two formal symbols and , this returns the list obtained by replacing each symbol with the formal operation on ordered indices and each symbol with the formal operation on those same indices, using the supplied distinctness proof throughout. The order and length of the word are preserved, and the empty word gives the empty list. Such distinct indices exist only when .
QAlgorithms.Papers.Independent.Intakethird100.P85.multiplyControlled
For every natural number and arbitrary complex matrix indexed by Boolean values, this defines a matrix on Boolean strings of length . Its entry at row , column is if and differ in any of their first coordinates. If those coordinates agree and all first coordinates of are , the entry is . If those coordinates agree but are not all , the entry is when , and otherwise. No unitarity assumption on is imposed. For , both conditions over the first coordinates are vacuous, so the defined matrix is simply on the sole Boolean coordinate.
QAlgorithms.Papers.Independent.Intakethird100.P85.omegaGate
This defines a gate of arity whose matrix has every entry equal to . There is exactly one zero-bit string, so its matrix is the matrix .
QAlgorithms.Papers.Independent.Intakethird100.P85.qubitLevelMatrix
For every natural number and coordinate operation on coordinates, this defines a matrix indexed by Boolean strings of length , with entry , where . Here is the identity outside the selected coordinates: an or operation selects distinct ordered indices and places the corresponding two-dimensional matrix on those coordinates, with corresponding to and to ; a phase operation at is diagonal with entry at and elsewhere. Thus this definition relabels a coordinate-operation matrix using Boolean strings. When , there is only one coordinate, so only the phase kind of operation is available.
QAlgorithms.Papers.Independent.Intakethird100.P85.residueConjugate
For any vector , this defines the vector , exchanging coordinates and and leaving coordinates and unchanged.
QAlgorithms.Papers.Independent.Intakethird100.P85.residueNorm
For any vector , this defines a vector whose coordinate is , where , the indicator is when its condition holds and otherwise, and all sums and products take place in .
QAlgorithms.Papers.Independent.Intakethird100.P85.rowCandidates
This defines an ordered list of words over the two formal symbols and . For , let be the word consisting of copies of followed by one , so . The list consists first of the empty word, then , and then all concatenations , with running from to and, for each fixed , running from to . Thus the list has entries.
QAlgorithms.Papers.Independent.Intakethird100.P85.rowWord
For any function and natural number , this defines a word in the letters . Put , , and let denote the complex constant named sqrtTwo, whose value is not specified in the supplied definitions. For a word , write , where is the Hadamard or matrix corresponding to , and . Search, in order, the following list of 73 candidate words: the empty word; the eight words , for , where this notation denotes a list of letters followed by ; and all concatenations of two such words, ordered first by the first word and then by the second. Return the first candidate for which every coordinate of belongs to . If no candidate satisfies this condition, return the empty word. Thus the empty output can indicate either a successful first candidate or failure to find any candidate; is included, and its tested exponent is . No normalization or denominator hypothesis on is required.
QAlgorithms.Papers.Independent.Intakethird100.P85.shiftOp
For every natural number , this maps an operation on coordinates to an operation on coordinates by increasing every coordinate index by . An or operation on distinct ordered indices becomes the same operation on ; a phase operation at becomes a phase operation at . The two-coordinate operations apply the corresponding Pauli , Hadamard, or matrix and are the identity elsewhere, while a phase operation multiplies its selected coordinate by . Distinctness is preserved, and the newly introduced coordinate is fixed. When , there are no operations to which this map can be applied.
QAlgorithms.Papers.Independent.Intakethird100.P85.twoLevel
For any natural number , any complex matrix with rows and columns indexed by , and any indices , this defines a complex matrix by the following ordered cases:
There is no assumption that : if , the result is diagonal with entry at and at every other diagonal position. No unitarity hypothesis on is imposed. For , no indices exist.
QAlgorithms.Papers.Independent.Intakethird100.P85.vectorNormSq
For any type equipped with a finite enumeration and any function , this defines the real number
The type may be empty, in which case the sum is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.