Lemma 2: equivalent residue reducibility tests
ProvedQAlgorithms.Papers.Independent.Intakethird100.P85.residue_reducibilityprove2quantum
Let with , and write for coefficients of . For , reducible means for some , where the residue of is . Then
Moreover, is twice reducible, meaning in , if and only if .
These tests detect the residue classes permitting denominator reduction.
Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
Formal statement
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P85
open scoped Classical BigOperators
open QAlgorithms
open QAlgorithms.Papers.Independent.Gap48.P10
(InZomega InDomega Residue bits residue residueMultiply Reducible)
open QAlgorithms.Papers.Independent.Support21.P13
(synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)
local notation "omega" => QAlgorithms.gateT true true
local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)
/-- Lemma 2, PDF p.3: all four reducibility criteria and twice reducibility. -/
theorem residue_reducibility (x : Residue) :
(Reducible x ↔ x ∈ ({bits 0, bits 5, bits 10, bits 15} : Set Residue)) ∧
(Reducible x ↔ residueMultiply (bits 10) x = bits 0) ∧
(Reducible x ↔ residueNorm x = bits 0) ∧
(TwiceReducible x ↔ x = bits 0) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P85
end
Source
Exact synthesis of multiqubit Clifford+T circuits, arXiv:1212.0506v3, PDF p. 3, Lemma 2: equivalent residue reducibility tests
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For , let have coordinates , for . Define a multiplication on these quadruples by
with the sum taken in , and define . For every , all four equivalences hold:
Here , , , and .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.