Proposition 2: effective canonical representation
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.effective_canonical_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 are fixed normalization and canonical-reduction procedures and universal positive constants . For each raw gate list , returns a normalized presentation , and returns actual Clifford gates and a canonical core , with
The bound charges the two executions separately, so normalization of a long raw input is included. The construction corresponds to Appendix D, including its recursive terminal cases.
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 2, PDF p.2, recursive construction Appendix D, pp.8--9.
The same fixed normalization and canonical phase apply to every raw gate list. -/
theorem effective_canonical_representation :
∃ pn pc : Program, ∃ Kn Kc : ℕ, 0 < Kn ∧ 0 < Kc ∧
LinearNormalizes pn Kn ∧ QuadraticReduces pc Kc ∧
∀ w : List BsHTLetter, ∃ o : NormalOutput, ∃ c : CanonicalOutput, ∃ cn cc : ℕ,
BsNormalized o.body ∧ BsCanonical c.body ∧
SameGate (bsNormalValue o) (htValue w) ∧
SameGate (canonicalValue c) (htValue w) ∧
BsExecutes pn (htSymbols w) (normalSymbols o) cn ∧
BsExecutes pc (normalSymbols o) (canonicalSymbols c) cc ∧
cn + cc ≤ Kn * (w.length + 1) + Kc * (bsTCount o.body + 1) ^ 2 := 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 finite programs and positive natural numbers satisfying the three requirements below. To specify them, put , , and ; let multiply for a finite word in , and let multiply for a finite syllable list in , with empty products . A syllable list is normalized if it is empty or ends in and has no adjacent syllables; it is canonical if it is normalized and its first syllables are all . Define
A normal output consists of , a syllable list , and ; write and , where replaces by . A canonical output consists of and a syllable list ; write and . Let encode as , and let count the syllables of . Write to mean that there exists a complex with and . For any program , write for the following execution condition: is an ordered finite list of instructions for four stacks over , each instruction matching a natural control state and all four exact heads and specifying simultaneous keep, pop, or single-symbol push actions and a next natural state or halt; popping an empty stack leaves it empty. The machine starts in state , with on stack and the other stacks empty, applies the first matching instruction, halts with unchanged stacks when none matches, and remains fixed after halting. There is a natural number of steps after which it is halted with stack exactly , with no restriction on the other stacks, and
The first requirement is that for every finite word there exist a normal output and a natural cost such that is normalized, , , and . The second is that for every normal output whose body is normalized, there exist a canonical output and a natural cost such that is canonical, , , and . The third is that for every finite word there exist a normal output , a canonical output , and natural costs , such that is normalized, is canonical,
and
Each occurrence of permits its own modulus-one scalar. These requirements include empty input words and empty bodies.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.