Adaptive rounds on fresh blocks of copies: a union bound
ProvedShadowTomography.UpperBound.adaptive_roundsLet and let be a finite set of outcomes. Suppose that for every round and every history of previous outcomes we are given a POVM with outcomes in acting on copies, . Then there is a single POVM on with outcomes in , not depending on any state, which realises the adaptive procedure "in round , measure a fresh block of copies with , where is the record so far", in the following sense. For every density operator , every family of events and every : if
then
The shadow-tomography algorithm consumes fresh copies in each of its rounds (p. 16, "assume ... fresh copies"); this lemma turns the per-round guarantees into a guarantee for the whole procedure.
Formalization Note The -copy blocks are laid out consecutively in ; the history of round is the restriction of the record to the first rounds.
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
/-- **K3.** Adaptive rounds on fresh blocks of i.i.d. copies. For `R` rounds, each measuring a
fresh block of `k` copies with a POVM chosen from the previous outcomes, there is a single POVM
on all `R k` copies (independent of the state), whose outcome is the record of all rounds, such
that: if in every round and after every history the "good" event has probability at least
`1 - δ_r`, then all rounds are good with probability at least `1 - ∑_r δ_r`. -/
theorem adaptive_rounds {n : Type} [Fintype n] [DecidableEq n] {Ω : Type} [Fintype Ω]
(R k : ℕ) (P : ∀ r : Fin R, (Fin r → Ω) → POVM Ω (Fin k → n)) :
∃ Q : POVM (Fin R → Ω) (Fin (R * k) → n),
∀ (ρ : Matrix n n ℂ), WildeQIT.IsDensityOperator ρ →
∀ (good : ∀ r : Fin R, (Fin r → Ω) → Ω → Prop) (δ : Fin R → ℝ),
(∀ r h, 1 - δ r ≤ (P r h).prob (tensorPow ρ k) (good r h)) →
1 - ∑ r, δ r ≤ Q.prob (tensorPow ρ (R * k))
(fun ω => ∀ r : Fin R,
good r (fun i => ω (Fin.castLT i (lt_trans i.isLt r.isLt))) (ω r)) := by
sorry
end ShadowTomography.UpperBound