Theorem 2.8 — complete-Pauli specialization
OpenPersistQMem.Supplement.theorem_2_8p2o-gran-per-chapterp2o-plan-paperp2o-v1pauli-operatorsquantum-informationquantum-memorysample-complexity
Let , let be all nonidentity canonical Pauli operators with the uniform prior, and let with . Then the structural quantities are exactly
Every persistent-memory receiver estimating all expectations with simultaneous signed error and success probability at least for every state satisfies
If , this implies the explicit absolute-constant bounds .
Differences from the source:
- encoding: the unordered complete Pauli set → an arbitrary enumeration certified equivalent to all nonidentity canonical words; reason: ordering the same family changes neither the profile nor the task
- encoding: every receiver in the persistent-memory model → every achievable cap under the published protocol and a measurable real-vector terminal POVM density; reason: this unfolds the same universal operational claim using the source model's density representation
- reading: with an unspecified absolute constant → the consequences and ; reason: these explicit constants follow from the displayed exact bound for and
Preamble
import Mathlib import Definitions.Def_PersistQMem_ProfileData import Definitions.Def_PersistQMem_Supplement_Achievable import Definitions.Def_PersistQMem_Supplement_IsWeightPauliFamily set_option autoImplicit false
Formal statement
namespace PersistQMem
namespace Supplement
/-- **Theorem 2.8 (Complete-Pauli specialization), p.8** (Tao--Shen, *Structural Lower
Bounds for Quantum Property Estimation with Persistent Memory*, STOC 2027 submission,
manuscript of 2026-11-03, sha256 6d48ad24..., Theorem 2.8, (19), p.8, PDF p.11).
For all `D = 2^n >= 2`, the complete nonidentity canonical Pauli family with uniform prior has the
three exact profile values in (19). Every successful persistent-memory receiver obeys the exact copy
lower bound. When `K <= D`, the last two inequalities give an explicit absolute-constant form of the
paper's `Omega(D/(K epsilon^2))` clause.
**Formalization Note.** `G` is any enumeration of the exact canonical family, pinned by
`IsCompletePauliFamily`; `p` is `uniformPrior`. The final asymptotic clause is rendered with the
absolute constants `1/40` and `1/80`, rather than an unquantified big-O predicate. -/
theorem theorem_2_8 (n K : Nat) (hn : 1 <= n) (hK : 1 <= K)
(epsilon : Real) (he0 : 0 < epsilon) (he1 : epsilon <= 1 / 8)
(G : Fin (completePauliCount n) -> Matrix (Fin (2 ^ n)) (Fin (2 ^ n)) Complex)
(hG : IsCompletePauliFamily n G) :
let D := 2 ^ n
let M := completePauliCount n
let p := uniformPrior M
let q := min K D
gramNorm G p = 1 / ((D : Real) ^ 2 - 1) /\
profile G p K = ((D : Real) * (q : Real) - 1) / ((D : Real) ^ 2 - 1) /\
budget G p K =
((D : Real) * (q : Real) + 2 * (K : Real) - 3) / ((D : Real) ^ 2 - 1) /\
(forall N : Nat, Achievable G K epsilon N ->
((D : Real) ^ 2 - 1) /
(20 * epsilon ^ 2 * ((D : Real) * (q : Real) + 2 * (K : Real) - 3)) <=
(N : Real)) /\
(K <= D -> forall N : Nat, Achievable G K epsilon N ->
((D : Real) - 1) / (40 * (K : Real) * epsilon ^ 2) <= (N : Real) /\
(D : Real) / (80 * (K : Real) * epsilon ^ 2) <= (N : Real)) := by sorry
end Supplement
end PersistQMem
Source
Tao, Shen, Structural Lower Bounds for Quantum Property Estimation with Persistent Memory, STOC 2027 submission (manuscript of 2026-11-03, sha256 6d48ad24…), Theorem 2.8, (19), p.8 (PDF p.11)