Aaronson's refinement protocol with explicit parameters
ProvedShadowTomography.UpperBound.refinement_protocolThere is a universal constant such that the following holds. Let , , , and let be natural numbers with
Then for every family of two-outcome measurements on there is a measurement of copies, with finite outcome set , together with estimates , such that for every state ,
This is the correctness statement of the iterative procedure in Aaronson's proof of Theorem 2 (§5): rounds, each spending fresh copies on Gentle Search over the amplified tests ( registers of copies each) and fresh copies on checking the test it finds, followed by post-selection of the classical hypothesis. The parameters are explicit and tuned so that Chernoff bounds compose with the quantum union bound for every . Theorem 2's copy bound follows by choosing as small as allowed.
Formalization Note The measurement uses exactly copies (unused copies are ignored); the paper's "if no index is found, halt" step is realised by the explicit verification on copies.
import Mathlib import Definitions.Def_WildeQIT_IsDensityOperator import Definitions.Def_ShadowTomography_UpperBound_IsEffect import Definitions.Def_ShadowTomography_UpperBound_tensorPow import Definitions.Def_ShadowTomography_UpperBound_POVM import Definitions.Def_ShadowTomography_UpperBound_ampMeasurements import Definitions.Def_ShadowTomography_UpperBound_avgMarginal import Definitions.Def_ShadowTomography_UpperBound_seqAccept set_option autoImplicit false open scoped ComplexOrder MatrixOrder
namespace ShadowTomography.UpperBound
/-- **K0 (refinement protocol).** Aaronson's §5 procedure with explicit parameters: `T` rounds,
each spending `q ℓ` fresh copies on Gentle Search over the `2M` amplified tests (`q` copies per
amplified register, `ℓ` registers) and `v` fresh copies on verifying the found index, then
post-selecting the classical hypothesis. When `q, T, ℓ, v` exceed the stated thresholds, the
procedure measures `T (q ℓ + v)` copies (unused copies are ignored) and estimates every `Tr(E_i ρ)` to within `ε` with
probability at least `1 - δ`, for every state `ρ`. -/
theorem refinement_protocol :
∃ C₀ : ℝ, 0 < C₀ ∧
∀ (D M : ℕ) (ε δ : ℝ) (q ℓ v T : ℕ), 2 ≤ D → 2 ≤ M → 0 < ε → ε ≤ 1 / 2 → 0 < δ →
δ ≤ 1 / 2 →
C₀ * (1 + Real.log T) / ε ^ 2 ≤ (q : ℝ) →
C₀ * q * Real.log D / ε ≤ (T : ℝ) →
C₀ * Real.log M ^ 4 * (1 + Real.log (Real.log M) + Real.log (T / δ)) ≤ (ℓ : ℝ) →
C₀ * (1 + Real.log (T / δ)) / ε ^ 2 ≤ (v : ℝ) →
∀ E : Fin M → Matrix (Fin D) (Fin D) ℂ, (∀ i, IsEffect (E i)) →
∃ (Ω : Type) (_ : Fintype Ω) (P : POVM Ω (Fin (T * (q * ℓ + v)) → Fin D))
(b : Ω → Fin M → ℝ),
(∀ ω i, b ω i ∈ Set.Icc (0 : ℝ) 1) ∧
∀ ρ : Matrix (Fin D) (Fin D) ℂ, WildeQIT.IsDensityOperator ρ →
1 - δ ≤ P.prob (tensorPow ρ (T * (q * ℓ + v)))
(fun ω => ∀ i, |b ω i - ((E i) * ρ).trace.re| ≤ ε) := by
sorry
end ShadowTomography.UpperBound