Theorem 1, p. 4 — Solovay-Kitaev: every gate in SU(d) has an ε-approximating instruction sequence of length O(log^{ln 5/ln(3/2)}(1/ε))
ProvedSKAlgorithm.Qudit.theorem_1Theorem (Solovay-Kitaev). Let be an instruction set for . There is a constant such that for every accuracy and every gate there is a finite sequence of gates from with
Here is the operator-norm distance between and the product of the gates of , and . Theorem 1 asserts length for some constant ; the Solovay-Kitaev algorithm described in the paper gives (Eq. (8), and §5.1 for qudits), and that is the exponent stated here. The theorem says that any universal instruction set simulates any other with only polylogarithmic overhead in the accuracy.
Formalization Note. The constant depends only on and and is chosen before and ; this order is the content of the . is replaced by so that the bound is positive for every ; as the two are asymptotically equivalent, so the class is unchanged. Instruction sets are as in Definition 1: finite, closed under , universal.
import Mathlib import Definitions.Def_SKAlgorithm_Qudit_Model open scoped Matrix open QAlgorithms
namespace SKAlgorithm.Qudit
theorem theorem_1 (d : ℕ) (G : Finset (SU d)) (hG : IsInstructionSet G) :
∃ C : ℝ, 0 < C ∧ ∀ ε : ℝ, 0 < ε → ∀ U : SU d,
∃ S : List (SU d), (∀ g ∈ S, g ∈ G) ∧
(S.length : ℝ) ≤ C * Real.log (2 + 1 / ε) ^ (Real.log 5 / Real.log (3 / 2)) ∧
opDist U (seqUnitary S) < ε := by sorry
end SKAlgorithm.Qudit
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.