Structural Lower Bounds for Quantum Property Estimation with Persistent Memory
Abstract
In quantum property estimation, an experimenter estimates 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 D2−1 Paulis, eliminating the cubic loss in prior bounds. For growing weight-w Pauli strings (w=⌈log2 n⌉) and quadratic Majorana cross-correlations, it proves lower bounds of Ω(3w/ε2) and Ω(n2/(ε2(1+ln n)2)) against an indefinitely persistent memory of dimension K=⌊√n⌋. 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.
Related
- Quantum Tsallis Entropy Estimation: Near-Optimal Bounds and High-Precision Improvements
- Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
- Schurunicodex2013Weyl Reduction of Finite-Copy Precision Bounds for Multiparameter Quantum Estimation
- Local and Global Risk Bounds for Quantum Entropy Estimation under Projective-Design Measurements
- The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem
BibTeX
@misc{tao2026structural,
title = {{Structural Lower Bounds for Quantum Property Estimation with Persistent Memory}},
author = {Ye Tao and Hong Shen},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05792},
eprint = {2611.05792},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05792},
}
RIS
TY - UNPB
TI - Structural Lower Bounds for Quantum Property Estimation with Persistent Memory
AU - Ye Tao
AU - Hong Shen
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.05792
UR - https://arxiv.org/abs/2611.05792
AB - In quantum property estimation, an experimenter estimates 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=⌈log_2 n⌉) 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=⌊√n⌋. 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.
ER -