Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 15 (Gentle Search) — find j with Tr(E_jρ) ≥ c − ε from O(log⁴M/ε² · (log log M + log 1/δ)) copies

Proved
ShadowTomography.UpperBound.lemma_15

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

gentle-searchp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexityshadow-tomography

There is a universal constant C>0C>0C>0 with the following property. Let ρ\rhoρ be an unknown mixed state of any finite dimension, let E1,…,EME_1,\dots,E_ME1​,…,EM​ (M≥1M\ge1M≥1) be known two-outcome measurements, and let c∈Rc\in\mathbb Rc∈R, ε>0\varepsilon>0ε>0 and 0<δ≤1/20<\delta\le 1/20<δ≤1/2. Then there are a number of copies

k≤C log⁡4Mε2(log⁡log⁡M+log⁡1δ)k \le C\,\frac{\log^4 M}{\varepsilon^2}\Big(\log\log M + \log\frac1\delta\Big)k≤Cε2log4M​(loglogM+logδ1​)

and a measurement of ρ⊗k\rho^{\otimes k}ρ⊗k with outcomes j∈[M]j\in[M]j∈[M] (depending on the EiE_iEi​, ccc, ε\varepsilonε, δ\deltaδ, but not on ρ\rhoρ) such that, whenever there exists i∈[M]i\in[M]i∈[M] with Tr(Eiρ)≥c\mathrm{Tr}(E_i\rho)\ge cTr(Ei​ρ)≥c, the outcome jjj satisfies Tr(Ejρ)≥c−ε\mathrm{Tr}(E_j\rho)\ge c-\varepsilonTr(Ej​ρ)≥c−ε with probability at least 1−δ1-\delta1−δ.

Gentle Search is the subroutine that, inside each iteration of the main procedure, locates a measurement on which the current hypothesis is wrong.

Formalization Note The constant CCC is quantified before the dimension. Added hypotheses: M≥1M\ge1M≥1 (with M=0M=0M=0 there is no measurement with outcomes in the empty set), and δ≤1/2\delta\le 1/2δ≤1/2, which keeps the factor log⁡log⁡M+log⁡(1/δ)\log\log M+\log(1/\delta)loglogM+log(1/δ) positive at M=2M=2M=2 (log⁡log⁡2<0\log\log 2<0loglog2<0). Logarithms are natural; for log⁡log⁡\log\logloglog the base matters only through the constant and the additive shift covered by δ≤1/2\delta\le1/2δ≤1/2.

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

open scoped ComplexOrder
Formal statement
namespace ShadowTomography.UpperBound

/-- **Lemma 15 (Gentle Search).** There is a universal constant `C` such that for every finite
dimension, every `M ≥ 1` known two-outcome measurements `E i`, every `c`, `ε > 0` and
`δ ∈ (0, 1/2]`, some `k ≤ C (log⁴ M / ε²)(log log M + log(1/δ))` and some measurement of
`ρ^{⊗k}` with an index `j` as outcome output, for every state with some `Tr(E_i ρ) ≥ c`, an
index with `Tr(E_j ρ) ≥ c - ε` with probability at least `1 - δ`. -/
theorem lemma_15 :
    ∃ C : ℝ, 0 < C ∧
      ∀ {n : Type} [Fintype n] [DecidableEq n] (M : ℕ) (E : Fin M → Matrix n n ℂ) (c ε δ : ℝ),
        1 ≤ M → (∀ i, IsEffect (E i)) → 0 < ε → 0 < δ → δ ≤ 1 / 2 →
        ∃ k : ℕ, (k : ℝ) ≤ C * (Real.log M ^ 4 / ε ^ 2) *
            (Real.log (Real.log M) + Real.log (1 / δ)) ∧
          ∃ P : POVM (Fin M) (Fin k → n),
            ∀ ρ : Matrix n n ℂ, WildeQIT.IsDensityOperator ρ →
              (∃ i, c ≤ ((E i) * ρ).trace.re) →
                1 - δ ≤ P.prob (tensorPow ρ k) (fun j => c - ε ≤ ((E j) * ρ).trace.re) := by sorry

end ShadowTomography.UpperBound
Source
Aaronson, Shadow Tomography of Quantum States, arXiv:1711.01053v2, p. 14, Lemma 15 (proof pp. 14–15)
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