Theorem 2.5 — finite Pauli copy bounds
OpenPersistQMem.Supplement.theorem_2_5p2o-gran-per-chapterp2o-plan-paperp2o-v1pauli-operatorsquantum-informationquantum-memorysample-complexity
Let , , , and . Request all canonical weight- Pauli means simultaneously. For every integer with , define
Every successful persistent-memory receiver with worst-case copy cap satisfies
Conversely, the cap
is achievable with retained quantum dimension one, and hence under any cap . The lower bound holds for every legal .
Differences from the source:
- encoding: the least worst-case budget and its two inequalities → every achievable cap is lower-bounded and the displayed cap is explicitly achievable; reason: this is equivalent on the finite Pauli task and avoids a default value for an empty infimum
- encoding: an arbitrary final measurement producing a real output vector → a jointly measurable POVM density on the same real-vector output space against an s-finite reference kernel; reason: this is the measurable density representation used by the published protocol model and changes no receiver instance
- encoding: the set → an arbitrary enumeration certified equivalent to the canonical weight- labels; reason: ordering the same finite family changes no task instance
Preamble
import Mathlib import Definitions.Def_PersistQMem_Supplement_Achievable import Definitions.Def_PersistQMem_Supplement_IsWeightPauliFamily set_option autoImplicit false
Formal statement
namespace PersistQMem
namespace Supplement
/-- **Theorem 2.5 (Finite Pauli copy bounds), pp.5--6** (Tao--Shen, *Structural
Lower Bounds for Quantum Property Estimation with Persistent Memory*, STOC 2027 submission,
manuscript of 2026-11-03, sha256 6d48ad24..., Theorem 2.5, (9)--(10), pp.5--6,
PDF pp.8--9).
For `n >= 2`, `1 <= w <= n`, `K >= 1`, `0 < epsilon <= 1/8`, and every integer
`p >= 1` with `2p >= w`, put
`M = 3^w binom(n,w)` and
`B = min{1, K^(w/(2p)) (n + sqrt(8np))^w / (M w!)} + (2K-2)/M`.
Every successful persistent-`K` receiver with copy cap `N` has
`1/(20 epsilon^2 B) <= N`, while the displayed ceiling is achievable with retained dimension
one (and hence also under cap `K`).
**Formalization Note.** Instead of taking a potentially default-valued infimum called `N*`, the two
budget inequalities are stated operationally: every achievable cap obeys the lower bound, and the
upper cap is explicitly achievable. `IsWeightPauliFamily` supplies an enumeration of exactly the
canonical Hermitian strings. The fractional power is `Real.rpow`. -/
theorem theorem_2_5 (n w K : Nat) (hn : 2 <= n) (hw0 : 1 <= w) (hwn : w <= n)
(hK : 1 <= K) (epsilon : Real) (he0 : 0 < epsilon) (he1 : epsilon <= 1 / 8)
(p : Nat) (hp0 : 1 <= p) (hpw : w <= 2 * p)
(G : Fin (weightPauliCount n w) -> Matrix (Fin (2 ^ n)) (Fin (2 ^ n)) Complex)
(hG : IsWeightPauliFamily n w G) :
let M := weightPauliCount n w
let B := min 1
(Real.rpow (K : Real) ((w : Real) / (2 * (p : Real))) *
((n : Real) + Real.sqrt (8 * (n : Real) * (p : Real))) ^ w /
((M : Real) * (Nat.factorial w : Real))) +
(2 * (K : Real) - 2) / (M : Real)
let U := ⌈(13 / 6 : Real) * (3 : Real) ^ w * epsilon⁻¹ ^ 2 *
Real.log (6 * (M : Real))⌉₊
(forall N, Achievable G K epsilon N ->
1 / (20 * epsilon ^ 2 * B) <= (N : Real)) /\
Achievable G K epsilon U /\ Achievable G 1 epsilon U := 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.5, (9)–(10), pp.5–6 (PDF pp.8–9)