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.
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.
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.
Estimating nonlinear properties such as Rényi entropies and observable-weighted moments serves as a central strategy for spectrum spectroscopy, which is fundamental to property prediction and analysis in quantum information science, statistical mechanics, and many-body physics. However, existing approaches are susceptible to noise and require significant resources, making them challenging for near-term quantum hardware. In this work, we introduce a framework for resource-efficient simultaneous estimation of quantum state moments via qubit reuse. For an m-qubit quantum state ρ, our method achieves the simultaneous estimation of the full hierarchy of moments Tr(ρ2),…,Tr(ρk), as well as arbitrary polynomial functionals and their observable-weighted counterparts. By leveraging qubit reset operations, our core circuit for simultaneous moment estimation requires only 2m+1 physical qubits and O(k) CSWAP gates, achieving a near-optimal sample complexity of O(klogk/ε2). We demonstrate this protocol's utility by showing that the estimated moments yield tight bounds on a state's maximum eigenvalue and present applications in quantum virtual cooling to access low-energy states of the Heisenberg model. Furthermore, we show the protocol's viability on near-term quantum hardware by experimentally measuring higher-order Rényi entropy on a superconducting quantum processor. Our method provides a scalable and resource-efficient route to quantum system characterization and spectroscopy on near-term quantum hardware.
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.
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.
Nonlinear properties of quantum states are essential to quantum information and many-body physics, but assessing them experimentally is challenging, as it typically requires multi-copy operations or a large number of measurement settings. To address this challenge, we develop a universal framework, collision-based nonlinear estimation (CBNE), for efficiently measuring nonlinear quantities of a quantum state ρ, such as the higher-order expectation value tr(Oρt) for some observable O, using single-copy randomized measurements. Strikingly, our protocol requires only a single measurement setting, provided that the system dimension is sufficiently large or a few ancillary qubits are available; this contrasts with the conventional expectation that multiple measurement bases are necessary for nonlinear estimation. In addition, CBNE is observable-independent at the experimental stage, which enables simultaneous estimation of multiple nonlinear functions. It further extends to broader tasks, including the estimation of principal component properties and partial-transpose moments of quantum states. Our results provide a practical and scalable route for measuring nonlinear state properties on near-term quantum devices.
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.