A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation

Abstract

Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating Rényi entropies as specific examples. In particular, given a quantum oracle that prepares an $n$-dimensional quantum state ${\sum }_{i=1}^n\sqrt{p_i}|i⟩$, for $\alpha >1$ and $0<\alpha <1$, our algorithm framework estimates $\alpha$-Rényi entropy $H_{\alpha }(p)$ to within additive error $\epsilon$ with probability at least $2/3$ using $\tilde{\mathcal{O}}(n^{1-\frac{1}{2\alpha }}/\epsilon +\sqrt{n}/{\epsilon }^{1+\frac{1}{2\alpha }})$ and $\tilde{\mathcal{O}}(n^{\frac{1}{2\alpha }}/{\epsilon }^{1+\frac{1}{2\alpha }})$ queries, respectively. This improves the best known dependence in $\epsilon$ as well as the joint dependence between $n$ and $1/\epsilon$. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications.

arXiv commentto be published in IEEE Transactions on Information Theory

References in corpus (25)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• On quantum Renyi entropies: a new generalization and some properties
• 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
• A Grand Unification of Quantum Algorithms
• Quantum speedup of Monte Carlo methods
• Fixed-point quantum search with an optimal number of queries
• A different kind of quantum search
• On Arbitrary Phases in Quantum Amplitude Amplification
• Quantum Speed-up for Approximating Partition Functions
• A Variational Quantum Algorithm for Preparing Quantum Gibbs States
• 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
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Quantum algorithms for estimating quantum entropies
• Fast Quantum Algorithms for Trace Distance Estimation
• Improved Quantum Algorithms for Fidelity Estimation
• Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
• The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
• Quantum algorithm for estimating volumes of convex bodies

Cited by in corpus (5)

• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• Time-Efficient Quantum Entropy Estimator via Samplizer
• Quantum Lower Bounds by Sample-to-Query Lifting
• Performance Guarantees for Quantum Neural Estimation of Entropies