Non-adaptive purity estimation: tight copy complexity
OpenIncoherentPurity.Adaptive.Supplement.nonadaptive_copy_complexityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationstatistics
A non-adaptive incoherent protocol measures each fresh copy separately, chooses its entire POVM schedule before seeing outcomes, and may use shared classical randomness. It succeeds if, for every -dimensional state , its estimate obeys with probability at least .
There exist absolute constants and an integer such that, for every and , writing ,
Both statements allow arbitrary measurable POVM outcomes and the published shared-seed protocol model. The constants and thresholds are chosen before dimension, precision, budget or protocol. This companion theorem supplies the full non-adaptive characterization alongside the adaptive goal.
Differences from the source:
- encoding: Theta of the maximum rate → uniform positive constants and thresholds with operational existence and universal lower clauses; reason: this spells out both sides of the source asymptotic claim without changing any regime
- 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 1.2, PDF = printed p.4; pinned source SHA-256 7d80a6695c9c0b12bfa088a8f47d2a298b93f9fde9668867acfb4a95b19f03ce. -/
theorem nonadaptive_copy_complexity : ∃ (c C ε₀ : ℝ) (d₀ : ℕ),
0 < c ∧ 0 < C ∧ 0 < ε₀ ∧ 1 < d₀ ∧
∀ d : ℕ, d₀ ≤ d → ∀ ε : ℝ, 0 < ε → ε ≤ ε₀ →
(∃ (N : ℕ) (P : Protocol d), IsNonadaptive P ∧ Succeeds P N ε ∧
(N : ℝ) ≤ C * max ((d : ℝ)/ε^2) ((d : ℝ)*Real.sqrt d/ε)) ∧
(∀ (N : ℕ) (P : Protocol d), IsNonadaptive P → Succeeds P N ε →
c * max ((d : ℝ)/ε^2) ((d : ℝ)*Real.sqrt d/ε) ≤ (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 1.2, PDF p.4 = printed p.4