Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Exact synthesis of multiqubit Clifford+T circuits

Definition
QAlgorithms_Papers_Independent_Intakethird100_P85

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The 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.
Definition code
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
Source
Exact synthesis of multiqubit Clifford+T circuits, arXiv:1212.0506v3, https://arxiv.org/abs/1212.0506v3
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 ddd and distinguished index first<d\mathrm{first}<dfirst<d, this defines a relation between a vector u∈Cdu\in\mathbb C^du∈Cd, a natural number kkk, and a finite chronological list of coordinate operations. Write ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4, O=Z[ω]\mathcal O=\mathbb Z[\omega]O=Z[ω], and let sss denote the supplied complex constant sqrtTwo, whose value is not specified here. At index 000, a trace exists by the base construction for every j<dj<dj<d and m∈{0,…,7}m\in\{0,\ldots,7\}m∈{0,…,7}: its vector has entry ω8−m\omega^{8-m}ω8−m at jjj and zero elsewhere, and its operation list exchanges first\mathrm{first}first with jjj if they differ, then applies mmm copies of the phase ω\omegaω at first\mathrm{first}first. At index k+1k+1k+1, a trace consists of a pass on uuu at exponent k+1k+1k+1, followed by a trace at index kkk 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 qqq means a finite sequence of the following pair steps ending when all coordinate residues are reducible: express an element of O\mathcal OO in the ordered basis (ω3,ω2,ω,1)(\omega^3,\omega^2,\omega,1)(ω3,ω2,ω,1) and reduce its integer coefficients modulo 222, assigning residue 000 to numbers outside O\mathcal OO; use the residue of sqvis^qv_isqvi​ for coordinate iii of the current vector vvv. On residue vectors put (a∗b)ℓ=∑p,t=031p+t≡ℓ+3(mod4)apbt(a*b)_\ell=\sum_{p,t=0}^3\mathbf1_{p+t\equiv\ell+3\pmod4}a_pb_t(a∗b)ℓ​=∑p,t=03​1p+t≡ℓ+3(mod4)​ap​bt​ and aˉ=(a2,a1,a0,a3)\bar a=(a_2,a_1,a_0,a_3)aˉ=(a2​,a1​,a0​,a3​); a residue is reducible if it equals (1,0,1,0)∗b(1,0,1,0)*b(1,0,1,0)∗b for some bbb. A pair step chooses distinct coordinates j,lj,lj,l with the first residue nonreducible and with equal products aˉ∗a\bar a*aaˉ∗a for their two residues. On (vj,vl)(v_j,v_l)(vj​,vl​), it selects the first word from [][][], the words TmHT^mHTmH for m=0,…,7m=0,\ldots,7m=0,…,7, and all their pairwise concatenations in nested order, whose chronological matrix produces coordinates lying in s−max⁡(q−1,0)Os^{-\max(q-1,0)}\mathcal Os−max(q−1,0)O, meaning explicitly that multiplication by smax⁡(q−1,0)s^{\max(q-1,0)}smax(q−1,0) puts each coordinate in O\mathcal OO; if none qualifies, it selects the empty word. It applies the selected H,TH,TH,T 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 d=0d=0d=0 supplies no distinguished index.

QAlgorithms.Papers.Independent.Intakethird100.P85.CompilationTrace

For any natural numbers B,nB,nB,n, this defines a relation between a finite list of coordinate operations on 2n2^n2n coordinates and a circuit on n+1n+1n+1 Boolean wires. The permitted circuit gates are Hadamard, S=diag⁡(1,i)S=\operatorname{diag}(1,i)S=diag(1,i), T=diag⁡(1,ω)T=\operatorname{diag}(1,\omega)T=diag(1,ω), controlled-NOT, and a zero-wire gate with scalar matrix entry ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4. 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 III. The empty operation list is related to the empty circuit. A nonempty list g::wg::wg::w is related to a circuit obtained by concatenating a segment and a remaining circuit if the remaining circuit is recursively related to www, the segment contains at most BnBnBn gate applications, and, for every vector ψ\psiψ on nnn wires, the segment sends ψ⊗∣0⟩\psi\otimes|0\rangleψ⊗∣0⟩ exactly to Q(g)ψ⊗∣0⟩Q(g)\psi\otimes|0\rangleQ(g)ψ⊗∣0⟩. Here Q(g)Q(g)Q(g) is obtained by labeling coordinate jjj with its length-nnn binary expansion: X,H,TX,H,TX,H,T operations act on their distinct selected ordered coordinates and fix the others, while a phase operation multiplies its selected coordinate by ω\omegaω. These finite recursive rules are the entire relation; no existence assertion for an arbitrary operation list is included. The extra wire must return to 000 after each segment. If B=0B=0B=0 or n=0n=0n=0, the size bound forces every segment to be empty.

