Eqs. (7)–(8), p. 7 — the depth needed for accuracy ε, and 5ⁿ = O(ln^{ln 5/ln(3/2)}(1/ε))
ProvedSKAlgorithm.Qudit.eq_7_8asymptoticsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1recurrencesolovay-kitaev
Let and with . There is a constant such that for every there is a depth with
By Eq. (4) the first inequality says ; since the sequence returned at depth has length at most , the second gives the length bound of Eq. (8), with exponent .
Formalization Note. The depth is existential; the paper's explicit choice, Eq. (7), , gives , and the strict inequality needed later may require one more level, which absorbs. is chosen before . is replaced by so that the bound is meaningful for every , including ; as the two are asymptotically equal, so the -class is the same.
Preamble
import Mathlib import Definitions.Def_SKAlgorithm_Qudit_Model open scoped Matrix open QAlgorithms
Formal statement
namespace SKAlgorithm.Qudit
theorem eq_7_8 (c ε₀ : ℝ) (hc : 0 < c) (hε₀ : 0 < ε₀) (hlt : ε₀ * c ^ 2 < 1) :
∃ K : ℝ, 0 < K ∧ ∀ ε : ℝ, 0 < ε → ∃ n : ℕ,
1 / c ^ 2 * (ε₀ * c ^ 2) ^ (((3 : ℝ) / 2) ^ n) < ε ∧
(5 : ℝ) ^ n ≤ K * Real.log (2 + 1 / ε) ^ (Real.log 5 / Real.log (3 / 2)) := by sorry
end SKAlgorithm.Qudit
Source
Dawson and Nielsen, The Solovay-Kitaev algorithm, arXiv:quant-ph/0505030v2, p. 7, Eqs. (7)–(8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.