Proposition 3: linear symbolic normalization cost
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.linear_symbolic_normalizationAll 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.
For the effective normalization problem there are one fixed symbolic program and a constant , chosen before every input gate list , that return with normalized, , and
The execution consists only of constant-size finite table tests and stack operations; setup and the complete retained output are charged. This expresses the linear symbolic cost of Appendix C, including the empty input.
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 3, PDF p.3 and Appendix C, p.8.
Runtime includes actual execution, input scan and the retained output. -/
theorem linear_symbolic_normalization :
∃ 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 such that the following holds for every finite word in , including the empty word. Set , , and , and let multiply in the order prescribed by , using for the empty word. A syllable represents , a syllable represents , and is their list-order product, with . Define
There exist , a syllable list that is empty or ends in and has no two consecutive syllables, an index , a natural cost , and a complex scalar with , such that
The program executes from , obtained from by encoding as , to , where encodes as . The program is an ordered finite list of instructions for four stacks over , each specifying a natural state, the exact four heads, four keep, pop, or single-symbol push actions, and a next natural state or halt. Popping an empty stack leaves it empty. Starting in state with on stack and all other stacks empty, execution applies the first matching instruction and updates the stacks simultaneously; if none matches, it halts with unchanged stacks, and halted configurations remain fixed. There must be a natural number of steps after which the machine is halted with stack exactly , without constraints on the other stacks, and the cost is
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.