New Quantum Algorithms for Computing Quantum Entropies and Distances

Abstract

We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances, including the von Neumann entropy, quantum Rényi entropy, trace distance, and fidelity. The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case, some of which achieve exponential speedups. In particular, for $N$-dimensional quantum states of rank $r$, our proposed quantum algorithms for computing the von Neumann entropy, trace distance and fidelity within additive error $\epsilon$ have time complexity of $\tilde{O}(r/{\epsilon }^2)$, $\tilde{O}(r^5/{\epsilon }^6)$ and $\tilde{O}(r^{6.5}/{\epsilon }^{7.5})$, respectively. By contrast, prior quantum algorithms for the von Neumann entropy and trace distance usually have time complexity $\Omega (N)$, and the prior best one for fidelity has time complexity $\tilde{O}(r^{12.5}/{\epsilon }^{13.5})$. The key idea of our quantum algorithms is to extend block-encoding from unitary operators in previous work to quantum states (i.e., density operators). It is realized by developing several convenient techniques to manipulate quantum states and extract information from them. The advantage of our techniques over the existing methods is that no restrictions on density operators are required; in sharp contrast, the previous methods usually require a lower bound on the minimal non-zero eigenvalue of density operators.

Final version. 58 pages, 5 tables, 1 figure. Minor corrections to Theorem 3.1, Theorem 3.4, and Corollary 3.5

References in corpus (53)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• Quantum fingerprinting
• Quantum state tomography via compressed sensing
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• On quantum Renyi entropies: a new generalization and some properties
• The operational meaning of min- and max-entropy
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Renyi relative entropy
• Min- and Max- Relative Entropies and a New Entanglement Monotone
• Universal Quantum Estimator
• Direct estimations of linear and non-linear functionals of a quantum state
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Simulating Physical Phenomena by Quantum Networks
• Quantum speedup of Monte Carlo methods
• A quantum-inspired classical algorithm for recommendation systems
• Sample-optimal tomography of quantum states
• Quantum singular value decomposition of non-sparse low-rank matrices
• Variational Quantum Fidelity Estimation
• Hamiltonian Simulation with Optimal Sample Complexity
• Some general properties of unified entropies
• Subadditivity of q-entropies for q>1
• Quantum algorithm for Petz recovery channels and pretty good measurements
• The structure of Renyi entropic inequalities
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• A Variational Quantum Algorithm for Preparing Quantum Gibbs States
• Direct Fidelity Estimation of Quantum States using Machine Learning
• Quantum algorithm for estimating Renyi entropies of quantum states
• Quantum Algorithm for Fidelity Estimation
• A Survey of Quantum Property Testing
• Quantum algorithms for testing properties of distributions
• Measuring Quantum Entropy
• Estimating distinguishability measures on quantum computers
• Quantum algorithms for estimating quantum entropies
• Renyi-entropic bounds on quantum communication
• Distributed quantum inner product estimation
• Variational quantum algorithms to estimate rank, quantum entropies, fidelity and Fisher information via purity minimization
• Fast Quantum Algorithms for Trace Distance Estimation
• Improved Quantum Algorithms for Fidelity Estimation
• Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems
• Quantum Neural Estimation of Entropies
• Some inequalities for quantum Tsallis entropy related to the strong subadditivity
• Spectral thresholding quantum tomography for low rank states
• Quantum polar decomposition algorithm
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• The quantum low-rank approximation problem
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• Space-bounded quantum state testing via space-efficient quantum singular value transformation
• Asymptotically Optimal Quantum Amplitude Estimation by Generalized Qubitization

Cited by in corpus (13)

• Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems
• Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
• Quantum algorithms for matrix geometric means
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• Topologically protected negative entanglement
• QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
• Time-Efficient Quantum Entropy Estimator via Samplizer
• Evolved Quantum Boltzmann Machines
• Quantum Lower Bounds by Sample-to-Query Lifting
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Disentangling quantum neural networks for unified estimation of quantum entropies and distance measures
• Virtual Quantum Markov Chains
• Performance Guarantees for Quantum Neural Estimation of Entropies