Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
ShadowTomography.UpperBound.markov_bound

by mikedeng1 · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-inequalityp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1postselectionshadow-tomography

Let σ\sigmaσ be a mixed state on q≥1q\ge1q≥1 registers, possibly correlated or entangled across the registers, let EEE be a two-outcome measurement on one register, and let ε>0\varepsilon>0ε>0. Let σˉ\bar\sigmaσˉ be the average one-register marginal of σ\sigmaσ and a=Tr(Eσˉ)a=\mathrm{Tr}(E\bar\sigma)a=Tr(Eσˉ). Let F+F_{+}F+​ apply EEE to each of the qqq registers and accept iff at least (a+ε/4)q(a+\varepsilon/4)q(a+ε/4)q invocations accept, and F−F_{-}F−​ accept iff at most (a−ε/4)q(a-\varepsilon/4)q(a−ε/4)q invocations accept. Then

Tr(F+σ)≤a q(a+ε/4) q,Tr(F−σ)≤(1−a) q(1−a+ε/4) q.\mathrm{Tr}(F_{+}\sigma) \le \frac{a\,q}{(a+\varepsilon/4)\,q}, \qquad \mathrm{Tr}(F_{-}\sigma)\le \frac{(1-a)\,q}{(1-a+\varepsilon/4)\,q}.Tr(F+​σ)≤(a+ε/4)qaq​,Tr(F−​σ)≤(1−a+ε/4)q(1−a)q​.

In the proof of Theorem 2, σ=ρt∗\sigma=\rho^*_tσ=ρt∗​, σˉ=ρt\bar\sigma=\rho_tσˉ=ρt​ and F±F_\pmF±​ is the postselection measurement FtF_tFt​; the bound shows that each postselection step shrinks the success probability ptp_tpt​ by a factor 1−Ω(ε)1-\Omega(\varepsilon)1−Ω(ε), whatever the correlations of ρt∗\rho^*_tρt∗​.

Formalization Note The fractions are kept exactly as printed (the factors qqq are not cancelled). q≥1q\ge1q≥1 is required because the average marginal divides by qqq. The paper's "=1−Ω(ε)=1-\Omega(\varepsilon)=1−Ω(ε)" tail is not part of the statement; the bookkeeping quantity ptp_tpt​ is not formalized.

Preamble
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
Formal statement
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
Source
Aaronson, Shadow Tomography of Quantum States, arXiv:1711.01053v2, p. 17, proof of Theorem 2 (definition of F_t; the two Markov displays)
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me