Proposition 5: normalized inverse and linear construction
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.normalized_inverse_linearAll 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 procedure and a universal such that every normalized word yields an actual normalized word and a choice with
Here is syllable depth, within a fixed factor of the displayed elementary depth. The empty word is included via projectively. The proposition supplies the two inverse presentations and their linear construction.
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 5, PDF p.3. The last factor is S cubed, not G3.
No equality of T-counts is asserted; empty c is allowed. -/
theorem normalized_inverse_linear :
∃ p : Program, ∃ K : ℕ, 0 < K ∧
∀ c : List Syllable, BsNormalized c →
∃ d : List Syllable, ∃ hasS3 : Bool, ∃ cost : ℕ,
BsNormalized d ∧
SameGate (star (syllableValue c))
(QAlgorithms.hadamard * syllableValue d * QAlgorithms.hadamard *
(if hasS3 then QAlgorithms.phaseS ^ 3 else 1)) ∧
BsExecutes p (syllableSymbols c)
([if hasS3 then 30 else 29] ++ syllableSymbols d) cost ∧
cost ≤ K * (c.length + 1) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P82
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let , , and , with rows and columns ordered as false, true. A syllable is either or ; for a syllable list , let be its matrix product in list order, with . Call a list normalized when it is empty, or ends in and has no two consecutive 's. Write when there exists with and . There exist a finite program and a natural number such that, for every normalized syllable list , including the empty list, there exist a normalized syllable list , a Boolean , and a natural number satisfying
Here denotes conjugate transpose. The program operates on four stacks whose symbols are the integers , with a natural-number control state or a halted state. Each instruction specifies a control state, the exact four stack heads, an action on each stack—keep, remove its first symbol, or prepend a specified symbol—and a next control state or halt. Removing a symbol from an empty stack leaves it empty. Each step uses the first matching instruction in program order; if none matches, it halts without changing the stacks, and halted configurations remain unchanged. Initially the control state is , stack contains encoded by , , and the other stacks are empty. For some natural number , after steps the machine is halted and stack contains the symbol if is true, or otherwise, followed by the encoding of ; no final condition is imposed on the other stacks. The asserted cost is exactly
where is the number of instructions; is included among the quantified possibilities.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.