Eq. (4), p. 7 — closed form of the accuracies ε_n
ProvedSKAlgorithm.Qudit.eq_4p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1recurrencesolovay-kitaev
Let and , and let for (Eq. (1)). Then for every
In particular doubly exponentially in when , which is what makes the number of recursion levels logarithmic in .
Formalization Note. is the paper's ; powers with non-integer exponents are real powers of positive reals.
Preamble
import Mathlib import Definitions.Def_SKAlgorithm_Qudit_Model open scoped Matrix open QAlgorithms
Formal statement
namespace SKAlgorithm.Qudit
theorem eq_4 (c ε₀ : ℝ) (hc : 0 < c) (hε₀ : 0 < ε₀) (n : ℕ) :
epsSeq c ε₀ n = 1 / c ^ 2 * (ε₀ * c ^ 2) ^ (((3 : ℝ) / 2) ^ n) := by sorry
end SKAlgorithm.Qudit
Source
Dawson and Nielsen, The Solovay-Kitaev algorithm, arXiv:quant-ph/0505030v2, p. 7, Eq. (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.