Eqs. (1)–(2), (15), (21)–(22) — the Solovay-Kitaev recursion returns ε_n-approximations of length ≤ 5ⁿ l₀
ProvedSKAlgorithm.Qudit.recursion_invariantFix and constants . There are constants and with the following property. Let be finite and closed under , let and , and let be defined by (Eq. (1)). Suppose
- the lookup routine returns, for every , a sequence of gates from of length at most with ;
- the decomposition routine, at every level , returns for every with a pair in with
Then for every and every the sequence consists of gates from , has length at most (Eq. (2), ), and
This is the accuracy and length analysis of the qudit algorithm: Lemma 1 bounds the error of the approximate commutator (Eq. (15)) and the triangle inequality (Eqs. (21)–(22)) gives .
Formalization Note. The constant plays the role of and is existential (the paper estimates only approximately); and depend on (and possibly ) only, and are chosen before , , and the routines. The threshold is the paper's requirement (p. 6) that makes the accuracies decrease. The length bound is Eq. (2) unrolled. The decomposition routine is indexed by the level (see the definition file).
import Mathlib import Definitions.Def_SKAlgorithm_Qudit_Model open scoped Matrix open QAlgorithms
namespace SKAlgorithm.Qudit
theorem recursion_invariant (d : ℕ) (c' c'' : ℝ) (hc' : 0 < c') (hc'' : 0 < c'') :
∃ c εs : ℝ, 0 < c ∧ 0 < εs ∧
∀ (G : Finset (SU d)), (∀ g ∈ G, g⁻¹ ∈ G) →
∀ (ε₀ : ℝ) (l₀ : ℕ), 0 < ε₀ → ε₀ ≤ εs →
∀ (basic : SU d → List (SU d)) (gc : ℕ → SU d → SU d × SU d),
(∀ U : SU d, (∀ g ∈ basic U, g ∈ G) ∧ (basic U).length ≤ l₀ ∧
opDist U (seqUnitary (basic U)) < ε₀) →
(∀ (k : ℕ) (Δ : SU d), opDist 1 Δ < epsSeq c ε₀ k →
opDist ((gc k Δ).1 * (gc k Δ).2 * (gc k Δ).1⁻¹ * (gc k Δ).2⁻¹) Δ <
c' * epsSeq c ε₀ k ^ ((3 : ℝ) / 2) ∧
opDist 1 (gc k Δ).1 < c'' * Real.sqrt (epsSeq c ε₀ k) ∧
opDist 1 (gc k Δ).2 < c'' * Real.sqrt (epsSeq c ε₀ k)) →
∀ (n : ℕ) (U : SU d),
(∀ g ∈ solovayKitaev basic gc n U, g ∈ G) ∧
(solovayKitaev basic gc n U).length ≤ 5 ^ n * l₀ ∧
opDist U (seqUnitary (solovayKitaev basic gc n U)) < epsSeq c ε₀ n := by sorry
end SKAlgorithm.Qudit
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.