Non-adaptive precision contribution
OpenIncoherentPurity.Adaptive.Supplement.nonadaptive_precision_lowerp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationstatistics
There is an absolute , which can be chosen at most , such that for every integer and , every non-adaptive incoherent protocol that estimates the purity of every -dimensional state to relative error with success probability at least needs
The bound covers arbitrary measurable single-copy POVMs and shared classical randomness in the published protocol model. It supplies the precision term of Theorem 5.1. The coefficient is the explicit witness established by Equation (5.17), rather than a claim about the optimal leading constant.
Differences from the source:
- encoding: Omega(d/epsilon squared) with a universal sufficiently small precision threshold → the proof witness N at least d/(576 epsilon squared), with an existential universal threshold at most 1/576; reason: Equation (5.17) gives this coefficient, and the Section 5 common threshold is chosen no larger than 1/576; no precision instance below the existential threshold is removed
Preamble
import Definitions.Def_IncoherentPurity_Adaptive_Supplement_Testing open MeasureTheory ProbabilityTheory Matrix open scoped ENNReal set_option autoImplicit false noncomputable section
Formal statement
namespace IncoherentPurity.Adaptive.Supplement
/-- Proposition 5.4, PDF = printed p.17; pinned source SHA-256 7d80a6695c9c0b12bfa088a8f47d2a298b93f9fde9668867acfb4a95b19f03ce. -/
theorem nonadaptive_precision_lower : ∃ ε₀ : ℝ, 0 < ε₀ ∧ ε₀ ≤ 1/576 ∧
∀ d : ℕ, 16 ≤ d → ∀ ε : ℝ, 0 < ε → ε ≤ ε₀ →
∀ (N : ℕ) (P : Protocol d), IsNonadaptive P → Succeeds P N ε →
(d : ℝ)/(576*ε^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; Proposition 5.4, PDF p.17 = printed p.17; Eq. (5.17) for the explicit proof witness