Resource-efficient algorithm for estimating the trace of quantum state powers

Abstract

Estimating the trace of quantum state powers, $\text{Tr}({\rho }^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 $\mathcal{O}(\tilde{r})$ qubits and $\mathcal{O}(\tilde{r})$ multi-qubit gates, where $\tilde{r}=\min \left\{\text{rank}(\rho ),\lceil \ln \left(2k/\epsilon \right)\rceil \right\}$. This approach is efficient, as it employs the $\tilde{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 $\{\text{Tr}({\rho }^i){\}}_{i=1}^{\tilde{r}}$ is sufficient to approximate $\text{Tr}({\rho }^k)$ even for large integers $k>\tilde{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 $\text{Tr}(M{\rho }^k)$ for arbitrary observables and $\text{Tr}({\rho }^k{\sigma }^l)$ for multiple quantum states.

45 pages, 9 figures, 4 tables, The first two authors (MS, JL) contributed equally to this work

References in corpus (25)

• Quantum principal component analysis
• Quantum fingerprinting
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Direct estimations of linear and non-linear functionals of a quantum state
• Universal Quantum Estimator
• Mixed-state entanglement from local randomized measurements
• Bipartite Fluctuations as a Probe of Many-Body Entanglement
• Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
• Thermalization in Nature and on a Quantum Computer
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Direct measurement of non-linear properties of bipartite quantum states
• The power of random measurements: measuring Tr(ρ^n) on single copies of ρ
• Variational Thermal Quantum Simulation via Thermofield Double States
• Modelling and Simulating the Noisy Behaviour of Near-term Quantum Computers
• Unitary $n$-designs via random quenches in atomic Hubbard and Spin models: Application to the measurement of Rényi entropies
• Hamiltonian Simulation with Optimal Sample Complexity
• Entanglement spectroscopy on a quantum computer
• Quantum circuits for measuring weak values, Kirkwood--Dirac quasiprobability distributions, and state spectra
• Beyond the swap test: optimal estimation of quantum state overlap
• Entanglement spectroscopy with a depth-two quantum circuit
• Qubit-efficient entanglement spectroscopy using qubit resets
• Multivariate trace estimation in constant quantum depth
• Variational Gibbs State Preparation on NISQ devices
• Unified multivariate trace estimation and quantum error mitigation
• Cycle Index Polynomials and Generalized Quantum Separability Tests

Cited by in corpus (1)

• Estimation of multivariate traces of states given partial classical information