Theorem 2 (Shadow Tomography Theorem) — Õ(log(1/δ) log⁴M log D/ε⁵) copies estimate all Tr(E_iρ) to ±ε
ProvedShadowTomography.UpperBound.theorem_2Shadow tomography. Let be an unknown -dimensional mixed state and known two-outcome measurements. The task is to output numbers with for all , with success probability at least , via a measurement of with as small as possible.
Theorem. There is a universal constant such that for all , , and there is a number of copies
with the following property: for every list of two-outcome measurements on there is a measurement of , together with outputs for each outcome, such that for every -dimensional mixed state ,
The bound is : polylogarithmic in both the number of measurements and the dimension.
Formalization Note This is the explicit bound of the last display of the proof of Theorem 2 (p. 19), i.e. the form proved in §5; the printed form of p. 3 relies on an external online-learning algorithm and is not stated. Quantifier order: first; depends only on ; the measurement and outputs depend on the but not on . Added hypotheses: (at , forces , and no zero-copy output estimates one nontrivial to within ), and (they keep both -containing factors positive; for outputting is trivially correct). No hypothesis on is needed: has no state and at the state is known. All logarithms are natural (Real.log), including inside . The measurement is a POVM with a finite outcome type, and "probability" is the Born-rule probability of the success event.
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 open scoped ComplexOrder
namespace ShadowTomography.UpperBound
/-- **Theorem 2 (Shadow Tomography Theorem), in the explicit form proved in §5.** There is a
universal constant `C` such that for all `D`, `M ≥ 2`, `0 < ε ≤ 1/2` and `0 < δ ≤ 1/2` there is a
number of copies
`k ≤ C (log D/ε) ((log log D + log(1/ε))/ε²)² log⁴ M (log log M + log log D + log(1/ε) + log(1/δ))`
such that for every list of two-outcome measurements `E 0, …, E (M-1)` on `ℂ^D` there is a
measurement of `ρ^{⊗k}` (independent of `ρ`) whose outcome yields numbers `b_i ∈ [0, 1]` with
`|b_i - Tr(E_i ρ)| ≤ ε` for all `i` simultaneously, with probability at least `1 - δ`, for every
`D`-dimensional mixed state `ρ`. -/
theorem theorem_2 :
∃ C : ℝ, 0 < C ∧
∀ (D M : ℕ) (ε δ : ℝ), 2 ≤ M → 0 < ε → ε ≤ 1 / 2 → 0 < δ → δ ≤ 1 / 2 →
∃ k : ℕ, (k : ℝ) ≤ C * (Real.log D / ε) *
((Real.log (Real.log D) + Real.log (1 / ε)) / ε ^ 2) ^ 2 * Real.log M ^ 4 *
(Real.log (Real.log M) + Real.log (Real.log D) + Real.log (1 / ε) +
Real.log (1 / δ)) ∧
∀ E : Fin M → Matrix (Fin D) (Fin D) ℂ, (∀ i, IsEffect (E i)) →
∃ (Ω : Type) (_ : Fintype Ω) (P : POVM Ω (Fin k → Fin D)) (b : Ω → Fin M → ℝ),
(∀ ω i, b ω i ∈ Set.Icc (0 : ℝ) 1) ∧
∀ ρ : Matrix (Fin D) (Fin D) ℂ, WildeQIT.IsDensityOperator ρ →
1 - δ ≤ P.prob (tensorPow ρ k)
(fun ω => ∀ i, |b ω i - ((E i) * ρ).trace.re| ≤ ε) := by sorry
end ShadowTomography.UpperBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.