QAlgorithms.Papers.Independent.Intakethird100.P85.Dyadic

For a real number aaa, this predicate means that there exist an integer zzz and a natural number kkk such that a=z/2ka=z/2^ka=z/2k. The exponent may be 000, 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 a=(a0,a1,a2,a3)a=(a_0,a_1,a_2,a_3)a=(a0​,a1​,a2​,a3​) such that, for every i∈{0,1,2,3}i\in\{0,1,2,3\}i∈{0,1,2,3}, there exist an integer zzz and a natural number kkk with ai=z/2ka_i=z/2^kai​=z/2k. The numerator and exponent may depend on iii, and k=0k=0k=0 is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P85.LeastMatrixExponent

For any type ι\iotaι, any complex matrix UUU indexed by ι×ι\iota\times\iotaι×ι, and any natural number kkk, this predicate means that every entry of skUs^k UskU can be written as a0ω3+a1ω2+a2ω+a3a_0\omega^3+a_1\omega^2+a_2\omega+a_3a0​ω3+a1​ω2+a2​ω+a3​ with integer coefficients, and that for every natural number ℓ\ellℓ, if every entry of sℓUs^\ell UsℓU has such an expression, then k≤ℓk\leq\ellk≤ℓ. Here coefficients may vary between entries, ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4, and sss is the complex constant named sqrtTwo, whose definition is not supplied. There are no finiteness, nonemptiness, or unitarity assumptions on UUU; if the index type is empty, or if U=0U=0U=0, the predicate holds exactly when k=0k=0k=0.

QAlgorithms.Papers.Independent.Intakethird100.P85.LeastScalarExponent

For a complex number ttt and a natural number kkk, this predicate means that skts^k tskt has an expression a0ω3+a1ω2+a2ω+a3a_0\omega^3+a_1\omega^2+a_2\omega+a_3a0​ω3+a1​ω2+a2​ω+a3​ with integer coefficients, and that for every natural number ℓ\ellℓ, if sℓts^\ell tsℓt has such an expression, then k≤ℓk\leq\ellk≤ℓ. Here ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4, and sss is the complex constant named sqrtTwo, whose definition is not supplied. Thus the minimum is taken over natural exponents, including 000; for t=0t=0t=0, this predicate holds exactly when k=0k=0k=0.

QAlgorithms.Papers.Independent.Intakethird100.P85.LevelOp

For each natural number ddd, this defines a type of formal operations with four distinct constructors: an xxx operation, an hhh operation, or a ttt operation, each carrying ordered indices j,l∈{0,…,d−1}j,l\in\{0,\ldots,d-1\}j,l∈{0,…,d−1} and a proof that j≠lj\ne lj=l; or a phase operation carrying a single index jjj in the same range. These constructors specify formal data without asserting matrix properties. For d=0d=0d=0 there are no such operations; for d=1d=1d=1 only the phase constructor can be used.

QAlgorithms.Papers.Independent.Intakethird100.P85.MatrixExponent

For any type ι\iotaι, any complex matrix UUU with rows and columns indexed by ι\iotaι, and any natural number kkk, this predicate means that for every i,j∈ιi,j\in\iotai,j∈ι there exist integers a0,a1,a2,a3a_0,a_1,a_2,a_3a0​,a1​,a2​,a3​, allowed to depend on i,ji,ji,j, such that skUij=a0ω3+a1ω2+a2ω+a3s^k U_{ij}=a_0\omega^3+a_1\omega^2+a_2\omega+a_3skUij​=a0​ω3+a1​ω2+a2​ω+a3​, where ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4 and sss 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 kkk, including 000.

QAlgorithms.Papers.Independent.Intakethird100.P85.MatrixTrace

