Two-stage adaptive measurements on fresh copies
ProvedShadowTomography.UpperBound.povm_seqprobabilityquantum-information
Let , let be a POVM with finite outcome set on , and for each let be a POVM with finite outcome set on . Then there is a POVM on with outcomes , independent of any state, realising "measure copies with , then fresh copies with ", such that the following holds. For every density operator , events and , and , : if
then
Each round of the shadow-tomography algorithm is such a two-stage measurement: a search over amplified tests followed by a verification of the test found on fresh copies.
Formalization Note The hypothesis is needed when no outcome lies in .
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
/-- **K7.** Two-stage adaptive measurement on fresh copies: measure `a` copies with `P`, then
`b` further copies with a POVM `Q ω₁` chosen from the first outcome. There is one POVM on all
`a + b` copies (independent of the state) recording both outcomes such that, if the first stage
lands in `S` with probability `≥ 1 - δ₁` and after every first outcome in `S` the second stage is
good with probability `≥ 1 - δ₂` (`δ₂ ≥ 0`), then the pair is good with probability
`≥ 1 - δ₁ - δ₂`. -/
theorem povm_seq {n : Type} [Fintype n] [DecidableEq n] {Ω₁ Ω₂ : Type} [Fintype Ω₁]
[Fintype Ω₂] (a b : ℕ) (P : POVM Ω₁ (Fin a → n)) (Q : Ω₁ → POVM Ω₂ (Fin b → n)) :
∃ R : POVM (Ω₁ × Ω₂) (Fin (a + b) → n),
∀ ρ : Matrix n n ℂ, WildeQIT.IsDensityOperator ρ →
∀ (S : Ω₁ → Prop) (good : Ω₁ → Ω₂ → Prop) (δ₁ δ₂ : ℝ), 0 ≤ δ₂ →
1 - δ₁ ≤ P.prob (tensorPow ρ a) S →
(∀ ω₁, S ω₁ → 1 - δ₂ ≤ (Q ω₁).prob (tensorPow ρ b) (good ω₁)) →
1 - δ₁ - δ₂ ≤ R.prob (tensorPow ρ (a + b)) (fun ω => good ω.1 ω.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