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.
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=⌈log2n⌉) and quadratic Majorana cross-correlations, it proves lower bounds of Ω(3w/ε2) and Ω(n2/(ε2(1+lnn)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.
Optimal single-copy estimation of quantum state moments: why Tr(ρ3) and Tr(ρ4) are equally hard
Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments Tr(ρt), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(d) at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer t≥2: for any sufficiently small constant additive error, the optimal sample complexity is Θ(d1+⌈log2t⌉⌈log2t⌉) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1, all moment orders 2h−1<t≤2h share the same exponent. In particular, the third and fourth moments both require Θ(d2/3) copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. We also establish an Ω(d1−1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t≥4. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond d.
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr(φ(dρ))/d, where ρ is an unknown d-dimensional quantum state and φ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ) from properties of φ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting.
The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ(εlog2(d)max{1,εlog2(d)}d2+ε2log2(d)), and the sample complexity of spectrum estimation is Θ(ε2log2(d)max{1,ε2log2(d)}d2). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown d-dimensional quantum state ρ and a known collection of observables E1,…,EM, the goal is to estimate all expectation values {Tr(ρEi)}i=1M to additive accuracy ε with probability at least 1−δ.
An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on M, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(ε2log(M)log(M/δ)), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright.
Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.
We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum stateρ, estimate Tr(Pρ)for some set of Pauli operatorsFto within additive errorϵ. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate∣Tr(Pρ)for allPusingO(n/ϵ4)copies, but withk≤nqubits of memory,Ω(2(n−k)/3)copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence onϵ?What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subsetAof Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up tolog∣A∣factors. •We show any protocol that makes poly(n)-copy measure-ments must makeΩ(1/ϵ4)measurements. •For any protocol that makes poly(n)-copy measurements and only hask<nqubits of memory, we show thatΘ~(min{2n/ϵ2,2n−k/ϵ4})copies are necessary and sufficient. The protocols we propose can also estimate the actual valuesTr(Pρ), rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be Θ(din3dout3/ε2), where din and dout are the channel input and output dimensions, respectively, and ε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires Ω(din3dout3/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound O(din3dout3/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case din=1. By contrast, coherent protocols with quantum memory achieve query complexity Θ(din2dout2/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown n-qubit state, but may keep only k qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test n-qubit stabilizer states using 6 copies, which is dimension independent, unlike the learning complexity of Θ(n). We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that
(1) The sample complexity of testing stabilizer states in the k-qubit memory framework is Θ(n−k). Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group.
(2) The sample complexity of learning stabilizer states with k qubits of memory, in the non-adaptive framework, is Θ(n2/k).
As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with k=0.99n qubits of memory, there is no constant-copy stabilizer tester; furthermore for k=cn qubits of memory (for 0<c<1), stabilizer testing is as hard as learning, with both requiring Θ(n) copies.