Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices

• URL: http://arxiv.org/abs/2509.01571v1
• Date: Mon, 01 Sep 2025 15:56:49 GMT
• Title: Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices
• Authors: Yukun Zhang, Yusen Wu, You Zhou, Xiao Yuan,
• Abstract summary: A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as $mathrmTr(rhok O)$.<n>We present a quadratic quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods.<n>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.
• Score: 6.701793676773711
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as $\mathrm{Tr}(\rho^k O)$. Intuitively, one expects that computing a $k$-th order quantity generally requires $O(k)$ copies of the state $\rho$, and we rigorously establish this lower bound under sample access to $\rho$. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of $\rho$, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of $\Theta(\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.

Related papers

• Near-Optimal Simultaneous Estimation of Quantum State Moments [7.1834855718325805]
  We introduce a framework for resource-efficient simultaneous estimation of quantum state moments via qubit reuse.<n>By leveraging qubit reset operations, our core circuit for simultaneous moment estimation requires only $2m+1$ physical qubits and $mathcalO(k)$ CSWAP gates.<n>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.
  arXiv  Detail & Related papers  (2025-09-29T14:23:26Z)
• Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States [16.185988658474635]
  We prove that estimation of $mathrmtr(rhok O)$ for a broad class of observables $O$ is exponentially hard for any protocol restricted to $(k-1)$-replica joint measurements.<n>Results establish, for the first time, an exponential separation between $(k-1)$- and $k$-replica protocols for any integer $k>2$.
  arXiv  Detail & Related papers  (2025-09-28T17:46:43Z)
• Sample-Efficient Estimation of Nonlinear Quantum State Functions [5.641998714611475]
  We introduce the quantum state function (QSF) framework by extending the SWAP test via linear combination of unitaries and parameterized quantum circuits.<n>Our framework enables the implementation of arbitrarily normalized degree-$n$ functions of quantum states with precision.<n>We apply QSF for developing quantum algorithms for fundamental tasks, including entropy, fidelity, and eigenvalue estimations.
  arXiv  Detail & Related papers  (2024-12-02T16:40:17Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• One-Shot Min-Entropy Calculation Of Classical-Quantum States And Its Application To Quantum Cryptography [21.823963925581868]
  We develop a one-shot lower bound calculation technique for the min-entropy of a classical-quantum state.<n>It offers an alternative tight finite-data analysis for the BB84 quantum key distribution scheme.<n>It gives the best finite-key bound known to date for a variant of device independent quantum key distribution protocol.
  arXiv  Detail & Related papers  (2024-06-21T15:11:26Z)
• Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
  We present a model for parallelizing simulation of quantum circuit executions. The model can take advantage of its backend-agnostic features, enabling parallel quantum circuit execution over any target backend.
  arXiv  Detail & Related papers  (2024-06-05T17:16:07Z)
• Quantum quench dynamics as a shortcut to adiabaticity [31.114245664719455]
  We develop and test a quantum algorithm in which the incorporation of a quench step serves as a remedy to the diverging adiabatic timescale. Our experiments show that this approach significantly outperforms the adiabatic algorithm.
  arXiv  Detail & Related papers  (2024-05-31T17:07:43Z)
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix [0.0]
  Learning about physical systems from quantum-enhanced experiments can outperform learning from experiments in which only classical memory and processing are available. We show that a quantum memory allows to efficiently solve the following tasks. Our results highlight the power of quantum-enhanced experiments for learning highly complex quantum dynamics.
  arXiv  Detail & Related papers  (2022-12-08T18:46:06Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quantum variational learning for entanglement witnessing [0.0]
  This work focuses on the potential implementation of quantum algorithms allowing to properly classify quantum states defined over a single register of $n$ qubits. We exploit the notion of "entanglement witness", i.e., an operator whose expectation values allow to identify certain specific states as entangled. We made use of Quantum Neural Networks (QNNs) in order to successfully learn how to reproduce the action of an entanglement witness.
  arXiv  Detail & Related papers  (2022-05-20T20:14:28Z)
• Quantum algorithms for estimating quantum entropies [6.211541620389987]
  We propose quantum algorithms to estimate the von Neumann and quantum $alpha$-R'enyi entropies of an fundamental quantum state. We also show how to efficiently construct the quantum entropy circuits for quantum entropy estimation using single copies of the input state.
  arXiv  Detail & Related papers  (2022-03-04T15:44:24Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.