A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as Tr(ρ^{k}O). Intuitively, one expects that computing a kth order quantity generally requires O(k) copies of the state ρ, and we rigorously establish this lower bound under sample access to ρ. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of ρ, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of Θ(sqrt[k]) and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory-specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling and evaluating other multiple nonlinear quantum observables with classical shadows.
A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as Tr(ρ^{k}O). Intuitively, one expects that computing a kth order quantity generally requires O(k) copies of the state ρ, and we rigorously establish this lower bound under sample access to ρ. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of ρ, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of Θ(sqrt[k]) and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory-specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling and evaluating other multiple nonlinear quantum observables with classical shadows.
A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as Tr(ρkO). Intuitively, one expects that computing a k-th order quantity generally requires O(k) copies of the state ρ, and we rigorously establish this lower bound under sample access to ρ. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of ρ, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of Θ(k), and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory -- specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling, and evaluating other multiple nonlinear quantum observables with classical shadows.
We consider a fundamental task in quantum information theory, estimating the values of tr(Oρ), tr(Oρ2), . . . , tr(Oρk) for an observableOand a quantum state ρ. We show that Θ(k) samples of ρ are sufficient and necessary to simultaneously estimate all thekvalues. This means that estimating all thekvalues is almost as easy as estimating only one of them, tr(Oρk). As an application, our approach advances the sample complexity of entanglement spectroscopy and the virtual cooling for quantum many-body systems. Moreover, we extend our approach to estimating general functionals by polynomial approximation.
How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.
Estimating nonlinear functions of quantum states is essential for quantum information processing tasks such as entropy quantification, fidelity estimation, and entanglement spectroscopy. Existing approaches based on quantum state tomography incur exponential resource overhead, while methods relying on purified query access impose significant practical constraints. Here, we introduce the quantum state function framework, which extends the swap test via a linear combination of unitaries and parameterized quantum circuits. The framework estimates any normalized degree-n polynomial function of a quantum state with precision ε using O(n/ε2) copies, operating directly on identical copies without block-encoding or purified queries. Applied to von Neumann entropy, quantum relative entropy, and state fidelity, it achieves sample complexity O(γ2/(ε2κ)), where κ is the minimal nonzero eigenvalue and γ a normalization factor. This framework establishes a unified paradigm for nonlinear quantum state processing, broadening the toolkit for practical quantum data analysis. Estimating nonlinear functions of quantum states is essential for quantum information processing but often computationally expensive. The quantum state function framework estimates a degree-n polynomial of a quantum state with O(n/ε2) copies without purified query access, enabling practical entropy, fidelity, and eigenvalue estimation.
Estimating the trace of quantum state powers, Tr ( ρ k ) , for k identical quantum states is a fundamental task with numerous applications in quantum information processing, including nonlinear function estimation of quantum states and entanglement detection. On near-term quantum devices, reducing the required quantum circuit depth, the number of multi-qubit quantum operations, and the copies of the quantum state needed for such computations is crucial. In this work, inspired by the Newton-Girard method, we significantly improve upon existing results by introducing an algorithm that requires only O ( r ~ ) qubits and O ( r ~ ) multi-qubit gates, where r ~ = min { rank ( ρ ) , ⌈ ln ( 2 k / ϵ ) ⌉ } . This approach is efficient, as it employs the r ~ -entangled copy measurement instead of the conventional k -entangled copy measurement, while asymptotically preserving the known sample complexity upper bound. Furthermore, we prove that estimating { Tr ( ρ i ) } i = 1 r ~ is sufficient to approximate Tr ( ρ k ) even for large integers k > r ~ . This leads to a rank-dependent complexity for solving the problem, providing an efficient algorithm for low-rank quantum states while also improving existing methods when the rank is unknown or when the state is not low-rank. Building upon these advantages, we extend our algorithm to the estimation of Tr ( M ρ k ) for arbitrary observables and Tr ( ρ k σ l ) for multiple quantum states.
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.