Proposition 1: effective normalized representation
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.effective_normalized_representationAll circuits are single-qubit circuits without ancillas or measurements. Products act from right to left. Let , , , and . The two distinct syllable letters are and . A normalized word is empty, or ends in with no adjacent letters. A canonical word is normalized and its first four syllables, when present, are all . Write for the number of letters in ; Clifford gates have zero charged cost.
There is a fixed symbolic procedure and an input-independent constant such that, for every gate list over , it returns a flag , a normalized word , and an actual terminal satisfying
Cost includes primitive list/stack operations, finite Clifford lookups, input setup, and the retained output. This is the effective normalized representation of Proposition 1 with its Proposition 3 efficiency clause.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P82
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P82
open scoped BigOperators
local notation "Mat" => Matrix Bool Bool ℂ
/-- Proposition 1, PDF p.2, effective construction Appendix C, p.8.
The program returns all three components with a uniform linear symbolic charge. -/
theorem effective_normalized_representation :
∃ p : Program, ∃ K : ℕ, 0 < K ∧ LinearNormalizes p K := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P82
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exist a finite program and a positive natural number with the following property. Put , , , and let be the matrix product of an arbitrary finite word in , replacing these letters by , with empty product . Let multiply the matrices for a syllable list in , respectively, again with empty product . Define
For every such , including the empty word, there exist , a syllable list that is empty or ends in and has no consecutive syllables, an index , a natural cost , and a complex number with , such that
The program executes from , the encoding of , to , where encodes . Precisely, is an ordered finite list of instructions for four stacks over , with natural control states. An instruction matches a specified state and all four exact heads and gives simultaneous keep, pop, or single-symbol push actions and a next state or halt; popping an empty stack leaves it empty. Starting in state with stack equal to and the other stacks empty, the machine applies the first matching instruction; absence of a match halts it without changing the stacks, and halted configurations remain fixed. For some natural number of steps, it is halted with stack equal to , with the other stacks unrestricted, and
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.