Proposition 4: quadratic worst-case canonical reduction cost
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.quadratic_canonical_reductionAll 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 are a fixed symbolic reduction procedure and a universal constant such that every already computed normalized presentation is converted to actual Clifford gates and a canonical word satisfying
The bound is a worst-case upper bound on the phase after normalization, including its input and output lists. Raw-input normalization is separately linear in the raw gate-list length.
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 4, PDF p.3 and Appendix D, pp.8--9.
This is the quadratic upper bound for the phase after normalization. -/
theorem quadratic_canonical_reduction :
∃ p : Program, ∃ K : ℕ, 0 < K ∧ QuadraticReduces 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. Set , , and . For a syllable list in , let multiply , respectively, in list order, with empty product ; call the list normalized if it is empty or ends in and has no adjacent syllables, and canonical if it is normalized and its first syllables are all . Define
For every , every normalized syllable list , including the empty list, and every , there exist , a canonical syllable list , a natural cost , and a complex scalar with , such that
where counts the syllables. The program executes from to , where encodes as . Precisely, is an ordered finite list of instructions for four stacks over ; instructions specify a natural state, all four exact heads, simultaneous keep, pop, or single-symbol push actions, and a next natural state or halt. Popping an empty stack leaves it empty. Execution starts in state , with stack equal to and the other stacks empty, and applies the first matching instruction. No matching instruction causes a halt without changing the stacks, and halted configurations stay fixed. For some natural number of steps, the machine must be halted with stack exactly , with no restriction on the other stacks, and
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.