Proof of Theorem 2, p. 17 — Markov bound Tr(F_tρ*_t) ≤ Tr(E_jρ_t)q/((Tr(E_jρ_t)+ε/4)q) for entangled ρ*_t
ProvedShadowTomography.UpperBound.markov_boundLet be a mixed state on registers, possibly correlated or entangled across the registers, let be a two-outcome measurement on one register, and let . Let be the average one-register marginal of and . Let apply to each of the registers and accept iff at least invocations accept, and accept iff at most invocations accept. Then
In the proof of Theorem 2, , and is the postselection measurement ; the bound shows that each postselection step shrinks the success probability by a factor , whatever the correlations of .
Formalization Note The fractions are kept exactly as printed (the factors are not cancelled). is required because the average marginal divides by . The paper's "" tail is not part of the statement; the bookkeeping quantity is not formalized.
import Mathlib import Definitions.Def_WildeQIT_IsDensityOperator import Definitions.Def_ShadowTomography_UpperBound_IsEffect import Definitions.Def_ShadowTomography_UpperBound_ampMeasurements import Definitions.Def_ShadowTomography_UpperBound_avgMarginal open scoped ComplexOrder
namespace ShadowTomography.UpperBound
/-- **Proof of Theorem 2, p. 17 (Markov claim).** Let `σ` be any (possibly entangled) state on
`q ≥ 1` registers, `E` a two-outcome measurement, `ε > 0`, and `a = Tr(E σ_avg)` where `σ_avg` is
the average one-register marginal of `σ`. Then the measurement accepting iff at least
`(a + ε/4) q` invocations of `E` accept has acceptance probability at most `a q / ((a + ε/4) q)`
on `σ`, and the one accepting iff at most `(a - ε/4) q` accept has acceptance probability at most
`(1 - a) q / ((1 - a + ε/4) q)`. -/
theorem markov_bound {n : Type} [Fintype n] [DecidableEq n] (E : Matrix n n ℂ) (q : ℕ)
(σ : Matrix (Fin q → n) (Fin q → n) ℂ) (ε : ℝ)
(hE : IsEffect E) (hσ : WildeQIT.IsDensityOperator σ) (hq : 1 ≤ q) (hε : 0 < ε) :
(ampAtLeast E q ((E * avgMarginal σ).trace.re + ε / 4) * σ).trace.re ≤
(E * avgMarginal σ).trace.re * q / (((E * avgMarginal σ).trace.re + ε / 4) * q) ∧
(ampAtMost E q ((E * avgMarginal σ).trace.re - ε / 4) * σ).trace.re ≤
(1 - (E * avgMarginal σ).trace.re) * q /
((1 - (E * avgMarginal σ).trace.re + ε / 4) * q) := by sorry
end ShadowTomography.UpperBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.