Quantum query complexity of entropy estimation

Tongyang Li, Xiaodi Wu

TL;DR

This paper introduces the first quantum algorithms for estimating various types of entropy (Shannon, Rényi, Hartley, min-entropy) and KL divergence. It achieves significant quantum speedups, including a quadratic speedup for Shannon entropy, and provides corresponding quantum lower bounds, establishing a more complete picture of quantum advantages in this domain.

What Problem Does This Paper Address?

Estimating the entropy of unknown probability distributions is a fundamental problem in statistics and information theory, with applications ranging from understanding randomness to data compression. While classical algorithms have well-established sample complexity bounds for these tasks, the quantum realm has remained largely unexplored. This paper aims to bridge this gap by developing quantum algorithms for estimating a broad class of entropies (Rényi entropies for all $\alpha \ge 0$) and related measures like KL divergence, and to characterize the quantum query complexity for these problems by providing both upper and lower bounds.

Methods

The authors build upon the framework of Bravyi, Harrow, and Hassidim (BHH) for quantum property testing. Their key technical contributions include:

  • Improved Error Analysis for Shannon and 0-Rényi Entropy: They leverage Montanaro's approach for estimating quantum subroutine expectations with bounded variance, combined with a fine-tuned error analysis, to achieve a quadratic speedup for Shannon entropy and a similar improvement for Hartley entropy ($\alpha=0$).
  • Recursive Approach for General $\alpha$-Rényi Entropy: For general $\alpha$-Rényi entropies, they develop a recursive procedure that approximates the entropy by iteratively refining estimates for $\alpha$ values closer to 1. This is likened to a "cooling schedule" in simulated annealing.
  • Reductions to Distinctness Problems: For integer $\alpha \ge 2$ and min-entropy ($\alpha = \infty$), they reduce the entropy estimation problem to the $\alpha$-distinctness and $[\log n]$-distinctness problems, respectively. This allows them to leverage existing quantum algorithms for these problems.
  • Quantum Lower Bounds: They establish quantum lower bounds for various ranges of $\alpha$ using techniques like reductions to known quantum query complexity problems (e.g., collision problem) and the polynomial method.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their query complexity, assuming access to an oracle representing the probability distribution.

Key Insights and Ideas

  • Quadratic Speedup for Shannon Entropy: The paper demonstrates that quantum computation can offer a quadratic advantage in estimating Shannon entropy, a significant improvement over classical methods.
  • Unified Framework for $\alpha$-Rényi Entropies: The development of a generic quantum speedup for $\alpha$-Rényi entropies across all $\alpha \ge 0$ provides a comprehensive quantum approach to entropy estimation.
  • Novel Recursive Strategy: The "cooling schedule" inspired recursive approach for general $\alpha$ is a novel technique for tackling the complexity of estimating entropies for a wide range of parameters.
  • Bridging Entropy and Distinctness: The reduction of entropy estimation to distinctness problems highlights a deep connection between these seemingly different computational tasks and allows for leveraging powerful quantum algorithms for distinctness.
  • Comprehensive Complexity Landscape: By providing both upper and lower bounds for various $\alpha$ values, the paper paints a detailed picture of the quantum query complexity for entropy estimation, revealing where quantum advantages are most pronounced.

Key Results

The paper presents several quantum algorithms with improved query complexities compared to classical counterparts:

  • Shannon Entropy ($\alpha=1$): Quadratic speedup, achieving $\tilde{O}(n^{1/2})$ quantum queries.
  • Hartley Entropy ($\alpha=0$): $\tilde{O}(\sqrt{n})$ quantum queries.
  • General $\alpha$-Rényi Entropy ($\alpha > 0$):
    • For $0 < \alpha < 1$: $\tilde{O}(n^{1/2\alpha})$ quantum queries.
  • For $\alpha > 1, \alpha \notin \mathbb{N}$: $\tilde{O}(n^{1-1/2\alpha})$ quantum queries.
  • For integer $\alpha > 1$: $\tilde{O}(n^{1-1/\alpha})$ quantum queries.
  • Min-Entropy ($\alpha = \infty$): $\tilde{O}(Q([\log n]\text{-distinctness}))$ quantum queries, where $Q$ is the quantum query complexity of the $[\log n]$-distinctness problem.
  • KL Divergence: $\tilde{O}(1/\epsilon^2)$ quantum queries to $p$ and $\tilde{O}(\sqrt{nf(n)})$ quantum queries to $q$, where $f(n)$ bounds the probability ratios.
  • Quantum Lower Bounds: The paper establishes lower bounds that match or are close to the upper bounds for various ranges of $\alpha$, confirming the optimality of their algorithms in many cases.

Limitations and Future Work

  • Gaps in Lower Bounds: While the paper provides tight bounds for many cases, some gaps remain between the quantum upper and lower bounds, particularly for certain ranges of $\alpha$.
  • Classical Ideas Integration: The authors suggest that incorporating classical ideas might lead to improved quantum results.
  • Quantum Adversary Method: Exploring the quantum adversary method could potentially yield better lower bounds.
  • k-Distinctness for Super-Constant k: The quantum algorithm for k-distinctness with super-constant k remains an open area for further research.
  • Min-Entropy Algorithm Dependence: The presented algorithm for min-entropy has a super-exponential dependence on $\alpha$, making it impractical for large $\alpha$. The paper notes that a separate algorithm is provided for this case.
  • Polynomial Method Analysis: The analysis of the polynomial method for lower bounds is currently focused on the degree in $d$ for $c=1$, and a more general analysis for both $c$ and $d$ is left as an open problem.

Summary updated

Abstract

Estimation of Shannon and R\'enyi entropies of unknown discrete distributions is a fundamental problem in statistical property testing and an active research topic in both theoretical computer science and information theory. Tight bounds on the number of samples to estimate these entropies have been established in the classical setting, while little is known about their quantum counterparts. In this paper, we give the first quantum algorithms for estimating $\alpha$-R\'enyi entropies (Shannon entropy being 1-Renyi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for $\alpha$-R\'enyi entropy estimation for all $\alpha\geq 0$, including a tight bound for the collision-entropy (2-R\'enyi entropy). We also provide quantum upper bounds for extreme cases such as the Hartley entropy (i.e., the logarithm of the support size of a distribution, corresponding to $\alpha=0$) and the min-entropy case (i.e., $\alpha=+\infty$), as well as the Kullback-Leibler divergence between two distributions. Moreover, we complement our results with quantum lower bounds on $\alpha$-R\'enyi entropy estimation for all $\alpha\geq 0$.
BibTeX
@article{li2017quantum,
  author = {Tongyang Li and Xiaodi Wu},
  title = {{Quantum query complexity of entropy estimation}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  doi = {10.1109/ted.2018.2832118},
}
Figure