Lemma 15 (Gentle Search) — find j with Tr(E_jρ) ≥ c − ε from O(log⁴M/ε² · (log log M + log 1/δ)) copies
ProvedShadowTomography.UpperBound.lemma_15There is a universal constant with the following property. Let be an unknown mixed state of any finite dimension, let () be known two-outcome measurements, and let , and . Then there are a number of copies
and a measurement of with outcomes (depending on the , , , , but not on ) such that, whenever there exists with , the outcome satisfies with probability at least .
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 is quantified before the dimension. Added hypotheses: (with there is no measurement with outcomes in the empty set), and , which keeps the factor positive at (). Logarithms are natural; for the base matters only through the constant and the additive shift covered by .
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
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.