This defines, for every natural dimension ddd, complex d×dd\times dd×d matrix UUU, natural number kkk, and finite list www of coordinate operations, an inductively generated relation. In dimension 000, every matrix and every kkk has a trace with list [][][]. In dimension d+1d+1d+1, choose a list ppp tracing the first column (Ui0)i(U_{i0})_i(Ui0​)i​ toward distinguished coordinate 000 at index kkk, and a list rrr tracing the d×dd\times dd×d matrix with entries (W(p)U)i+1,j+1(W(p)U)_{i+1,j+1}(W(p)U)i+1,j+1​ at index 3k3k3k, where W(p)W(p)W(p) applies the operations in chronological order. The resulting list is ppp followed by rrr with every coordinate index increased by 111. Here the required column trace has the following full meaning: at index 000, its vector must have a single nonzero entry ω8−m\omega^{8-m}ω8−m at some coordinate jjj, with ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4 and m∈{0,…,7}m\in\{0,\ldots,7\}m∈{0,…,7}, and its list exchanges jjj with the distinguished coordinate if necessary, then applies mmm phases ω\omegaω there; at index q+1q+1q+1, its list is a pass at exponent q+1q+1q+1 followed by a column trace at index qqq for the transformed vector. To define a pass, put O=Z[ω]\mathcal O=\mathbb Z[\omega]O=Z[ω], let sss be the supplied complex constant sqrtTwo, whose value is not specified here, and reduce the integer coefficients of an element of O\mathcal OO in the basis (ω3,ω2,ω,1)(\omega^3,\omega^2,\omega,1)(ω3,ω2,ω,1) modulo 222, using residue 000 outside O\mathcal OO. For residues set (a∗b)ℓ=∑v,t=031v+t≡ℓ+3(mod4)avbt(a*b)_\ell=\sum_{v,t=0}^3\mathbf1_{v+t\equiv\ell+3\pmod4}a_vb_t(a∗b)ℓ​=∑v,t=03​1v+t≡ℓ+3(mod4)​av​bt​, aˉ=(a2,a1,a0,a3)\bar a=(a_2,a_1,a_0,a_3)aˉ=(a2​,a1​,a0​,a3​), and call aaa reducible if a=(1,0,1,0)∗ba=(1,0,1,0)*ba=(1,0,1,0)∗b for some bbb. A pass at exponent qqq repeatedly chooses distinct coordinates whose residues after multiplication by sqs^qsq have equal aˉ∗a\bar a*aaˉ∗a, requiring the first residue to be nonreducible. For that ordered pair, it searches [][][], then TmHT^mHTmH for m=0,…,7m=0,\ldots,7m=0,…,7, 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 smax⁡(q−1,0)s^{\max(q-1,0)}smax(q−1,0), 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 X,H,TX,H,TX,H,T operations on distinct indices or a single-coordinate phase ω\omegaω. No unitarity, normalization, or denominator bound on the input matrix is separately required by this relation; k=0k=0k=0 is included, and multiplication of that index by 333 still gives 000.

QAlgorithms.Papers.Independent.Intakethird100.P85.PassTrace

For every natural dimension ddd and natural number kkk, this defines a relation between vectors u∈Cdu\in\mathbb C^du∈Cd and finite lists of operations on their coordinates. Here an X,H,X,H,X,H, or TTT operation on distinct ordered indices j,l<dj,l<dj,l<d applies that two-dimensional matrix to coordinates j,lj,lj,l, with jjj corresponding to false\mathrm{false}false, and acts as the identity elsewhere; a phase operation at jjj multiplies that coordinate by ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4. A list acts in its listed chronological order. The residue tests used in the relation are defined as follows: let O=Z[ω]\mathcal O=\mathbb Z[\omega]O=Z[ω], let sss be the supplied complex constant sqrtTwo, whose value is not specified here, and let ρ(z)∈(Z/2Z)4\rho(z)\in(\mathbb Z/2\mathbb Z)^4ρ(z)∈(Z/2Z)4 be the coefficients modulo 222 of z=a0ω3+a1ω2+a2ω+a3z=a_0\omega^3+a_1\omega^2+a_2\omega+a_3z=a0​ω3+a1​ω2+a2​ω+a3​ when z∈Oz\in\mathcal Oz∈O, with ρ(z)=0\rho(z)=0ρ(z)=0 otherwise. For residue vectors define (a∗b)ℓ=∑p,q=031p+q≡ℓ+3(mod4)apbq(a*b)_\ell=\sum_{p,q=0}^3\mathbf1_{p+q\equiv\ell+3\pmod4}a_pb_q(a∗b)ℓ​=∑p,q=03​1p+q≡ℓ+3(mod4)​ap​bq​, define aˉ=(a2,a1,a0,a3)\bar a=(a_2,a_1,a_0,a_3)aˉ=(a2​,a1​,a0​,a3​), and call aaa reducible when (1,0,1,0)∗b=a(1,0,1,0)*b=a(1,0,1,0)∗b=a for some residue vector bbb. Starting from uuu, a trace is built by finitely many pair steps, followed by a stopping step. A pair step chooses distinct j,l<dj,l<dj,l<d such that ρ(skuj)\rho(s^ku_j)ρ(skuj​) is not reducible and ρ(skuj)‾∗ρ(skuj)=ρ(skul)‾∗ρ(skul)\overline{\rho(s^ku_j)}*\rho(s^ku_j)=\overline{\rho(s^ku_l)}*\rho(s^ku_l)ρ(skuj​)​∗ρ(skuj​)=ρ(skul​)​∗ρ(skul​). It forms the two-coordinate vector (uj,ul)(u_j,u_l)(uj​,ul​), searches the ordered candidate list consisting of [][][], then TmHT^mHTmH for m=0,…,7m=0,\ldots,7m=0,…,7, 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 smax⁡(k−1,0)s^{\max(k-1,0)}smax(k−1,0), lie in O\mathcal OO; if none qualifies, it selects [][][]. That word is lifted to operations on j,lj,lj,l, appended to the trace, and applied to the current vector; the process then continues at the same kkk. Stopping contributes no operations and is allowed precisely when every coordinate residue ρ(skui)\rho(s^ku_i)ρ(skui​) 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 k=0k=0k=0 uses exponent 000 in the candidate test, and for d=0d=0d=0 the stopping condition is vacuous and only the empty operation list is related.

