Structural Lower Bounds for Quantum Property Estimation with Persistent Memory
Ye Tao, Hong Shen
quant-ph
Nov 4, 2026 · v1
TL;DR
Lean 4 was used, with AI assistance, to verify an earlier formalization of the complete-Pauli lower bound; no Lean artifact is cited.
Abstract
In quantum property estimation, an experimenter estimates $\operatorname{Tr}(Oρ)$ for a family of observables from independent copies of an unknown state $ρ$ simultaneously to additive error $ε$. While quantum memory can dramatically reduce sample complexity, understanding the power of a modest register that remains coherent throughout an adaptive experiment has remained an open challenge because existing frameworks require optimizing over the infinite space of measurement trees. We overcome this barrier by developing a backward-induction framework based on operator resolvents. Rather than tracking path-dependent memory states across rounds, resolvent regularization cancels internal memory trajectories exactly, reducing the lower bound to an algebraic certificate computed directly from the target observables with sharp $Ω(1/ε^2)$ scaling. Our structural rule charges only the retained dimension $K$ under arbitrary adaptive instruments and unrestricted memory lifetime. Via symmetry reductions, it yields polynomial-size linear programs that establish the optimal linear $Ω(D/(Kε^2))$ trade-off for the $D^2-1$ Paulis, eliminating the cubic loss in prior bounds. For growing weight-$w$ Pauli strings ($w=\lceil\log_2 n\rceil$) and quadratic Majorana cross-correlations, it proves lower bounds of $Ω(3^w/ε^2)$ and $Ω(n^2/(ε^2(1+\ln n)^2))$ against an indefinitely persistent memory of dimension $K=\lfloor\sqrt n\rfloor$. These bounds match memoryless or commuting estimators within polylogarithmic factors, demonstrating that rank constraints on the persistent register fundamentally throttle observable overlap and prevent a modest coherent memory from overcoming the sample complexity barrier.
Problem
How many copies of an unknown quantum state are needed to estimate many observable expectation values to error ε? The question is asked for an adaptive receiver that keeps a modest coherent quantum memory of dimension K for the whole experiment. Existing frameworks require optimizing over infinite spaces of measurement trees and give loose bounds.
Approach
A backward-induction framework based on operator resolvents cancels path-dependent memory trajectories. This reduces the lower bound to an algebraic certificate (a Gram norm β and a rank-constrained source profile ζ(K)) computed from the target observables. Symmetry reductions yield polynomial-size linear programs, and moment bounds are used to evaluate the profile for Pauli and Majorana families. Lean 4 was used to verify an earlier formalization of the complete-Pauli lower bound.
Results
The framework gives the optimal Ω(D/(Kε²)) trade-off for all D²−1 Paulis, removing the cubic loss in prior bounds. With K=⌊√n⌋, it gives Ω(3^w/ε²) for weight-w Pauli strings (w=⌈log₂ n⌉) and Ω(n²/(ε²(1+ln n)²)) for quadratic Majorana cross-correlations. These bounds match memoryless or commuting estimators up to polylogarithmic factors.