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.

to be published in IEEE Transactions on Information Theory

References in corpus (7)

• Quantum algorithm for solving linear systems of equations
• Fixed-point quantum search with an optimal number of queries
• A Variational Quantum Algorithm for Preparing Quantum Gibbs States
• 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

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