QAlgorithms.Papers.Independent.Intakethird100.P85.ScalarExponent

For a complex number ttt and a natural number kkk, including k=0k=0k=0, this predicate means that there exist integers a0,a1,a2,a3a_0,a_1,a_2,a_3a0​,a1​,a2​,a3​ such that skt=a0ω3+a1ω2+a2ω+a3s^k t=a_0\omega^3+a_1\omega^2+a_2\omega+a_3skt=a0​ω3+a1​ω2+a2​ω+a3​, where ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4 and sss denotes the complex constant named sqrtTwo, whose definition is not included in the supplied code. This requires only such a representation at exponent kkk, without requiring kkk to be least; t=0t=0t=0 is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P85.TwiceReducible

For a vector x∈(Z/2Z)4x\in(\mathbb Z/2\mathbb Z)^4x∈(Z/2Z)4, this predicate means that there exists y∈(Z/2Z)4y\in(\mathbb Z/2\mathbb Z)^4y∈(Z/2Z)4 such that, for every ℓ∈{0,1,2,3}\ell\in\{0,1,2,3\}ℓ∈{0,1,2,3}, xℓ=∑i=03∑j=031(i+j) mod 4=(ℓ+3) mod 4 biyjx_\ell=\sum_{i=0}^{3}\sum_{j=0}^{3}\mathbf1_{(i+j)\bmod4=(\ell+3)\bmod4}\,b_i y_jxℓ​=∑i=03​∑j=03​1(i+j)mod4=(ℓ+3)mod4​bi​yj​, where bib_ibi​ is the reduction modulo 222 of ⌊0/23−i⌋ mod 2\lfloor0/2^{3-i}\rfloor\bmod2⌊0/23−i⌋mod2. Every bib_ibi​ is zero, so this predicate is equivalent to x=0x=0x=0; when x=0x=0x=0, every vector yyy satisfies the required equation.

QAlgorithms.Papers.Independent.Intakethird100.P85.VectorExponent

For any type ι\iotaι, any function u:ι→Cu:\iota\to\mathbb Cu:ι→C, and any natural number kkk, this predicate means that for every j∈ιj\in\iotaj∈ι there exist integers a0,a1,a2,a3a_0,a_1,a_2,a_3a0​,a1​,a2​,a3​, allowed to depend on jjj, such that skuj=a0ω3+a1ω2+a2ω+a3s^k u_j=a_0\omega^3+a_1\omega^2+a_2\omega+a_3skuj​=a0​ω3+a1​ω2+a2​ω+a3​, where ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4 and sss is the complex constant named sqrtTwo, whose definition is not supplied. No finiteness or nonemptiness assumption is imposed on ι\iotaι; if ι\iotaι is empty, the predicate holds for every kkk, and k=0k=0k=0 is permitted.

QAlgorithms.Papers.Independent.Intakethird100.P85.baseColumnWord

For any natural dimension ddd, indices first,j<d\mathrm{first},j<dfirst,j<d, and integer m∈{0,…,7}m\in\{0,\ldots,7\}m∈{0,…,7}, this defines the following list of coordinate operations: if first=j\mathrm{first}=jfirst=j, begin with the empty list; otherwise begin with the single XXX operation that exchanges coordinates first\mathrm{first}first and jjj and fixes all other coordinates. Then append exactly mmm phase operations at coordinate first\mathrm{first}first, each represented by the diagonal matrix with entry ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4 at that coordinate and 111 elsewhere. Thus for m=0m=0m=0 no phase operations are appended, and when also first=j\mathrm{first}=jfirst=j the result is empty. There are no choices of the required indices when d=0d=0d=0.

