p. 5 (and p. 11) — basic ε₀-approximations of bounded length l₀
ProvedSKAlgorithm.Qudit.base_casep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-compilingsolovay-kitaevuniversality
Let be an instruction set for and let . Then there is a length such that every gate has an -approximation by a sequence of gates from of length at most :
This is the preprocessing stage of the Solovay-Kitaev algorithm ("Return Basic Approximation to "): the paper obtains it by enumerating all instruction sequences up to a sufficiently large but fixed length . It supplies the depth-zero case of the recursion with a length independent of .
Formalization Note. The bound is chosen before ; it depends only on and . No compactness hypothesis is added; compactness of is a fact to be proved, not assumed.
Preamble
import Mathlib import Definitions.Def_SKAlgorithm_Qudit_Model open scoped Matrix open QAlgorithms
Formal statement
namespace SKAlgorithm.Qudit
theorem base_case {d : ℕ} (G : Finset (SU d)) (hG : IsInstructionSet G)
(ε₀ : ℝ) (hε₀ : 0 < ε₀) :
∃ l₀ : ℕ, ∀ U : SU d, ∃ S : List (SU d), (∀ g ∈ S, g ∈ G) ∧ S.length ≤ l₀ ∧
opDist U (seqUnitary S) < ε₀ := by sorry
end SKAlgorithm.Qudit
Source
Dawson and Nielsen, The Solovay-Kitaev algorithm, arXiv:quant-ph/0505030v2, p. 5, §3, base case 'In order to implement this step …'; p. 11, §5.1, 'This is done by enumerating all possible gate sequences up to some sufficient length'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.