Binomial tail bounds for amplified count measurements
ProvedShadowTomography.UpperBound.amp_tailprobabilityquantum-information
Let be an effect and a density operator on , and write . For , a threshold and a margin , consider the amplified measurements and on registers (accept iff at least, respectively at most, of the invocations of accept). On :
- if , then ;
- if , then ;
- if , then ;
- if , then .
On i.i.d. copies the number of accepting invocations is , so these are Hoeffding's inequalities. They are the Chernoff-bound steps of the shadow-tomography proof (pp. 16-17), stated with a free margin so that the failure probability can be matched to the quantum union bound.
Preamble
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
Formal statement
namespace ShadowTomography.UpperBound
/-- **K2.** Binomial tails of the amplified count measurements (Hoeffding): with
`p = Tr(Eρ)` and margin `γ > 0`, a threshold at least `γ` below `p` makes `ampAtLeast` accept
(and `ampAtMost` reject) except with probability `exp(-2qγ²)`, and a threshold at least `γ`
above `p` makes `ampAtLeast` reject (and `ampAtMost` accept) except with that probability. -/
theorem amp_tail {n : Type} [Fintype n] [DecidableEq n] (E ρ : Matrix n n ℂ)
(hE : IsEffect E) (hρ : WildeQIT.IsDensityOperator ρ) (q : ℕ) (θ γ : ℝ) (hγ : 0 < γ) :
(θ ≤ (E * ρ).trace.re - γ →
1 - Real.exp (-2 * q * γ ^ 2) ≤ (ampAtLeast E q θ * tensorPow ρ q).trace.re) ∧
((E * ρ).trace.re + γ ≤ θ →
(ampAtLeast E q θ * tensorPow ρ q).trace.re ≤ Real.exp (-2 * q * γ ^ 2)) ∧
((E * ρ).trace.re + γ ≤ θ →
1 - Real.exp (-2 * q * γ ^ 2) ≤ (ampAtMost E q θ * tensorPow ρ q).trace.re) ∧
(θ ≤ (E * ρ).trace.re - γ →
(ampAtMost E q θ * tensorPow ρ q).trace.re ≤ Real.exp (-2 * q * γ ^ 2)) := by
sorry
end ShadowTomography.UpperBoundSource
S. Aaronson, Shadow Tomography of Quantum States, arXiv:1711.01053v2, https://arxiv.org/abs/1711.01053, Section 5 (proof of Theorem 2), pp. 15-19