QAlgorithms.Papers.Independent.Intakethird100.P85.boundedOperators

For any natural numbers n,kn,kn,k, this defines the type of complex matrices UUU, with rows and columns indexed by Boolean strings of length nnn, equipped with the two properties U†U=UU†=IU^\dagger U=UU^\dagger=IU†U=UU†=I and skUyz∈Z[ω]s^kU_{yz}\in\mathbb Z[\omega]skUyz​∈Z[ω] for every pair of strings y,zy,zy,z. Here ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4, membership in Z[ω]\mathbb Z[\omega]Z[ω] means being expressible as aω3+bω2+cω+da\omega^3+b\omega^2+c\omega+daω3+bω2+cω+d for integers a,b,c,da,b,c,da,b,c,d, and sss denotes the complex constant named sqrtTwo, whose value is not specified in the supplied definitions. The exponent kkk need not be the least exponent with this property. The case k=0k=0k=0 requires the entries themselves to lie in Z[ω]\mathbb Z[\omega]Z[ω]; n=0n=0n=0 gives a 1×11\times11×1 matrix rather than an empty matrix.

QAlgorithms.Papers.Independent.Intakethird100.P85.coordinateWeight

For any real coordinate vector a=(a0,a1,a2,a3)a=(a_0,a_1,a_2,a_3)a=(a0​,a1​,a2​,a3​), this defines its coordinate weight to be the real number ∑j=03aj2\sum_{j=0}^{3}a_j^2∑j=03​aj2​. No restriction on the coordinates is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P85.dyadicValue

For any real coordinate vector a=(a0,a1,a2,a3)a=(a_0,a_1,a_2,a_3)a=(a0​,a1​,a2​,a3​), this defines the complex number

a0ω3+a1ω2+a2ω+a3,ω=eiπ/4.a_0\omega^3+a_1\omega^2+a_2\omega+a_3, \qquad \omega=e^{\mathrm{i}\pi/4}.a0​ω3+a1​ω2+a2​ω+a3​,ω=eiπ/4.

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 H=12(111−1)H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}H=2​1​(11​1−1​), S=diag⁡(1,i)S=\operatorname{diag}(1,i)S=diag(1,i), and T=diag⁡(1,eiπ/4)T=\operatorname{diag}(1,e^{i\pi/4})T=diag(1,eiπ/4), the two-qubit gate sending a basis label (a,b)(a,b)(a,b) to (a,b⊕a)(a,b\mathbin{\oplus}a)(a,b⊕a), and the zero-qubit gate with 1×11\times11×1 matrix [eiπ/4][e^{i\pi/4}][eiπ/4]. Here the one-qubit matrix order is false, true, and ⊕\oplus⊕ denotes exclusive or.

QAlgorithms.Papers.Independent.Intakethird100.P85.indexedMatrix

For every natural number nnn and complex matrix UUU indexed in both directions by Boolean strings of length nnn, this defines a 2n×2n2^n\times2^n2n×2n matrix by relabeling its rows and columns with the integers 0,…,2n−10,\ldots,2^n-10,…,2n−1. Explicitly, its (a,b)(a,b)(a,b) entry is Uβn(a),βn(b)U_{\beta_n(a),\beta_n(b)}Uβn​(a),βn​(b)​, where βn(a)\beta_n(a)βn​(a) is the unique Boolean string satisfying a=∑i=0n−11βn(a)i=true2n−1−ia=\sum_{i=0}^{n-1}\mathbf1_{\beta_n(a)_i=\mathrm{true}}2^{n-1-i}a=∑i=0n−1​1βn​(a)i​=true​2n−1−i, and similarly for bbb. No property of UUU is assumed. For n=0n=0n=0, there is one empty Boolean string and one integer index, so the result is still a 1×11\times11×1 matrix.

QAlgorithms.Papers.Independent.Intakethird100.P85.inverseOp

For every natural number ddd, this maps a formal operation to a list of formal operations as follows: an xxx operation on distinct ordered indices j,lj,lj,l gives the singleton list containing that same xxx operation; an hhh operation on distinct ordered indices gives the singleton list containing that same hhh operation; a ttt operation on distinct ordered indices gives seven copies of that same ttt operation; and a phase operation at an index jjj gives seven copies of that same phase operation. All indices and the supplied distinctness proofs are retained. For d=0d=0d=0, there are no input operations.

QAlgorithms.Papers.Independent.Intakethird100.P85.inverseWord

