Quantum algorithm for estimating Renyi entropies of quantum states

Abstract

We describe a quantum algorithm to estimate the $\alpha$-Renyi entropy of an unknown density matrix $\rho \in {\mathcal{C}}^{d\times d}$ for $\alpha \ne 1$ by combining the recent technique of quantum singular value transformations with the method of estimating normalised traces in the one clean qubit model. We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be non-singular. Our method outputs an estimate of the $\alpha$-Renyi entropy to additive precision $\epsilon$, using an expected total number $O\left(\frac{1}{(x\epsilon {)}^2}\right)$ of independent applications of a quantum circuit which coherently queries the input unitary $O\left(\frac{1}{\delta }\log \frac{d}{\epsilon }\right)$ times, in each case measuring a single output qubit. Here $\delta$ is a lower cutoff on the smallest eigenvalue of $\rho$ and $x=\frac{1}{d}\mathrm{Tr}{\rho }^{\alpha }$. The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require $\Theta (d^2/{\epsilon }^2)$ samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension $d$.

12 pages, updated with estimation to multiplicative precision, more references to existing work

References in corpus (10)

• Quantum algorithm for solving linear systems of equations
• Quantum discord and the power of one qubit
• Experimental quantum computing without entanglement
• Probing entanglement entropy via randomized measurements
• Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
• Quantum Computation Beyond the Circuit Model
• Computing partition functions in the one clean qubit model
• Implementing smooth functions of a Hermitian matrix on a quantum computer
• Do black holes store negative entropy?
• Second law of black hole thermodynamics

Cited by in corpus (25)

• Towards quantum advantage via topological data analysis
• Quantum Algorithm for Fidelity Estimation
• Measuring Quantum Entropy
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Quantum algorithms for estimating quantum entropies
• Multivariate trace estimation in constant quantum depth
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies
• Quantum simulation of in-medium QCD jets: momentum broadening, gluon production, and entropy growth
• Fast Quantum Algorithms for Trace Distance Estimation
• Estimating Quantum Mutual Information Through a Quantum Neural Network
• Quantum Neural Estimation of Entropies
• Variational quantum Gibbs state preparation with a truncated Taylor series
• In the shadow of the Hadamard test: Using the garbage state for good and further modifications
• The topology of data hides in quantum thermal states
• Quantum Tensor Product Decomposition from Choi State Tomography
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Time-Efficient Quantum Entropy Estimator via Samplizer
• Quantum Lower Bounds by Sample-to-Query Lifting
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Virtual Quantum Markov Chains
• Disentangling quantum neural networks for unified estimation of quantum entropies and distance measures
• Singular value transformation for unknown quantum channels
• Qubit frugal entanglement determination with the deep multi-scale entanglement renormalization ansatz
• Optimal Hamiltonian recognition of unknown quantum dynamics
• Performance Guarantees for Quantum Neural Estimation of Entropies