Non-adaptive purity estimation: full lower bound
OpenIncoherentPurity.Adaptive.Supplement.nonadaptive_lowerp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationstatistics
There exist absolute constants and an integer such that for every and every , every non-adaptive incoherent protocol that estimates the purity of every -dimensional state to relative error with probability at least satisfies
The protocol may use arbitrary measurable single-copy POVM outcomes and shared classical randomness. The constants are uniform jointly in dimension and precision and precede the budget and protocol quantifiers. This companion theorem collects both lower-bound contributions; the published mixedness result supplies one contribution and Proposition 5.4 supplies the other.
Differences from the source:
- encoding: Omega of the maximum rate for all sufficiently large dimensions and all sufficiently small positive precisions → a universal positive constant and dimension/precision thresholds, followed by every non-adaptive successful protocol; reason: this is the operational uniform lower-bound meaning of the source claim
- encoding: d to the power three halves → (d : real) times sqrt d; reason: these agree for every positive dimension
Preamble
import Definitions.Def_IncoherentPurity_Adaptive_Supplement_Spike open MeasureTheory ProbabilityTheory Matrix open scoped ENNReal set_option autoImplicit false noncomputable section
Formal statement
namespace IncoherentPurity.Adaptive.Supplement
/-- Theorem 5.1, PDF = printed p.15; pinned source SHA-256 7d80a6695c9c0b12bfa088a8f47d2a298b93f9fde9668867acfb4a95b19f03ce. -/
theorem nonadaptive_lower : ∃ (c ε₀ : ℝ) (d₀ : ℕ),
0 < c ∧ 0 < ε₀ ∧ 1 < d₀ ∧
∀ d : ℕ, d₀ ≤ d → ∀ ε : ℝ, 0 < ε → ε ≤ ε₀ →
∀ (N : ℕ) (P : Protocol d), IsNonadaptive P → Succeeds P N ε →
c * max ((d : ℝ)*Real.sqrt d/ε) ((d : ℝ)/ε^2) ≤ (N : ℝ) := by sorry
end IncoherentPurity.Adaptive.Supplement
Source
Lee–Wadhwa, Optimal Purity Estimation with Incoherent Measurements, STOC 2027 submission #66 (2026), preprint, pinned source.pdf; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/66.pdf; SHA-256 7d80a6695c9c0b12bfa088a8f47d2a298b93f9fde9668867acfb4a95b19f03ce; Theorem 5.1, PDF p.15 = printed p.15