For every natural number ddd and every finite list of formal operations on ddd indices, this reverses the list and then replaces each operation by a list: an xxx or hhh operation becomes one copy of itself, while a ttt or phase operation becomes seven copies of itself. An xxx, hhh, or ttt operation carries ordered indices j,l<dj,l<dj,l<d together with a proof that they are distinct, and a phase operation carries one index j<dj<dj<d; 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 d=0d=0d=0.

QAlgorithms.Papers.Independent.Intakethird100.P85.kResidue

For a complex number ttt and a natural number kkk, this defines a vector of four elements of Z/2Z\mathbb Z/2\mathbb ZZ/2Z as follows: set z=sktz=s^k tz=skt, where sss is the complex constant named sqrtTwo, whose definition is not supplied, and let ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4. If there exists an integer tuple (a0,a1,a2,a3)(a_0,a_1,a_2,a_3)(a0​,a1​,a2​,a3​) satisfying a0ω3+a1ω2+a2ω+a3=za_0\omega^3+a_1\omega^2+a_2\omega+a_3=za0​ω3+a1​ω2+a2​ω+a3​=z, use a tuple selected by classical choice and return its coordinates reduced modulo 222; if no such tuple exists, return the zero vector. The definition applies to every ttt and every kkk, including 000, without an assumption that the representation exists.

QAlgorithms.Papers.Independent.Intakethird100.P85.levelMatrix

For every natural number ddd, this assigns a complex d×dd\times dd×d matrix to each formal operation: an xxx, hhh, or ttt operation on distinct ordered indices j,lj,lj,l receives, respectively, the block

X=(0110),H=12(111−1),T=(100eiπ/4)X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad T=\begin{pmatrix}1&0\\0&e^{\mathrm{i}\pi/4}\end{pmatrix}X=(01​10​),H=2​1​(11​1−1​),T=(10​0eiπ/4​)

on rows and columns ordered as (j,l)(j,l)(j,l), with the identity on the remaining indices and zero entries connecting the block to those indices. A phase operation at jjj receives the diagonal matrix whose entry at jjj is eiπ/4e^{\mathrm{i}\pi/4}eiπ/4 and whose other diagonal entries are 111. When d=0d=0d=0, there is no formal operation to which this assignment can be applied.

QAlgorithms.Papers.Independent.Intakethird100.P85.levelWordMatrix

For every natural number ddd and every finite list w=[g1,…,gm]w=[g_1,\ldots,g_m]w=[g1​,…,gm​] of formal operations on ddd indices, this defines the matrix product L(gm)⋯L(g1)L(g_m)\cdots L(g_1)L(gm​)⋯L(g1​). Here an xxx, hhh, or ttt operation carries distinct ordered indices j,lj,lj,l and LLL places, respectively,

(0110),12(111−1),(100eiπ/4)\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad \begin{pmatrix}1&0\\0&e^{\mathrm{i}\pi/4}\end{pmatrix}(01​10​),2​1​(11​1−1​),(10​0eiπ/4​)

on those indices, with the identity elsewhere and zero connecting entries; for a phase operation at jjj, LLL is diagonal with entry eiπ/4e^{\mathrm{i}\pi/4}eiπ/4 at jjj and 111 elsewhere. The empty list gives the identity matrix, including when d=0d=0d=0.

QAlgorithms.Papers.Independent.Intakethird100.P85.liftHT

For every natural number ddd, every pair of indices j,l∈{0,…,d−1}j,l\in\{0,\ldots,d-1\}j,l∈{0,…,d−1}, every supplied proof that j≠lj\ne lj=l, and every finite word over the two formal symbols hhh and ttt, this returns the list obtained by replacing each hhh symbol with the formal hhh operation on ordered indices (j,l)(j,l)(j,l) and each ttt symbol with the formal ttt 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 d≥2d\ge2d≥2.

QAlgorithms.Papers.Independent.Intakethird100.P85.multiplyControlled

For every natural number rrr and arbitrary complex 2×22\times22×2 matrix MMM indexed by Boolean values, this defines a matrix on Boolean strings of length r+1r+1r+1. Its entry at row yyy, column zzz is 000 if yyy and zzz differ in any of their first rrr coordinates. If those coordinates agree and all first rrr coordinates of zzz are true\mathrm{true}true, the entry is Myr,zrM_{y_r,z_r}Myr​,zr​​. If those coordinates agree but are not all true\mathrm{true}true, the entry is 111 when yr=zry_r=z_ryr​=zr​, and 000 otherwise. No unitarity assumption on MMM is imposed. For r=0r=0r=0, both conditions over the first rrr coordinates are vacuous, so the defined matrix is simply MMM on the sole Boolean coordinate.

QAlgorithms.Papers.Independent.Intakethird100.P85.omegaGate

