Lemma 1, p. 9 — approximating a group commutator
ProvedSKAlgorithm.Qudit.lemma_1group-commutatoroperator-normp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1solovay-kitaev
Let be unitary matrices and real numbers such that
Then
In the Solovay-Kitaev recursion is the current accuracy and is of order , so the right-hand side is : approximating and to accuracy approximates their group commutator to the better accuracy .
Formalization Note. are matrices with membership in the unitary group (not necessarily of determinant one), as in the lemma. is and all distances use the operator norm QAlgorithms.specNorm; is the conjugate transpose.
Preamble
import Mathlib import Definitions.Def_SKAlgorithm_Qudit_Model open scoped Matrix open QAlgorithms
Formal statement
namespace SKAlgorithm.Qudit
theorem lemma_1 {d : ℕ} (V W Vt Wt : Matrix (Fin d) (Fin d) ℂ)
(hV : V ∈ Matrix.unitaryGroup (Fin d) ℂ) (hW : W ∈ Matrix.unitaryGroup (Fin d) ℂ)
(hVt : Vt ∈ Matrix.unitaryGroup (Fin d) ℂ) (hWt : Wt ∈ Matrix.unitaryGroup (Fin d) ℂ)
(Δ δ : ℝ) (hVVt : specNorm (V - Vt) < Δ) (hWWt : specNorm (W - Wt) < Δ)
(hIV : specNorm (1 - V) < δ) (hIW : specNorm (1 - W) < δ) :
specNorm (V * W * Vᴴ * Wᴴ - Vt * Wt * Vtᴴ * Wtᴴ) <
8 * Δ * δ + 4 * Δ * δ ^ 2 + 8 * Δ ^ 2 + 4 * Δ ^ 3 + Δ ^ 4 := by sorry
end SKAlgorithm.Qudit
Source
Dawson and Nielsen, The Solovay-Kitaev algorithm, arXiv:quant-ph/0505030v2, p. 9, §4.2, Lemma 1, Eq. (14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.