This defines a gate of arity 000 whose matrix has every entry equal to ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4. There is exactly one zero-bit string, so its matrix is the 1×11\times11×1 matrix [ω][\omega][ω].

QAlgorithms.Papers.Independent.Intakethird100.P85.qubitLevelMatrix

For every natural number nnn and coordinate operation ggg on 2n2^n2n coordinates, this defines a matrix indexed by Boolean strings y,zy,zy,z of length nnn, with entry L(g)ν(y),ν(z)L(g)_{\nu(y),\nu(z)}L(g)ν(y),ν(z)​, where ν(y)=∑i=0n−11yi=true2n−1−i\nu(y)=\sum_{i=0}^{n-1}\mathbf1_{y_i=\mathrm{true}}2^{n-1-i}ν(y)=∑i=0n−1​1yi​=true​2n−1−i. Here L(g)L(g)L(g) is the identity outside the selected coordinates: an X,H,X,H,X,H, or TTT operation selects distinct ordered indices j,l<2nj,l<2^nj,l<2n and places the corresponding two-dimensional matrix on those coordinates, with jjj corresponding to false\mathrm{false}false and lll to true\mathrm{true}true; a phase operation at jjj is diagonal with entry ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4 at jjj and 111 elsewhere. Thus this definition relabels a coordinate-operation matrix using Boolean strings. When n=0n=0n=0, there is only one coordinate, so only the phase kind of operation is available.

QAlgorithms.Papers.Independent.Intakethird100.P85.residueConjugate

For any vector x=(x0,x1,x2,x3)∈(Z/2Z)4x=(x_0,x_1,x_2,x_3)\in(\mathbb Z/2\mathbb Z)^4x=(x0​,x1​,x2​,x3​)∈(Z/2Z)4, this defines the vector (x2,x1,x0,x3)(x_2,x_1,x_0,x_3)(x2​,x1​,x0​,x3​), exchanging coordinates 000 and 222 and leaving coordinates 111 and 333 unchanged.

QAlgorithms.Papers.Independent.Intakethird100.P85.residueNorm

For any vector x=(x0,x1,x2,x3)∈(Z/2Z)4x=(x_0,x_1,x_2,x_3)\in(\mathbb Z/2\mathbb Z)^4x=(x0​,x1​,x2​,x3​)∈(Z/2Z)4, this defines a vector N(x)N(x)N(x) whose coordinate ℓ∈{0,1,2,3}\ell\in\{0,1,2,3\}ℓ∈{0,1,2,3} is N(x)ℓ=∑i=03∑j=031(i+j) mod 4=(ℓ+3) mod 4 cixjN(x)_\ell=\sum_{i=0}^{3}\sum_{j=0}^{3}\mathbf1_{(i+j)\bmod4=(\ell+3)\bmod4}\,c_i x_jN(x)ℓ​=∑i=03​∑j=03​1(i+j)mod4=(ℓ+3)mod4​ci​xj​, where c=(x2,x1,x0,x3)c=(x_2,x_1,x_0,x_3)c=(x2​,x1​,x0​,x3​), the indicator is 111 when its condition holds and 000 otherwise, and all sums and products take place in Z/2Z\mathbb Z/2\mathbb ZZ/2Z.

QAlgorithms.Papers.Independent.Intakethird100.P85.rowCandidates

This defines an ordered list of words over the two formal symbols hhh and ttt. For m=0,…,7m=0,\ldots,7m=0,…,7, let rmr_mrm​ be the word consisting of mmm copies of ttt followed by one hhh, so r0=[h]r_0=[h]r0​=[h]. The list consists first of the empty word, then r0,r1,…,r7r_0,r_1,\ldots,r_7r0​,r1​,…,r7​, and then all concatenations rarbr_a r_bra​rb​, with aaa running from 000 to 777 and, for each fixed aaa, bbb running from 000 to 777. Thus the list has 737373 entries.

QAlgorithms.Papers.Independent.Intakethird100.P85.rowWord

For any function u:{false,true}→Cu:\{\mathrm{false},\mathrm{true}\}\to\mathbb Cu:{false,true}→C and natural number kkk, this defines a word in the letters H,TH,TH,T. Put ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4, O=Z[ω]\mathcal O=\mathbb Z[\omega]O=Z[ω], and let sss denote the complex constant named sqrtTwo, whose value is not specified in the supplied definitions. For a word w=[g1,…,gq]w=[g_1,\ldots,g_q]w=[g1​,…,gq​], write W(w)=Gq⋯G1W(w)=G_q\cdots G_1W(w)=Gq​⋯G1​, where GiG_iGi​ is the Hadamard or T=diag⁡(1,ω)T=\operatorname{diag}(1,\omega)T=diag(1,ω) matrix corresponding to gig_igi​, and W([])=IW([])=IW([])=I. Search, in order, the following list of 73 candidate words: the empty word; the eight words TmHT^mHTmH, for m=0,…,7m=0,\ldots,7m=0,…,7, where this notation denotes a list of mmm letters TTT followed by HHH; and all concatenations of two such words, ordered first by the first word and then by the second. Return the first candidate www for which every coordinate of smax⁡(k−1,0)W(w)us^{\max(k-1,0)}W(w)usmax(k−1,0)W(w)u belongs to O\mathcal OO. 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; k=0k=0k=0 is included, and its tested exponent is 000. No normalization or denominator hypothesis on uuu is required.

QAlgorithms.Papers.Independent.Intakethird100.P85.shiftOp

For every natural number ddd, this maps an operation on ddd coordinates to an operation on d+1d+1d+1 coordinates by increasing every coordinate index by 111. An X,H,X,H,X,H, or TTT operation on distinct ordered indices j,l<dj,l<dj,l<d becomes the same operation on j+1,l+1j+1,l+1j+1,l+1; a phase operation at jjj becomes a phase operation at j+1j+1j+1. The two-coordinate operations apply the corresponding Pauli XXX, Hadamard, or T=diag⁡(1,eiπ/4)T=\operatorname{diag}(1,e^{i\pi/4})T=diag(1,eiπ/4) matrix and are the identity elsewhere, while a phase operation multiplies its selected coordinate by eiπ/4e^{i\pi/4}eiπ/4. Distinctness is preserved, and the newly introduced coordinate 000 is fixed. When d=0d=0d=0, there are no operations to which this map can be applied.

QAlgorithms.Papers.Independent.Intakethird100.P85.twoLevel

For any natural number ddd, any complex matrix MMM with rows and columns indexed by {false,true}\{\mathrm{false},\mathrm{true}\}{false,true}, and any indices j,l∈{0,…,d−1}j,l\in\{0,\ldots,d-1\}j,l∈{0,…,d−1}, this defines a complex d×dd\times dd×d matrix AAA by the following ordered cases:

Aab={Mfalse,falsea=j, b=j,Mfalse,truea=j, b≠j, b=l,0a=j, b≠j, b≠l,Mtrue,falsea≠j, a=l, b=j,Mtrue,truea≠j, a=l, b≠j, b=l,0a≠j, a=l, b≠j, b≠l,1a≠j, a≠l, a=b,0a≠j, a≠l, a≠b.A_{ab}= \begin{cases} M_{\mathrm{false},\mathrm{false}}&a=j,\ b=j,\\ M_{\mathrm{false},\mathrm{true}}&a=j,\ b\ne j,\ b=l,\\ 0&a=j,\ b\ne j,\ b\ne l,\\ M_{\mathrm{true},\mathrm{false}}&a\ne j,\ a=l,\ b=j,\\ M_{\mathrm{true},\mathrm{true}}&a\ne j,\ a=l,\ b\ne j,\ b=l,\\ 0&a\ne j,\ a=l,\ b\ne j,\ b\ne l,\\ 1&a\ne j,\ a\ne l,\ a=b,\\ 0&a\ne j,\ a\ne l,\ a\ne b. \end{cases}Aab​=⎩⎨⎧​Mfalse,false​Mfalse,true​0Mtrue,false​Mtrue,true​010​a=j, b=j,a=j, b=j, b=l,a=j, b=j, b=l,a=j, a=l, b=j,a=j, a=l, b=j, b=l,a=j, a=l, b=j, b=l,a=j, a=l, a=b,a=j, a=l, a=b.​

There is no assumption that j≠lj\ne lj=l: if j=lj=lj=l, the result is diagonal with entry Mfalse,falseM_{\mathrm{false},\mathrm{false}}Mfalse,false​ at jjj and 111 at every other diagonal position. No unitarity hypothesis on MMM is imposed. For d=0d=0d=0, no indices j,lj,lj,l exist.

QAlgorithms.Papers.Independent.Intakethird100.P85.vectorNormSq

For any type ι\iotaι equipped with a finite enumeration and any function u:ι→Cu:\iota\to\mathbb Cu:ι→C, this defines the real number

∑i∈ι((Re⁡ui)2+(Im⁡ui)2).\sum_{i\in\iota}\left((\operatorname{Re}u_i)^2+(\operatorname{Im}u_i)^2\right).i∈ι∑​((Reui​)2+(Imui​)2).

The type ι\iotaι may be empty, in which case the sum is 000.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me