Quantum query complexity of entropy estimation
Tongyang Li∗

Xiaodi Wu†

arXiv:1710.06025v1 [quant-ph] 16 Oct 2017

Department of Computer Science, Institute for Advanced Computer Studies, and
Joint Center for Quantum Information and Computer Science, University of Maryland, USA

Abstract
Estimation of Shannon and Rényi 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 αRényi 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 α-Rényi entropy estimation for all α ≥ 0, including a tight bound for the collision-entropy
(2-Rényi 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 α = 0) and
the min-entropy case (i.e., α = +∞), as well as the Kullback-Leibler divergence between two
distributions. Moreover, we complement our results with quantum lower bounds on α-Rényi
entropy estimation for all α ≥ 0.
Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH) [13]
on quantum algorithms for distributional property testing, however, with many new technical
ingredients. For Shannon entropy and 0-Rényi entropy estimation, we improve the performance
of the BHH framework, especially its error dependence, using Montanaro’s approach to estimating the expected output value of a quantum subroutine with bounded variance [41] and
giving a fine-tuned error analysis. For general α-Rényi entropy estimation, we further develop
a procedure that recursively approximates α-Rényi entropy for a sequence of αs, which is in
spirit similar to a cooling schedule in simulated annealing. For special cases such as integer
α ≥ 2 and α = +∞ (i.e., the min-entropy), we reduce the entropy estimation problem to the
α-distinctness and the dlog ne-distinctness problems, respectively. We exploit various techniques
to obtain our lower bounds for different ranges of α, including reductions to (variants of) existing lower bounds in quantum query complexity as well as the polynomial method inspired by
the celebrated quantum lower bound for the collision problem.

∗
†

tongyang@cs.umd.edu
xwu@cs.umd.edu

1

Introduction

Motivations. Property testing is a rapidly developing field in theoretical computer science (e.g. see
the survey [55]). It aims to determine properties of an object with the least number of independent
samples of the object. Property testing is a theoretically appealing topic with intimate connections
to statistics, learning theory, and algorithm design. One important topic in property testing is to
estimate statistical properties of unknown distributions (e.g., [61]), which are fundamental questions
in statistics and information theory, given that much of science relies on samples furnished by nature.
The Shannon [56] and Rényi [54] entropies are central measures of randomness compressibility. In
this paper, we focus on estimating these entropies for an unknown distribution.
Specifically, given a distribution p over a set X of size n (w.l.o.g. let X = [n]) where px denotes
the probability of x ∈ X, the Shannon entropy H(p) of this distribution p is defined by
1
X
H(p) :=
px log
.
(1.1)
px
x∈X: px >0

A natural question is to determine the sample complexity (i.e., the necessary number of independent samples from p) to estimate H(p), with error  and high probability. This problem has been
intensively studied in the classical literature. For multiplicative error , Batu et al. [7, Theorem
2
2] provided the upper bound of O(n(1+o(1))/(1+) log n), while an almost matching lower bound of
2
Ω(n(1−o(1))/(1+) ) was shown by Valiant [61, Theorem 1.3]. For additive errors, Paninski gave a
nonconstructive proof of the existence of sublinear estimators in [49, 50], while an explicit construction using Θ(n/ log n) samples was shown by Valiant and Valiant in [60] when  > n−0.03 ;
for the case  ≤ n−0.03 , Wu and Yang [64] and Jiao et al. [34] gave the optimal estimator with
(log n)2
n
Θ(  log
) samples. A sequence of works in information theory [33, 34, 64] studied the
n +
2
minimax mean-squared error, which becomes O(1) also using Θ(n/ log n) samples.
One important generalization of Shannon entropy is the Rényi entropy of order α > 0, denoted
Hα (p), which is defined by
(
P
1
log x∈X pαx , when α 6= 1.
1−α
(1.2)
Hα (p) :=
limα→1 Hα (p),
when α = 1.
The Rényi entropy of order 1 is simply the Shannon entropy, i.e., H1 (p) = H(p). General Rényi
entropy can be used as a bound on Shannon entropy, making it useful in many applications (e.g.,
[6, 17]). Rényi entropy is also of interest in its own right. One prominent example is the Rényi
entropy of order 2, H2 (p) (also known as the collision entropy), which measures the quality of
random number generators (e.g., [62]) and key derivation in cryptographic applications (e.g., [11,
32]). Motivated by these and other applications, the estimation of Rényi entropy has also been
actively studied [4, 33, 34]. In particular, Acharya et al. [4] have shown almost tight bounds on
the classical query complexity of computing Rényi entropy. Specifically, for any non-integer α > 1,
the classical query complexity of α-Rényi entropy is Ω(n1−o(1) ) and O(n). Surprisingly, for any
integer α > 1, the classical query complexity is Θ(n1−1/α ), i.e., sublinear in n. When 0 ≤ α < 1,
the classical query complexity is Ω(n1/α−o(1) ) and O(n1/α ), which is always superlinear.
The extreme case (α → ∞) is known as the min-entropy, denoted H∞ (p), which is defined by
H∞ (p) := lim Hα (p) = − log max pi .
α→∞

(1.3)

i∈[n]

Min-entropy plays an important role in the randomness extraction (e.g., [59]) and characterizes the
maximum number of uniform bits that can be extracted from a given distribution. Classically, the
query complexity of min-entropy estimation is Θ(n/ log n), which follows directly from [60].
1

Another extreme case (α = 0), also known as the Hartley entropy [29], is the logarithm of the
support size of distributions, where the support of any distribution p is defined by
Supp(p) := |{x : x ∈ X, px > 0}|.

(1.4)

It is a natural and fundamental quantity of distributions with various applications (e.g., [20, 22, 26,
31, 36, 51, 58]). However, estimating the support size is impossible in general because elements with
negligible but nonzero probability, which are very unlikely to be sampled, could still contribute to
Supp(p). Two related quantities (support coverage and support size) have hence been considered
as alternatives of 0-Rényi entropy with roughly Θ(n/ log(n)) complexity. (See details in Section 8.)
Besides the entropic measures of a discrete distribution, we also briefly discuss an entropic measure between two distributions, namely the Kullback-Leibler (KL) divergence. Given two discrete
distributions p and q with cardinality n, the KL divergence is defined as
X
pi
pi log .
DKL (pkq) =
(1.5)
qi
i∈[n]

KL divergence is a key measure with many applications in information theory [18, 37], data compression [15], and learning theory [35]. Classically, under the assumption that pqii ≤ f (n) ∀ i ∈ [n]
for some f (n), DKL (pkq) can be approximated within constant additive error with high success
(n)
probability if Θ( logn n ) samples are taken from p and Θ( nf
log n ) samples are taken from q.
Main question. In this paper, we study the impact of quantum computation on estimation of
general Rényi entropies. Specifically, we aim to characterize quantum speed-ups for estimating
Shannon and Rényi entropies.
Our question aligns with the emerging topic called “quantum property testing” (see the survey
[43]) and focuses on investigating the quantum advantage in testing classical statistical properties.
To the best of our knowledge, the first research paper on distributional quantum property testing is
by Bravyi, Harrow, and Hassidim (BHH) [13], where they discovered quantum speedups for testing
uniformity, orthogonality, and statistical difference on unknown distributions. Some of these results
were subsequently improved by Chakraborty et al. [16]. Reference [13] also claimed that Shannon
√
entropy could be estimated with query complexity O( n), however, without details and explicit
error dependence. Indeed, our framework is inspired by [13], but with significantly new ingredients
to achieve our results. There is also a related line of research on spectrum testing or tomography
of quantum states [25, 45–47]. However, these works aim to test properties of general quantum
states, while we focus on using quantum algorithms to test properties of classical distributions (i.e.,
diagonal quantum states)1 .
Distributions as oracles. The sampling model in the classical literature assumes that a tester
is presented with independent samples from an unknown distribution. One of the contributions
of BHH is an alternative model that allows coherent quantum access to unknown distributions.
Specifically, BHH models a discrete distribution p = (pi )ni=1 on [n] by an oracle Op : [S] → [n] for
some S ∈ N. The probability pi (i ∈ [n]) is proportional to the size of pre-image of i under Op .
Namely, an oracle Op : [S] → [n] generates p if and only if for all i ∈ [n],
pi = |{s ∈ [S] : Op (s) = i}|/S.

(1.6)

(note that we assume pi s to be rational numbers). If one samples s uniformly from [S], then the
output Op (s) is from distribution p. Instead of considering sample complexity—that is, the number
1

Note that one can also leverage the results of [25, 45–47] to test properties of classical distributions. However,
they are less efficient because they deal with a much harder problem involving general quantum states.

2

of used samples—we consider the query complexity in the oracle model that counts the number of
oracle uses. Note that a tester interacting with an oracle can potentially be more powerful due to
the possibility of learning the internal structure of the oracle as opposed to the sampling model.
However, it is shown in [13] that the query complexity of the oracle model and the sample complexity
of the sampling model are in fact the same classically.
A significant advantage of the oracle model is that it naturally allows coherent access when
extended to the quantum case, where we transform Op into a unitary operator Ôp acting on CS ⊗
Cn+1 such that
Ôp |si|0i = |si|Op (s)i

∀ s ∈ [S].

(1.7)

Moreover, this oracle model can also be readily obtained in some algorithmic settings, e.g., when
distributions are generated by some classical or quantum sampling procedure. Thus, statistical
property testing results in this oracle model can be potentially leveraged in algorithm design.
Our Results. Our main contribution is a systematic study of both upper and lower bounds for
the quantum query complexity of estimation of Rényi entropies (including Shannon entropy as a
special case). Specifically, we obtain the following quantum speedups for different ranges of α.
Theorem 1.1. There are quantum algorithms that approximate Hα (p) of distribution p on [n]
within an additive error 0 <  ≤ O(1) with success probability at least 2/3 using2
√ 
• Õ 1.5n quantum queries when α = 0, i.e., Hartley entropy. See Theorem 8.2.3
1/α−1/2 
• Õ n 2
quantum queries4 when 0 < α < 1. See Theorem 5.2.
√ 
• Õ 2n quantum queries when α = 1, i.e., Shannon entropy. See Theorem 3.1.
ν(1−1/α) 
quantum queries when α > 1, α ∈ N for some ν < 43 . See Theorem 6.1.
• Õ n 2
1−1/2α 
quantum queries when α > 1, α ∈
/ N. See Theorem 5.1.
• Õ n 2



n
n
• Õ Q( 16 log
-distinctness) quantum queries when α = ∞, where Q( 16 log
-distinctness) is
2
2
 16 log n 
the quantum query complexity of the
-distinctness problem. See Theorem 7.1.
2
Our quantum testers demonstrate advantages over classical ones for all 0 < α < ∞; in particular,
our quantum tester has a quadratic speedup in the case of Shannon entropy. When α = ∞,
our quantum upper bound depends on the quantum query complexity of the dlog ne-distinctness
problem, which is open to the best of our knowledge5 and might demonstrate a quantum advantage.
As a corollary, we also obtain quadratic quantum speedup for estimating KL divergence:
Corollary 1.1 (see Theorem 4.1). Assuming p and q satisfies pqii ≤ f (n) ∀ i ∈ [n] for some
function f : N → R+ , DKL (pkq), there is a quantum algorithm that √
approximates DKL (pkq) within

2
an additive error  > 0 with success probability at least 3 using Õ 2n quantum queries to p and
√
(n) 
quantum queries to q.
Õ nf
2
2

It should be understood that the success probability 2/3 can be boosted to close to 1 without much overhead,
e.g., see Lemma 5.5 in Section 5.1.5.
3
0-Rényi entropy estimation is intractable without any assumption, both classically and quantumly. Here, the
results are based on the assumption that nonzero probabilities are at least 1/n. See Section 8 for more information.
4
Õ hides factors that are polynomial in log n and log 1/.
5
Existing quantum algorithms for the k-distinctness problem (e.g., [5] has query complexity O(k2 nk/k+1 ) and [9]
2
has query complexity O(2k nν ) for some ν < 3/4) do not behave well for super-constant ks.

3

α

classical bounds

α=0

Θ( logn n ) [48, 63]
1
1
−o(1)
nα
α
O( log
) [4]
n ), Ω(n
n
Θ( log n ) [34, 60, 64]
O( logn n ), Ω(n1−o(1) ) [4]

0<α<1
α=1
α > 1, α ∈
/N
α=2
α > 2, α ∈ N
α=∞

√
Θ( n) [4]
Θ(n1−1/α ) [4]
Θ( logn n ) [60]

quantum bounds (this paper)
√
1
Õ( n), Ω(n 3 )
1

1

1

1

Õ(n α − 2 ), Ω(max{n 7α −o(1) , n 3 })
√
1
Õ( n), Ω(n 3 )
1 
1
1
1
Õ(n1− 2α , Ω(max{n 3 , n 2 − 2α })
1

Θ̃(n 3 )
1
1
ν(1−1/α)
Õ(n
), Ω(n 2 − 2α ), ν < 3/4
√
Õ(Q(dlog ne-distinctness)), Ω( n)

Table 1: Summary of classical and quantum query complexity of Hα (p), assuming  = Θ(1).

We also obtain corresponding quantum lower bounds on entropy estimation as follows. We
summarize both bounds in Table 1 and visualize them in Figure 1.
Theorem 1.2 (See Theorem 9.1). Any quantum algorithm that approximates Hα (p) of distribution
p on [n] within additive error  with success probability at least 2/3 must use
1

1

• Ω(n 3 / 6 ) quantum queries when α = 0, assuming 1/n ≤  ≤ 1.
1

2

• Ω̃(n 7α −o(1) / 7 ) quantum queries when 0 < α < 37 .
1

1

1

1

• Ω(n 3 / 6 ) quantum queries when

3
7

≤ α ≤ 3, assuming 1/n ≤  ≤ 1.

• Ω(n 2 − 2α /) quantum queries when 3 ≤ α < ∞.
√
• Ω( n/) quantum queries when α = ∞.
exponent of n

Classical tight bounds

2.0

Quantum upper bounds
Quantum lower bounds

1.5

1.0

0.5

0

1

2

3

4

5

α

Figure 1: Visualization of classical and quantum query complexity of Hα (p). The x-axis represents α and
the y-axis represents the exponent of n. Red curves and points represent quantum upper bounds. Green
curves and points represent classical tight bounds. The Blue curve represents quantum lower bounds.

Techniques. At a high level, our upper bound is inspired by BHH [13], where we formulate a
framework (in Section
P 2) that generalizes the technique in BHH and makes it applicable in our
case. Let F (p) =
x px f (px ) for some function f (·) and distribution p. Similar to BHH, we
design a master algorithm that samples x from p and then use the quantum counting primitive [12]
to obtain an estimate p̃x of px and outputs f (p̃x ). It is easy to see that the expectation of the
4

output of the master algorithm is roughly6 F (p). By choosing appropriate f (·)s, one can recover
H(p) or Hα (p) as well as the ones used in BHH. It suffices then to obtain a good estimate of the
output expectation of the master algorithm, which was achieved by multiple independent runs of
the master algorithm in BHH.
The performance of the above framework (and its analysis) critically depends on how close the
expectation of the algorithm is to F (p) and how concentrated the output distribution is around its
expectation, which in turn heavily depends on the specific f (·) in use. Our first contribution is a finetuned error analysis for specific f (·)s, such as in the case of Shannon entropy (i.e., f (px ) = − log(px ))
whose values could be significant for boundary cases of px . Instead of only considering the case
when p̃x is a good estimate of px as in BHH, we need to analyze the entire distribution of p̃x using
quantum counting. We also leverage a generic quantum speedup for estimating the expectation of
the output of any quantum procedure with additive errors [41], which significantly improves our
error dependence as compared to BHH. These improvements already give a quadratic quantum
speedup for Shannon (Section 3) and 0-Rényi (Section 8) entropy estimation. As an application,
it also gives a quadratic speedup for estimating the KL-divergence between two distributions (see
Section 4).
For general α-Rényi entropy Hα (p), we choose f (px ) = pα−1
and let Pα (p) = F (p) so that
x
Hα (p) ∝ log Pα (p). Instead of estimating F (p) with additive errors in the case of Shannon entropy,
we switch to working with multiplicative errors which is harder since the aforementioned quantum
algorithm [41] is much weaker in this setting. Indeed, by following the same technique, we can only
obtain quantum speedups for α-Rényi entropy when 1/2 < α < 2.
For general α > 0, our first observation is that if one knew the output expectation E[X] is
within [a, b] such that b/a = Θ(1), then one can slightly modify the technique in [41] (as shown in
Theorem 2.2) and obtain a quadratic quantum speedup similar to the additive error setting. This
approach, however, seems circular since it is unclear how to obtain such a, b in advance. Our second
observation is that for any close enough α1 , α2 , Pα1 (p) can be used to bound Pα2 (p). Precisely,
when α1 /α2 = 1 ± 1/ log(n), we have Pα1 (p) = Θ(Pα2 (p)α1 /α2 ) (see Lemma 5.3). As a result,
when estimating Pα (p), we can first estimate Pα0 to provide a bound on Pα , where α0 , α differ by
a 1 ± 1/ log(n) factor and α0 moves toward 1. We apply this strategy recursively on estimating
Pα0 until α0 is very close to 1 from above when initial α > 1 or from below when initial α < 1,
where a quantum speedup is already known. At a high level, we recursively estimate a sequence (of
size O(log n)) of such αs that eventually converges to 1, where in each iteration we establish some
quantum speedup which leads to an overall quantum speedup. We remark that our approach is in
spirit similar to the cooling schedules in simulated annealing (e.g. [57]). (See Section 5.)
For integer α ≥ 2, we observe a connection between Pα (p) and the α-distinctness problem which
leads to a more significant quantum speedup. Precisely, let Op : [S] → [n] be the oracle in (1.7), we
observe that Pα (p) is proportional to the α-frequency moment of Op (1), . . . , Op (S) which can be
solved quantumly [42] based on any quantum algorithm for the α-distinctness problem (e.g., [9]).
However, there is a catch that a direct application of [42] will lead to a dependence on S rather
than n. We remedy this situation by tweaking the algorithm and its analysis in [42] to remove the
dependence on S for our specific setting. (See Section 6.)
The integer α algorithm fails to extend to the min-entropy case (i.e., α = +∞) because the
hidden constant in O(·) has a poor dependence on α (see Remark 6.1). Instead, we develop another
reduction to the dlog ne-distinctness problem by exploiting the so-called “Poissonized sampling”
technique [34, 39, 60]. At a high level, we construct Poisson distributions that are parameterized
by pi s and leverage the “threshold” behavior of Poisson distributions (see Lemma 7.1). Roughly, if
6

The accurate expectation is

P

x

px E[f (p̃x )]. Intuitively, we expect p̃x to be a good estimate of px .

5

maxi pi passes some threshold, with high probability, these parameterized Poisson distributions will
lead to a collision of size dlog ne that will be caught by the dlog ne-distinctness algorithm. Otherwise,
we run again with a lower threshold until the threshold becomes trivial. (See Section 7.)
Some of our lower bounds come from reductions to existing ones in quantum query complexity,
such as the quantum-classical separation of symmetric boolean functions [1], the collision problem
[2, 38], and the Hamming weight problem [44], for different ranges of α. We also obtain lower bounds
with a better error dependence by the polynomial method, which is inspired by the celebrated
quantum lower bound for the collision problem [2, 38]. (See Section 9.)
Open questions. Our paper raises a few open questions. A natural question is to close the gaps
between our quantum upper and lower bounds. Our quantum techniques on both ends are actually
quite different from the state-of-the-art classical ones (e.g., [60]). It is interesting to see whether one
can incorporate classical ideas to improve our quantum results. It is also possible to achieve better
lower bounds by improving our application of the polynomial method or exploiting the quantum
adversary method (e.g., [10, 30]). Finally, our result motivates the study of the quantum algorithm
for the k-distinctness problem with super-constant k, which might also be interesting by itself.
Notations.
Throughout the paper, we consider a discrete distribution {pi }ni=1 on [n], and Pα (p) :=
Pn
α
i=1 pi represents the α-power sum of p. In the analyses of our algorithms, ‘log’ is natural
logarithm; ‘≈’ omits lower order terms.

2

Master algorithm

Let p = (pi )ni=1 be a discrete distribution on [n] encoded by the quantum oracle Ôp defined in (1.7).
Inspired by BHH,
P we develop the following master algorithm to estimate a property F with the
form F (p) := i∈[n] pi f (pi ) for a function f : (0, 1] → R.
Algorithm 1: Estimate F (p) =

P

i pi f (pi )

of a discrete distribution p = (pi )ni=1 on [n].

5

Set l, M ∈ N;
Regard the following subroutine as A:
Draw a sample i ∈ [n] according to p;
Use EstAmp or EstAmp0 with M queries to obtain an estimation p̃i of pi ;
Output X = f (p̃i );

6

Use A for l executions in Theorem 2.1 or Theorem 2.2 and output F̃ (p) to estimate F (p);

1
2
3
4

Comparing to BHH, we introduce a few new technical ingredients in the design of Algorithm 1
and its analysis, which significantly improve the performance of Algorithm 1 especially for specific
f (·)s in our case, e.g., f (px ) = − log(px ) (Shannon entropy) and f (px ) = pα−1
(Rényi entropy).
x
The first one is a generic quantum speedup of Monte Carlo methods [41], in particular, a
quantum algorithm that approximates the output expectation of a subroutine with additive errors
that has a quadratic better sample complexity than the one implied by Chebyshev’s inequality.
Theorem 2.1 (Additive error; Theorem 5 of [41]). Let A be a quantum algorithm with output X
such that Var[X] ≤ σ 2 . Then for  where 0 <  < 4σ, by using O((σ/) log3/2 (σ/) log log(σ/))
executions of A and A−1 , Algorithm 3 in [41] outputs an estimate Ẽ[X] of E[X] such that


Pr Ẽ[X] − E[X] ≥  ≤ 1/5.
(2.1)

6

It is worthwhile mentioning that classically one needs to use Ω(σ 2 /2 ) executions of A [19] to
estimate E[X]. Theorem 2.1 demonstrates a quadratic improvement on the error dependence. In
the case of approximating Hα (p), we need to work with multiplicative errors while existing results
(e.g. [41]) have a worse error dependence which is insufficient for our purposes. Instead, inspired
by [41], we prove the following theorem (our second ingredient) that takes auxiliary information
about the range of E[X] into consideration, which might be of independent interest.
Theorem 2.2 (Multiplicative error; Appendix A). Let A be a quantum algorithm with output X
such that Var[X] ≤ σ 2 E[X]2 for a known σ. Assume that E[X] ∈ [a, b]. Then for  where 0 <
 < 24σ, by using A and A−1 for O((σb/a) log3/2 (σb/a) log log(σb/a)) executions, Algorithm 10
(given in Appendix A) outputs an estimate Ẽ[X] of E[X] such that


Pr Ẽ[X] − E[X] ≥ E[X] ≤ 1/10.
(2.2)
The third ingredient is a fine-tuned error analysis due to the specific f (·)s. Similar to BHH,
we rely on quantum counting (named EstAmp) [12] to estimate the pre-image size of a Boolean
function, which provides another source of quantum speedup. In particular, we approximate any
probability px in the query model ((1.7)) by p̃x by estimating the size of the pre-image of a Boolean
function χ : [S] → {0, 1} with χ(s) = 1 if O(s) = i and χ(s) = 0 otherwise. However, for cases in
BHH, it suffices to only consider the probability when px and p̃x are close, while in our case, we need
to analyze the whole output distribution of quantum counting. Specifically, letting t = χ−1 (1)
and a = t/S = sin2 (ωπ) for some ω, we have
Theorem 2.3 ([12]). For any k, M ∈ N, there is a quantum algorithm (named EstAmp) with M
lπ
quantum queries to χ that outputs ã = sin2 M
for some l ∈ {0, . . . , M − 1} such that
 lπ i
h
1
sin2 (M ∆π)
≤
Pr ã = sin2
= 2 2
,
(2.3)
M
(2M ∆)2
M sin (∆π)
√
a(1−a)
π2
8
where ∆ = |ω − Ml |. This promises |ã − a| ≤ 2πk M
+ k2 M
2 with probability at least π 2 for
1
k = 1 and with probability greater than 1 − 2(k−1)
for k ≥ 2. If a = 0 then ã = 0 with certainty.
Moreover, we also need to slightly modify EstAmp to avoid outputting p̃x = 0 in estimating
Shannon entropy. This is because f (p̃x ) = log(p̃x ) is not well-defined at p̃x = 0. Let EstAmp0 be
π
the modified algorithm. It is required that EstAmp0 outputs sin2 ( 2M
) when EstAmp outputs 0
and outputs EstAmp’s output otherwise.
By leveraging Theorem 2.1, Theorem 2.2, Theorem 2.3, and carefully setting parameters in
Algorithm 1, we have the following corollaries that describe the complexity of estimating any F (p).



Corollary 2.1 (additive error). Given  > 0. If l = Θ σ log3/2 σ log log σ where Var[X] ≤
σ 2 and M is large enough such that E[X] − F (p) ≤ , then Algorithm 1 approximates F (p) with
an additive error  and success probability 2/3 using O M · l) quantum queries to p.
Corollary 2.2 (multiplicative error). Assume a procedure using Ca,b quantum queries that returns an estimated range [a,
 b], and that E[X] ∈2 [a, b] 2 with probability at least 0.9. Let l =
3/2 σb
σb
Θ ( σb
)
log
(
)
log
log(
)
where Var[X]/(E[X]) ≤ σ and  > 0. For large enough M such
a
a
a
that E[X] − F (p) ≤ , Algorithm 1 estimates F (p) with a multiplicative error  and success probability 2/3 with O M · l + Ca,b ) queries.

7

Algorithm 2: Estimate the Shannon entropy of p = (pi )ni=1 on [n].
2) 
2 ) 
log(n/2 )
1 Set l = Θ
log3/2 log(n/
log log log(n/
;



2 Regard the following subroutine as A:
3
Draw a sample i ∈ [n] according to p;
√
4
Use EstAmp0 with M = 2dlog2 ( n/)e queries to obtain an estimation p̃i of pi ;
5
Output x̃i = log(1/p̃i );
6

3

Use A for l executions in Theorem 2.1 and output an estimation H̃(p) of H(p);

Shannon entropy estimation

We develop Algorithm 2 for Shannon entropy estimation with EstAmp0 in Line 4, which provides
quadratic quantum speedup in n.
Theorem 3.1. Algorithm 2 approximates
H(p) within an additive error 0 <  ≤ O(1) with success
√ 
n
2
probability at least 3 using Õ 2 quantum queries to p.
Proof. We prove this theorem in two steps.
The first step is to show that the
P expectation of the
P
subroutine A’s output (denoted Ẽ := i∈[n] pi · log(1/p̃i )) is close to E := i∈[n] pi · log(1/pi ) =
H(p). To that end, we divide [n] into partitions based on the corresponding probabilities. Let
√
m = dlog2 ( n/)e and S0 = {i : pi ≤ sin2 (π/2m+1 )}, S1 = {i : sin2 (π/2m+1 ) < pi ≤ sin2 (π/2m )},
S2 = {i : sin2 (π/2m ) < pi ≤ sin2 (π/2m−1 )}, . . . , Sm = {i : sin2 (π/4) < pi ≤ sin2 (π/2)}. For
convenience, denote s0 = |S0 |, s1 = |S1 |, . . . , sm = |Sm |. Then
m
X

m
X
22j
sj = Θ(1).
22m

sj = n,

j=0

(3.1)

j=0

Our main technical contribution is the following upper bound on the expected difference between
log p̃i and log pi in terms of the partition Si , i = 1, · · · , n:
 2j s 
X


j
pi E log p̃i − log pi = O 2m
∀ j ∈ {1, . . . , m}.
(3.2)
2
i∈Sj

By linearity of expectation, we have
|Ẽ − E| ≤

X
i∈[n]

m X
m
 2j s 
 X

 X

j
O 2m .
pi E log p̃i − log pi =
pi E log p̃i − log pi =
2
j=0

j=0 i∈Sj

As a result, by applying (3.1) and Cauchy-Schwartz inequality to (3.3), we have
v
!
u X
m
m
 2j s 
 X

2j
X
u m 1
2
j
|Ẽ − E| =
O 2m ≤ O t
sj
sj
= O().
2
22m
22m
j=0

j=0

(3.3)

(3.4)

j=0

Because a constant overhead does not influence the query complexity, we may rescale Algorithm 2
by a large enough constant so that |Ẽ − E| ≤ /2.
The second step is to bound the variance of the random variable, which is
X
2 X
X
pi (log p̃i )2 −
pi log p̃i ≤
pi (log p̃i )2 .
(3.5)
i∈[n]

i∈[n]

i∈[n]

8

P
π
2
) ≥ M12 ≥ 4n
, we have i∈[n] pi (log p̃i )2 ≤
Since for any i, EstAmp0 outputs p̃i such that p̃i ≥ sin2 ( 2M

2
P
4n 2
= log 4n
. As a result, by Corollary 2.1 we can approximate Ẽ up to additive
2
i∈[n] pi · log 2

error /2 with failure probability at most 1/3 using
 log(n/2 )

 log(n/2 ) 
 √n 
2 
√
3/2 log(n/ )
dlog2 ( n/)e
O
log
log log
·2
= Õ 2
(3.6)




quantum queries. Together with |Ẽ −E| ≤ /2, Algorithm 2 approximates E = H(p) up to additive
error  with failure probability at most 1/3.
It remains to prove (3.2). We prove:
X
i∈S0

 s 


0
pi E log p̃i − log pi = O 2m .
2

(3.7)

For j ∈ {1, 2, . . . , m} in (3.2), the proof is similar because the dominating term has the angles of
p̃i and pi fall into the same interval of length 21m , and as a result | log p̃i − log pi = O( 21j ).
Proof of (3.7). For convenience, denote h(x) := x(log t−log x) ≤ t/e where 0 < t ≤ 1 and x ∈ (0, t].
Because h0 (x) = log t − log x − 1, when x ∈ (0, t/e), h0 (x) > 0 hence h(x) is an increasing function;
when x ∈ (t/e, t), h0 (x) < 0 hence h(x) is a decreasing function; when x = t/e, h0 (x) = 0 and h
reaches its maximum t/e.
Since i ∈ S0 , we can write pi = sin2 (θi π) where 0 < θi ≤ 1/2m+1 . By Theorem 2.3, for any
l ∈ {1, . . . , 2m−1 }, the output of EstAmp0 when taking 2m queries satisfies
 π i
h
Pr p̃i = sin2 m+1
=
2
 lπ i
h
Pr p̃i = sin2 m
=
2

sin2 (2m θi π)
≤ 1;
22m sin2 (θi π)
l
sin2 (2m ( 2m
− θi )π)
l
22m sin2 (( 2m

− θi )π)

(3.8)
≤

1
l
(2m+1 ( 2m

− θi ))2

.

(3.9)

Combining (3.8), (3.9), and the property of function h discussed above, for any i ∈ S0 we have


pi E log p̃i − log pi

m−1

 π 
 2X
pi log sin2 ( 2lπm ) − log pi
2
≤ 1 · pi log sin
− log pi +
(3.10)
l
2m+1
(2m+1 ( 2m
− θi ))2
l=1

≤

π
sin2 ( 2m+1
)
+
e

m−1
2X

l=1

 π 
 
 π 
1
2
2 lπ
2
·
sin
log
sin
−
log
sin
(2l − 1)2
2m+1
2m
2m+1

2m−1
 sin( lπ ) 2
1
π2 1
1
π2 X
2m 
+
·
log
≤
π
2m
2m
2
4e 2
2
4
(2l − 1)
sin 2m+1
l=1

(3.11)

(3.12)

m−1

2
π2 1
1
π 2 X log 2l
≤
+
·
4e 22m 22m 2
(2l − 1)2
l=1
 1 
= O 2m ,
2

(3.13)
(3.14)

where (3.10) comes from (3.8) and (3.9), (3.11) comes from the property of h, (3.12) holds because

π
π2
π
sin2 ( 2m+1
) ≤ 22m+2
, (3.13) holds because sin2 ( 2lπm ) ≤ 4l2 sin2 2m+1
, and (3.14) holds because
9

P∞

log l
l=1 (2l−1)2

= O(1). Consequently,
X
i∈S0

4

 1 
 s 


0
pi E log p̃i − log pi = O 2m · s0 = O 2m .
2
2

(3.15)

Application: KL divergence estimation

Classically, there does not exist any consistent estimator that guarantees asymptotically small
error over the set of all pairs of distributions [14, 27]. These two papers then consider pairs of
distributions with bounded probability ratios specified by a function f : N → R+ , namely all pairs
of distributions in the set as follows:

pi
Un,f (n) := (p, q) : |p| = |q| = n, ≤ f (n) ∀ i ∈ [n] .
(4.1)
qi
Denote the number of samples from p and q to be Mp and Mq , respectively. References [14, 27]
shows that classically, DKL (pkq) can be approximated within constant additive error with high
(n)
success probability if and only if Mp = Ω( logn n ) and Mq = Ω( nf
log n ).
Quantumly, we are given unitary oracles Ôp and Ôq defined by (1.7). Algorithm 3 below
estimates the KL-divergence between p and q, which is similar to Algorithm 2 that uses EstAmp0 ,
while adapts f to be mutually defined by p and q.
Algorithm 3: Estimate the KL divergence of p = (pi )ni=1 and q = (qi )ni=1 on [n].
2
2
2 
2 
log2 (nf (n)/2 )
log3/2 log (nf(n)/ ) log log log (nf(n)/ ) ;
1 Set l = Θ

2 Regard the following subroutine as A:
3
Draw a sample i ∈ [n] according to p;
√
4
Use the modified amplitude estimation procedure EstAmp0 with 2dlog2 ( n/)e and
√
2dlog2 ( nf (n)/)e quantum queries to p and q to obtain estimates p̃i and q̃i , respectively;
5
Output x̃i = log p̃i − log q̃i ;
6

Use A for l times in Theorem 2.1 and outputs an estimation D̃KL (pkq) of DKL (pkq);

Theorem 4.1. For (p, q) ∈ Un,f (n) , Algorithm 3 approximates DKL (pkq) within an additive error
√
√ 
(n) 
 > 0 with success probability at least 23 using Õ 2n quantum queries to p and Õ nf
quantum
2

queries to q, where Õ hides polynomials terms of log n, log 1/, and log f (n).
Proof. If the estimates
p̃i and q̃i were precisely accurate, the expectation of the subroutine’s output
P
would be E := i∈[n] pi ·(log pi −log qi ) = DKL (pkq). On the one hand, we bound how far the actual
expectation of the subroutine’s output Ẽ is from its exact value E. By linearity of expectation,
X


|Ẽ − E| ≤
pi E (log p̃i − log pi ) + (log q̃i − log qi )
(4.2)
i∈[n]

≤

X


 X


pi E log p̃i − log pi +
pi E log q̃i − log qi

i∈[n]

≤

X

(4.3)

i∈[n]

X




pi E log p̃i − log pi + f (n)
qi E log q̃i − log qi ,

i∈[n]

i∈[n]

10

(4.4)

where (4.4) comes from the definition of Un,f (n) in (4.1). By the proof of Theorem 3.1, in particular
√
√
equation (3.4), 2dlog2 ( n/)e and 2dlog2 ( nf (n)/)e quantum queries to p and q give
  
X
X




qi E log q̃i − log qi = O
pi E log p̃i − log pi = O() and
,
(4.5)
f (n)
i∈[n]

i∈[n]

respectively. Plugging them into (4.4) and rescaling Algorithm 3 by a large enough constant, we
get |Ẽ − E| ≤ 2 .
On the other hand, the variance of the random variable is at most
X
X
X
pi (log p̃i − log q̃i )2 =
pi (log q̃i − log p̃i )2 +
pi (log p̃i − log q̃i )2 .
(4.6)
i: p̃i ≥q̃i

i: p̃i <q̃i

i∈[n]

For the first term in (4.6), because EstAmp0 outputs p̃i such that p̃i ≥ sin2 ( dlog2 (√πn/)e+1 ) ≥
2
for any i, we have
X

pi (log q̃i − log p̃i )2 ≤

X
i: p̃i <q̃i

i: p̃i <q̃i


2 2 
4n 2
pi log 1 − log
≤ log 2 .
4n


For the second term in (4.6), we have
X
X
pi (log p̃i − log q̃i )2 ≤
pi (log f (n))2 ≤ (log f (n))2 .
i: p̃i ≥q̃i

2
4n

(4.7)

(4.8)

i: p̃i ≥q̃i

Plugging (4.7) and (4.8) into (4.6), the variance of the random variable is at most


log


4n 2
nf (n) 2 
2
+
(log
f
(n))
=
O
log
.
2
2

(4.9)

As a result, by Corollary 2.1 we can approximate
Ẽ up to additive error /2 with success probability
√ 
√
√
n
1
n/)e
dlog
(
2
= Õ 2 quantum queries to p and Õ( 1 ) · 2dlog2 ( nf (n)/)e =
at least 2/3 using Õ(  ) · 2
√
(n) 
Õ nf
quantum queries to q, respectively. Together with |Ẽ − E| ≤ /2, Algorithm 3 approxi2
mates E = DKL (pkq) up to additive error  with success probability at least 2/3.

5

Non-integer Rényi entropy estimation

Recall the classical query complexity of non-integer and integer Rényi entropy estimations are
different [4]. Quantumly, we also consider them separately; in this section, we consider α-Rényi
entropy estimation
Pfor general non-integer α1 > 0.
Let Pα (p) := ni=1 pαi . Since Hα (p) = 1−α
log Pα (p), to approximate Hα (p) within an additive
error  > 0 it suffices to approximate Pα (p) within a multiplicative error e(α−1) − 1 = Θ().

5.1

Case 1: α > 1, α ∈
/N

We develop Algorithm 4 to approximate Pα (p) with a multiplicative error .
Theorem 5.1. The output of Algorithm 4 approximates Pα (p) within a multiplicative error 0 <
1− 1 
 ≤ 1/4 with success probability at least 1 − δ for some δ > 0 using Õ n 22α quantum queries to
p, where Õ hides polynomials terms of log n, log 1/, and log 1/δ.
11

Algorithm 4: Estimate the α-power sum Pα (p) of p = (pi )ni=1 on [n], α > 1, α ∈
/ N.
Regard the following subroutine as A:
Draw a sample i ∈ [n] according to p;

√

Use the amplitude estimation procedure EstAmp with M = 2dlog2 (
to obtain an estimate p̃i of pi ;
Output x̃i = p̃α−1
;
i
1
2
3
4
5

6
7

8

n


√

log(

n
))e+1


queries

Input parameters (α, , δ), where  is the multiplicative error and δ is the failure probability;
if α < 1 + log1 n then
Take a = 1e and b = 1 as lower and upper bounds on Pα (p), respectively;
else
Recursively call Algorithm 4 with α0 = α(1 + log1 n )−1 ,  = 1/4, and δ = 12 log 1n log α
therein to give an estimate P̃α0 (p) of Pα0 (p). For simplicity, denote P := P̃α0 (p). Take
1+ 1
1+ 1
log n
log n
a = (3P/4)e
and b = 5P
as lower and upper bounds on Pα (p), respectively;
4
1− 1
1− 1
1− 1

Set l = Θ n 2  2α log3/2 ( n 2  2α ) log log( n 2  2α ) ;
Use A for l executions in Theorem 2.2 using a and b as auxiliary information and output an
estimation of Pα (p);
Run Line 1 to Line 7 for d48 log 1δ e executions and take the median of all outputs in Line 7,
denoted as P̃α (p). Output P̃α (p);

Proof of Theorem 5.1. First, we design a subroutine A in Algorithm 4 to approximate Pα (p) following the same principle asPin Algorithm 2. If the estimate p̃i in A were precisely accurate, its
expectation would be E := i∈[n] pi · pα−1
= Pα (p). To be precise, we bound how far the actual
i
expectation of the subroutine’s
output
Ẽ is from the exact value Pα (p). In Lemma 5.1, we show
√
√
n

n

that when taking M = 2dlog2 (  log(  ))e+1 queries in EstAmp, we have |Ẽ − E| = O(E).
As a result, to approximate Pα (p) within multiplicative error Θ(), it is equivalent to approximate Ẽ within multiplicative error Θ(). Recall Theorem 2.2 showed that if the variance of the
random variable output by A is at most σ 2 Ẽ 2 for a known σ, and if we can obtain two values a, b
such that Ẽ ∈ [a, b], then Õ(σb/a) executions of A suffice to approximate Ẽ within multiplicative
error  with success probability at least 9/10. In the main body of the algorithm (Line 1 to Line
8), we use Theorem 2.2 to approximate Ẽ.
On the one hand, in Lemma 5.2, we show that for α > 1 and
√ large enough n, the variance is at
most 5n1−1/α Ẽ 2 with probability at least π82 . This gives σ = 5n1−1/α = O(n1/2−1/2α ).
On the other hand, we need to compute the lower bound a and upper bound b. A key observation
(Lemma 5.3) is that for any 0 < α1 < α2 , we have
X

pαi 2

 α1
α2

i∈[n]

Because n1/ log n = e, if

α2
α1

X

≤

pαi 1

α

≤n

1− α1

i∈[n]

2

X

pαi 2

 α1
α2

.

(5.1)

i∈[n]

= 1 + O( log1 n ), then
X
i∈[n]

pαi 1

 X
 α1 
α 2 α2
=Θ
pi
.
i∈[n]

12

(5.2)

As a result, we compute a and b by recursively calling Algorithm 4 to estimate Pα0 (p) for α0 =
α/(1 + 1/ log n), which is used to compute the lower bound a and upper bound b in Line 5; the
recursive call keeps until α < 1 + log1 n , when a = 1e and b = 1 (as in Line 3) are simply lower and
upper bounds on Pα (p) by (5.1).
To be precise, in Lemma 5.4, we prove that b/a < 4e = O(1), and with probability at least
1/e1/12 > 0.92, a and b are indeed lower and upper bounds on Pα (p), respectively; furthermore,
in Line 5, Algorithm 4 is recursively called by at most log n log α times, and each recursive call
1
takes at most Õ(n1− 2α ) queries. This promises that when we apply Corollary 2.2, the cost Ca,b is
dominated by the query cost from Algorithm 10.
Combining all points above, Corollary 2.2 approximates Ẽ up to multiplicative error Θ() with
success probability at least π82 · 0.92 · 9/10 > 2/3 using
log n log α · Õ

 4e · √5n1−1/α 


√

dlog2 (

·2

n


log(

√
n
))e+1


= Õ

 n1−1/2α 
2

(5.3)

quantum queries. Together with |Ẽ − E| = O(E) and rescale l, M by a large enough constant,
Line 1 to Line 7 in Algorithm 4 approximates E = Pα (p) up to multiplicative error  with success
probability at least 2/3.
Finally, in Lemma 5.5, we show that after repeating the procedure for d48 log 1δ e executions
and taking the median P̃α (p) (as in Line 8), the success probability that P̃α (p) approximates Pα (p)
within multiplicative error  is boosted to 1 − δ.
It remains to prove the lemmas mentioned above.
5.1.1

Expectation of A is -close to Pα (p)

Lemma 5.1. |Ẽ − E| = O(E).
√
√
Proof of Lemma 5.1. For convenience, denote m = dlog2 ( n/ log( n/))e + 1, and S0 , S1 , . . . , Sm
the same as in Section 3. We still have (3.1). By linearity of expectation,
|Ẽ − E| ≤

X

m X


 X

α−1
pi E p̃α−1
−
p
pi E p̃α−1
− pα−1
=
.
i
i
i
i

(5.4)

j=0 i∈Sj

i∈[n]

Therefore, to prove |Ẽ − E| = O(E) it suffices to show
m X
X

 X 


α−1
pi E p̃α−1
−
p
=
O

pαi .
i
i

j=0 i∈Sj

(5.5)

i∈[n]

For each i ∈ [n] we write pi = sin2 (θi π). Assume k ∈ Z such that k ≤ 2m θi < k + 1. By
Theorem 2.3, for any l ∈ {1, 2, . . . , max{k − 1, 2m − k − 1}} the output of EstAmp taking 2m
queries satisfies
h
h
i
1
(k + l + 1)π i
2 (k − l − 1)π
,
Pr
p̃
=
sin
≤ 2.
Pr p̃i = sin2
i
m
m
2
2
4l

(5.6)

Furthermore, because sin θi = θi −O(θi3 ), cos θi = 1−O(θi2 ), and (1+θi )2α−1 = 1+(2α−1)θi +o(θi ),
sin((θi +

 l

2(α−1)
2(α−1)
l
2α−3
−
sin(θ
π)
=
O
.
)π)
(θ
π)
i
i
2m
2m
13

(5.7)

Combining (5.6), (5.7), and the fact that
m X
X
j=0 i∈Sj

P2m

1
l=1 l

= Θ(m), we have
m

m
2
X


2j 2 X 1 l 2j 2α−3 
α−1
pi E p̃α−1
−
p
=
O
s
·
π
·
2
π
j
i
i
2m
4l2 2m 2m
j=0

(5.8)

l=1

m
 π 2α−1 m X

(2α−1)j
=O
·
s
2
.
j
22αm

(5.9)

j=0

On the other side,


X
i∈[n]

m
m
 X
  · π 2α X

2j 2α 
pαi = Θ 
= Θ 2αm
sj · m π
sj 22αj .
2
2
j=0

(5.10)

j=0

Therefore, to prove equation (5.5), by (5.9) and (5.10) it suffices to prove
m
X

sj 2(2α−1)j = O

j=0
n


log(

n
 ))e

+ 1, we have
m
X

(5.11)

j=0

√

√

Since m = dlog2 (

m
 X

sj 22αj .
m

sj 2

2m
m

(2α−1)j

√

n
 ,

≥

=O

thus

m
 √n X

2m

j=0

√


m

≥

n
2m .

Therefore, it suffices to show


sj 22αj .

(5.12)

j=0

If α ≥ 3/2, by Hölder’s inequality we have
m
X

sj



1
2α

m
X

j=0

sj 22αj

 2α−1
2α

≥

j=0

m
X

sj 2(2α−1)j .

(5.13)

j=0

By equation (3.1), this gives
n

1
2α−1

m
X

sj 2

2αj



≥

m
X

j=0

sj 2

(2α−1)j

m
 X

j=0

sj 2

(2α−1)j



1
2α−1

.

(5.14)

j=0

By Hölder’s inequality and also equation (3.1), we have
m
X

sj

m
 2α−3  X
2α−1

j=0

sj 2(2α−1)j



2
2α−1

≥

m
X

sj 22j = Θ(22m ).

(5.15)

j=0

j=0

This is equivalent to
2α−3

n 2(2α−1)

m
X

sj 2(2α−1)j



1
2α−1

≥ Θ(2m ).

(5.16)

j=0

Combining (5.14) and (5.16), we get exactly (5.12).
If 1 < α < 3/2, by Hölder’s inequality we have
m
X

sj 22αj

j=0
m
X
j=0

sj 2

2j

m
1X
α

j=0
m
2α−1

X
2

sj

sj

 α−1
α

 3−2α

j=0

2

≥

≥

m
X
j=0
m
X
j=0

14

sj 22j ;

(5.17)

sj 2(2α−1)j .

(5.18)

By equation (3.1), the two inequalities above give
m
X

sj 22αj ≥ n1−α 22αm

m
X

and

j=0

sj 2(2α−1)j ≤ n1.5−α 2(2α−1)m ,

(5.19)

j=0

which give (5.12).
5.1.2

Bound the variance of A by the square of its expectation

Lemma 5.2. With probability at least
most 5n1−1/α Ẽ 2 .

8
,
π2

the variance of the random variable output by A is at

Pn
α−1
Proof of Lemma 5.2. The expectation and variance of the output by A are Ẽ =
i=1 pi · p̃i

P
P
α−1 2
and i∈[n] pi · (p̃iα−1 )2 −
, respectively. Therefore, it suffices to show that with
i∈[n] pi · p̃i
8
probability at least π2 ,
X

pi · (p̃α−1
)2 ≤ 5n1−1/α
i

n
X

pi · p̃α−1
i

2

.

(5.20)

i=1

i∈[n]
8
,
π2

By Theorem 2.3, with probability at least

we have

√
√
2π pi
π pi
|p̃i − pi | ≤
≤ √
2m
n

i ∈ [n].

(5.21)

For convenience, denote p := pi∗ to be the maximal one among p1 , . . . , pn , i.e., p = maxi∈{1,...,n} pi .
We also denote p̃ := p̃i∗ . Then we have
Pn

i=1 pi

P

i∈[n] pi

· p̃iα−1

2

· (p̃α−1
)2
i

Pn
≥

i=1 pi

p̃α−1 ·

P

· p̃α−1
i

i∈[n] pi

2

· p̃α−1
i

Pn
=

α−1
i=1 pi · p̃i
.
p̃α−1

(5.22)

Furthermore, because xα is a convex function in [0, 1], by (5.21) and Jensen’s inequality we have
P
Pn
α−1
p · p̃α−1 + i6=i∗ pi · p̃α−1
i
i=1 pi · p̃i
=
(5.23)
p̃α−1
p̃α−1
√



√ 
π (1−p)/(n−1) α−1
π p α−1
1−p 1−p
√
p p + √n
+ (n − 1) · n−1
−
n−1
n
≥
(5.24)

√ α−1
π p
p + √n
 1 − p − π √1 − p α−1
≈ p + (1 − p)
.
(5.25)
√
np + π np
Therefore, it suffices to show that for large enough n,
 1 − p − π √1 − p α−1
p + (1 − p)
≥ 0.2n−(1−1/α) .
√
np + π np

15

(5.26)

If p ≥ 0.2n−(1−1/α) , equation (5.26) directly follows. If p < 0.2n−(1−1/α) ,
 1 − p − π √1 − p α−1
1−1/α
lim n
· (1 − p)
√
n→∞
np + π np
 1 − 0.2n−(1−1/α) − π α−1
√
≥ lim n1−1/α (1 − 0.2n−(1−1/α) )
n→∞
0.2n1/α + 0.2πn1/2α
 n1/α (1 − 0.2n−(1−1/α) − π) α−1
√
= lim (1 − 0.2n−(1−1/α) )
n→∞
0.2n1/α + 0.2πn1/2α
 1 − π α−1
=1·
> 1 > 0.2,
0.2

(5.27)
(5.28)
(5.29)

1−3.2/4
where (5.29) is true because 1−π
= 1. Because (5.25) only omits lower order terms and
0.2 >
0.2
the limit in (5.29) is a constant larger than 0.2, Lemma 5.2 follows.

5.1.3

Give tight bounds on Pα (p) by Pα0 (p)

Lemma 5.3. For any distribution (pi )ni=1 and 0 < α1 < α2 , we have
X

pαi 2

 α1
α2

≤

i∈[n]

X

pαi 1 ≤ n

α

1− α1

2

X

i∈[n]

 α1
α2

pαi 2

.

(5.30)

i∈[n]

Proof of Lemma 5.3. On the one hand, by the generalized mean inequality, we have
α2
i∈[n] pi

P

!

1
α2

P
≥

n

α1
i∈[n] pi

!

1
α1

n

,

(5.31)

which gives the second inequality in (5.30).
On the other hand, since αα21 ≤ 1 and
0≤ P

pαi 2

α2
j∈[n] pj

≤1

∀ i ∈ [n],

(5.32)

we have
α1
X
i∈[n] pi
P
 α1 =
α 2 α2
i∈[n]
j∈[n] pj

P

pαi 2

α2
j∈[n] pj

P

! α1

α2

≥

pαi 2

X

α2
j∈[n] pj

P
i∈[n]

= 1,

(5.33)

which is equivalent to the first inequality in (5.30).
5.1.4

Analyze the recursive calls

Lemma 5.4. With probability at least 0.92, the a and b in Line 3 or Line 5 of Algorithm 4 are
indeed lower and upper bounds on Pα (p), respectively, and b/a = O(1); furthermore, in Line 5,
Algorithm 4 is recursively called for at most log n log α executions, and each recursive call takes at
1
most Õ(n1− 2α ) queries.
Proof of Lemma 5.4. We decompose the proof into two parts:

16

• In Line 5, Algorithm 4 is recursively called for at most log n log α executions, and
1
each recursive call takes at most Õ(n1− 2α ) queries:
1
−1 and the
log n )
log α
most log(1+
≤
1
)
log n

Because each recursive call of Algorithm 4 reduces α by multiplying (1 +
recursion ends when α < 1 + log1 n , the total number of recursive calls is at
log n log α.

When α < 1 + log1 n , a and b are set in Line 3 and no extra queries are needed; when Line
5 calls α(1 + log1 n )−k -power sum estimation for some k ∈ N, by induction on k, we see that
(1+1/ log n)k 
1
2α
≤ Õ(n1− 2α ) queries. As a result, when we apply
this call takes at most Õ n1−
Corollary 2.2, the cost Ca,b is dominated by the query cost from Algorithm 10.
• With probability at least 0.92, a and b are lower and upper bounds on Pα (p)
respectively, and b/a = O(1):
P
P
When 1 < α < 1 + log1 n , on the one hand we have ni=1 pαi ≤ ni=1 pi = 1; on the other hand,
1

because n log n = e, by Lemma 5.3 we have
n
X

pαi

Pn

i=1 pi
nα−1

≥

i=1

α

1
≥ .
e

(5.34)

Therefore, a = 1/e and b = 1 in Line 3 are lower and upper bounds on Pα (p) respectively,
and b/a = e = O(1).
When α > 1 + log1 n , for convenience denote α0 = α(1 + log1 n )−1 . As justified above, the total
number of recursive calls in Line 5 is at most log n log α. Because we take δ = 12 log 1n log α in
Line 5, with probability at least

log n log α
1
1
1−
(5.35)
≥ 1/12 > 0.92,
12 log n log α
e
the output of every recursive call is within 1/4-multiplicative error. As a result, the P in Line
1
P
0
5 satisfies 3P/4 ≤ ni=1 pαi ≤ 5P/4. Combining this with Lemma 5.3 and using n log n = e,
we have
1+ log1 n

(3P/4)
e

≤

n
X
i=1

pαi ≤

 5P 1+

1
log n

4

.

(5.36)

In other words, a and b are indeed lower and upper bounds on Pα (p), respectively. Furthermore, b/a = O(1) because
 5 1+ 1
b
log n
< 4e = O(1).
=e·
a
3

5.1.5

(5.37)

Boost the success probability

Lemma 5.5. By repeating Line 1 to Line 7 in Algorithm 4 for d48 log 1δ e executions and taking the
median P̃α (p), the success probability is boosted to 1 − δ.
17

Proof of Lemma 5.5. Denote the outputs after running Line 1 to Line 7 for d48 log 1δ e executions
1
as P̃α (p)(1) , . . . , P̃α (p)(d48 log δ e) , respectively. Based on the correctness of Lemma 5.1, Lemma 5.2,
and Lemma 5.4, for each i ∈ {1, . . . , d48 log 1δ e}, with probability at least 2/3 we have
|P̃α (p)(i) − Pα (p)| ≤ Pα (p).

(5.38)

For each i ∈ {1, . . . , d48 log 1δ e}, denote Xi to be a Boolean random variable such that Xi = 1
if (5.38) holds, and Xi = 0 otherwise. Then Pr[Xi = 1] ≥ 2/3. Because in Line 8 the output P̃α (p)
Pd48 log 1 e
1
is the median of all P̃α (p)(1) , . . . , P̃α (p)(d48 log δ e) , |P̃α (p) − Pα (p)| > Pα (p) leads to i=1 δ Xi <
d48 log 1δ e/2. On the other hand, by Chernoff bound we have
1

Pr

log δ e
h d48X
i=1

Xi <

 2/3d48 log 1 e · (1/4)2 
d48 log 1δ e i
δ
≤ exp −
≤ δ.
2
2

(5.39)

Therefore, with probability at least 1 − δ, we have |P̃α (p) − Pα (p)| ≤ Pα (p).

5.2

Case 2: 0 < α < 1

When 0 < α < 1, our quantum algorithm follows the same structure as Algorithm 4:
Algorithm 5: Estimate the α-power sum Pα (p) of p = (pi )ni=1 on [n], 0 < α < 1.
Regard the following subroutine as A:
Draw a sample i ∈ [n] according to p;
Use the amplitude estimation procedure EstAmp with M = 2dlog2 (
queries to obtain an estimate p̃i of pi ;
Output x̃i = p̃α−1
;
i
1
2
3
4
5

6
7

8

n1/2α


log( n

1/2α
))e+1


Input parameters (α, , δ), where  is the multiplicative error and δ is the failure probability;
if α > 1 − log1 n then
Take a = 1 and b = e as lower and upper bounds on Pα (p), respectively;
else
Recursively call Algorithm 5 with α0 = α(1 − log1 n )−1 ,  = 1/2, and δ = 12 log n1log 1/α
therein to give an estimate P̃α0 (p) of Pα0 (p). For simplicity, denote P := P̃α0 (p). Take
1− 1
1− 1
a = (P/2) log n and b = e(2P ) log n as lower and upper bounds on Pα (p), respectively;
1 −1
1 −1 
1 −1
Set l = Θ n 2α 2 log3/2 ( n 2α 2 ) log log( n 2α 2 ) ;
Use A for l executions in Theorem 2.2 using a and b as auxiliary information and output an
estimation of Pα (p);
Run Line 1 to Line 7 for d48 log 1δ e executions and take the median of all outputs in Line 7,
denoted as P̃α (p). Output P̃α (p);

The main difference is that, in the case α > 1, Algorithm 4 makes α0 smaller and smaller by
multiplying (1 + log1 n )−1 each time, whereas in the case 0 < α < 1, Algorithm 5 makes α0 larger
and larger by multiplying (1 − log1 n )−1 each time; nevertheless, both recursions end when α0 is close
enough to 1. On the more technical level, they have different M in A, different upper bounds on
the variance of A, and different expressions for a and b in Line 3 and Line 5.
18

Theorem 5.2. The output of Algorithm 5 approximates Pα (p) within a multiplicative error 0 <
1 −1 
 ≤ O(1) with success probability at least 1 − δ for some δ > 0 using Õ n α2 2 quantum queries to
p, where Õ hides polynomials terms of log n, log 1/, and log 1/δ.
Before we give the formal proof of Theorem 5.2, we compare the similarities and differences between
Algorithm 4 and Algorithm 5, listed below:
• In both algorithms, the subroutine A has the same structure, and is designed to estimate
Pα (p). However, to make the
expectation
of A -close to Pα (p), the EstAmp in Algorithm 4
√
√
suffices to take M = 2dlog2 (

n


n
))e+1


log(

dlog2 ( n

Algorithm 5 needs to take M = 2

queries (see Lemma 5.1), whereas the EstAmp in

1/2α


log( n

1/2α
))e+1


queries (see Lemma 5.6);

• In both algorithms, we use Theorem 2.2 to approximate the expectation of A (denoted Ẽ),
hence they both need to upper-bound the variance of A by a multiple of Ẽ 2 . However,
technically the proofs are different, and we obtain different upper bounds in Lemma 5.2 and
Lemma 5.7, respectively;
• Since both algorithms use Theorem 2.2, they both need to compute a lower bound a and
upper bound b on Pα (p). Both algorithms achieve this by observing Lemma 5.3, and they
both compute a and b by recursively call the estimation of Pα0 (p) for some α0 closer to
1. However, in the case α > 1, Algorithm 4 makes α0 smaller and smaller by multiplying
(1 + log1 n )−1 each time, and ends the recursion when α0 < 1 + log1 n ; in the case 0 < α < 1,
Algorithm 5 makes α0 larger and larger by multiplying (1 − log1 n )−1 each time, and ends the
recursion when α0 > 1− log1 n . This leads to different expressions for a and b in Line 3 and Line
5 of both algorithms, and technically the proofs for Lemma 5.4 and Lemma 5.8 is different;
• Both algorithms boost the success probability to 1−δ by repeating the algorithm for d48 log 1δ e
executions and taking the median, and their correctness is both promised by Lemma 5.5.
Proof of Theorem 5.2. First, if the estimate p̃i in the subroutine AP
of Algorithm 5 were precisely
α−1
:=
= Pα (p). To be
accurate, the expectation of the subroutine’s output would be E
i∈[n] pi · pi
precise, we bound how far the actual expectation of the subroutine’s output Ẽ is from the exact
n1/2α

n1/2α

value Pα (p). In Lemma 5.6, we show that when taking M = 2dlog2 (  log(  ))e+1 queries in
EstAmp, we have |Ẽ − E| = O(E).
As a result, to approximate Pα (p) within multiplicative error Θ(), it is equivalent to approximate Ẽ within multiplicative error Θ(). Recall Theorem 2.2 showed that if the variance of the
random variable output by A is at most σ 2 Ẽ 2 for a known σ, and if we can obtain two values a, b
such that Ẽ ∈ [a, b], then Õ(σb/a) executions of A suffice to approximate Ẽ within multiplicative
error  with success probability at least 9/10. In the main body of the algorithm (Line 1 to Line
8), we use Theorem 2.2 to approximate Ẽ.
On the one hand, in Lemma 5.7, we show that for√any 0 < α < 1, the variance is at most
1/α−1
2n
Ẽ 2 with probability at least π82 . This gives σ = 2n1/α−1 = O(n1/2α−1/2 ).
On the other hand, we need to compute the lower bound a and upper bound b. As stated in
the proof of Theorem 5.1, for any 0 < α1 < α2 with αα21 = 1 + O( log1 n ),
X
i∈[n]

pαi 1

 X
 α1 
α 2 α2
=Θ
pi
.
i∈[n]

19

(5.40)

As a result, we compute a and b by recursively calling Algorithm 5 to estimate Pα0 (p) for α0 =
α/(1 − 1/ log n), which is used to compute the lower bound a and upper bound b in Line 5; the
recursive call keeps until α > 1 − log1 n , when a = 1 and b = e (as in Line 3) are simply lower and
upper bounds on Pα (p).
To be precise, in Lemma 5.8, we prove that b/a ≤ 4e = O(1), and with probability at least
1/e1/12 > 0.92, a and b are indeed lower and upper bounds on Pα (p), respectively; furthermore,
in Line 5, Algorithm 5 is recursively called by at most log n log α1 times, and each recursive call
1
1
takes at most Õ(n α − 2 ) queries. This promises that when we apply Corollary 2.2, the cost Ca,b is
dominated by the query cost from Algorithm 10.
Combining all points above, Corollary 2.2 approximates Ẽ up to multiplicative error Θ() with
success probability at least π82 · 0.92 · 9/10 > 2/3 using
 4e ·
1
log n log · Õ
α

√

1

1

nα−2 
2n1/α−1  dlog2 ( n1/2α log( n1/2α ))e+1


= Õ
·2

2

(5.41)

quantum queries. Together with |Ẽ − E| = O(E) and rescale l, M by a large enough constant,
Line 1 to Line 7 in Algorithm 5 approximates E = Pα (p) up to multiplicative error  with success
probability at least 2/3.
Finally, following from Lemma 5.5, after repeating the procedure for d48 log 1δ e executions and
taking the median P̃α (p) (as in Line 8), the success probability that P̃α (p) approximates Pα (p)
within multiplicative error  is boosted to 1 − δ.
It remains to prove the lemmas mentioned above.
5.2.1

Expectation of A is -close to Pα (p)

Lemma 5.6. |Ẽ − E| = O(E).
1/2α

1/2α

Proof of Lemma 5.6. For convenience, denote m = dlog2 ( n  log( n  ))e + 1, and S0 , S1 , . . . , Sm
the same as previous definitions. We still have (3.1). By linearity of expectation,
X

|Ẽ − E| ≤

h
pi E

i∈[n]

1
p̃1−α
i

−

1

i

p1−α
i

=

m X
X



pi E p̃α−1
− pα−1
.
i
i

(5.42)

j=0 i∈Sj

Therefore, to prove |Ẽ − E| = O(E) it suffices to show
m X
X

 X 


α−1
pi E p̃α−1
−
p
=
O

pαi .
i
i

j=0 i∈Sj

(5.43)

i∈[n]

Similar to the proof of Lemma 5.1, we have
m X
X

m
 π 2α−1 m X



(2α−1)j
pi E p̃iα−1 − pα−1
=
O
·
s
2
.
j
i
22αm

(5.44)

m
m
  · π 2α X

 X
2j 2α 
pαi = Θ 
sj · m π
= Θ 2αm
sj 22αj .
2
2

(5.45)

j=0 i∈Sj

j=0

On the other side,


X
i∈[n]

j=0

j=0

20

Therefore, to prove Equation (5.43), by (5.44) and (5.45) it suffices to prove
m
X

sj 2(2α−1)j = O

1/2α



1/2α

log( n



2m
m

))e + 1, we have

m
X

sj 2

(2α−1)j

=O

1/α

Pm

2j
j=0 sj 2

Pm

j=0 sj 2


2αj 1/α

n1/2α
 ,

2m

thus


m

≥

n1/2α
2m .


sj 22αj .

Therefore, it suffices

(5.47)

j=0

; as a result,

Pm
≤

≥

m
 n1/2α X

j=0

Since sj ∈ N, sj ≤ sj

(5.46)

j=0

j=0

Since m = dlog2 ( n
to prove

m

 X
sj 22αj .
m

2αj )1/α
j=0 (sj 2

Pm
2αj 1/α
j=0 sj 2

=

m 
X

m

1/α X
sj 22αj
s 22αj
Pm j
P
= 1. (5.48)
≤
m
2αk
2αk
k=0 sk 2
k=0 sk 2
j=0

j=0

Plugging (3.1) into the inequality above, we have
m
X

sj 22αj



1
2α

= Ω(2m ).

(5.49)

j=0

On the other side, by Hölder’s inequality we have
m
X

sj



j=0

1
2α

m
X

sj 2

2αj

 2α−1
2α

≥

j=0

m
X

sj 2(2α−1)j .

(5.50)

j=0

Combining (3.1), (5.49), and (5.50), we get exactly (5.47).
5.2.2

Bound the variance of A by the square of its expectation

Lemma 5.7. With probability at least π82 , the variance of the random variable output by A is at
most 2n1/α−1 Ẽ 2 .
Pn
P
P
)2 −
Proof of Lemma 5.7. Because Ẽ = ni=1 pi · p̃α−1
and the variance is ni=1 pi · (p̃α−1
i=1 pi ·
i
i

Pn
α−1 2
α−1 2
p̃i
≤ i=1 pi · (p̃i ) , it suffices to show that
n
X

pi ·

(p̃α−1
)2
i

≤ 2n

1/α−1

i=1

By Theorem 2.3, with probability at least

n
X

pi · p̃α−1
i

2

.

(5.51)

i=1
8
,
π2

we have

√
√
2π pi
π pi
|p̃i − pi | ≤
≤ 1/2α
2m
n

21

i ∈ [n].

(5.52)

As a result,
n
X

√
n

X
π pi −2(1−α)
pi pi − 1/2α
n
i=1
n
−2(1−α)

X
π
=
p2α−1
1
−
√
i
n1/2α pi
i=1
n


X
π
≈
p2α−1
1
+
2(1
−
α)
√
i
n1/2α pi
i=1

pi (p̃iα−1 )2 ≤

i=1

=

n
X

p2α−1
+
i

i=1

(5.53)
(5.54)
(5.55)

n
2(1 − α)π X 2α−0.5
pi
.
n1/2α
i=1

(5.56)

Furthermore,
n
n
n
n
n
 X
X
√ X
√  X 2α−1 
√ 2α−1 X 2α−0.5
2α−1
≥
n
pi
pj
pj pi
=
≥
pi
pi
.
i=1

j=1

i=1

i=j=1

(5.57)

i=1

Plugging this into (5.56), we have
n
X

pi (p̃iα−1 )2

i=1

n

2(1 − α)π  X 2α−1
pi
.
≤ 1 + 1/2α−1/2
n
i=1


(5.58)

Using similar techniques, we can show
n
X

pi ·

p̃α−1
i

2

i=1

n

2(1 − α)π  X α 2
pi .
≥ 1−
n1/α−1
i=1


(5.59)

Since 0 < α < 1,
lim 1 +

n→∞

2(1 − α)π
= 1,
n1/2α−1/2

lim 1 −

n→∞

2(1 − α)π
= 1.
n1/α−1

(5.60)

Because (5.55) only omits lower order terms and the limits in (5.60) are both 1, to prove (5.51) it
suffices to prove that for large enough n,
n
X

p2α−1
i

≤n

1/α−1

i=1

n
X

pαi

2

.

(5.61)

i=1

By generalized mean inequality, we have
n
1 X

n

p2α−1
i



1
2α−1

i=1

≤

n
1 X

n

pαi

1

α

.

(5.62)

i=1

Therefore,
n
X

p2α−1
≤ n1−
i

2α−1
α

i=1

n
X

pαi

 2α−1
α

= n1/α−1

n
X
i=1

i=1

Hence the result follows.
22

pαi

2−1/α

≤ n1/α−1

n
X
i=1

pαi

2

.

(5.63)

5.2.3

Analyze the recursive calls

Lemma 5.8. With probability at least 0.92, the a and b in Line 3 or Line 5 of Algorithm 5 are
indeed lower and upper bounds on Pα (p), respectively, and b/a = O(1); furthermore, in Line 5,
Algorithm 5 is recursively called for at most log n log α1 executions, and each recursive call takes at
1
1
most Õ(n α − 2 ) queries.
Proof of Lemma 5.8. Similar to Lemma 5.4, we decompose the proof into two parts:
• In Line 5, Algorithm 5 is recursively called for at most log n log α1 executions, and
1
1
each recursive call takes at most Õ(n α − 2 ) queries:
Because each recursive call of Algorithm 5 increases α by multiplying (1 − log1 n )−1 and
the recursion ends when α > 1 − log1 n , the total number of recursive calls is at most
log α
log(1− log1 n )

≤ log n log α1 .

When α > 1 − log1 n , a and b are set in Line 3 and no extra queries are needed; when Line
5 calls α(1 − log1 n )−k -power sum estimation for some k ∈ N, by induction on k, we see that

(1−1/ log n)k
1
1
− 12
α
this call takes at most Õ n
≤ Õ(n α − 2 ) queries. As a result, when we apply
Corollary 2.2, the cost Ca,b is dominated by the query cost from Algorithm 10.
• With probability at least 0.92, a and b are lower and upper bounds on Pα (p)
respectively, and b/a = O(1):
P
P
When 1 − log1 n < α < 1, on the one hand we have ni=1 pαi ≥ ni=1 pi = 1; on the other hand,
1

because n log n = e, by Lemma 5.3 we have
n
X

pαi ≤ n1−α

n
X
α
pi ≤ e.

i=1

(5.64)

i=1

Therefore, a = 1 and b = e in Line 3 are lower and upper bounds on Pα (p) respectively, and
b/a = e = O(1).
When α < 1 − log1 n , for convenience denote α0 = α(1 − log1 n )−1 . As justified above, the total
number of recursive calls in Line 5 is at most log n log α1 . Because we take δ = 12 log n1log 1/α
in Line 5, with probability at least

log n log 1/α
1
1
1−
≥ 1/12 > 0.92,
(5.65)
12 log n log 1/α
e
the output of every recursive call is within 1/2-multiplicative error. As a result, the P in Line
1
P
0
5 satisfies P/2 ≤ ni=1 pαi ≤ 2P . Combining this with Lemma 5.3 and using n log n = e, we
have
n
X
1− log1 n
1− 1
(P/2)
≤
pαi ≤ e(2P ) log n .
(5.66)
i=1

In other words, a and b are indeed lower and upper bounds on Pα (p), respectively. Furthermore, b/a = O(1) because
b
1− 1
= e · 4 log n ≤ 4e = O(1).
a
23

(5.67)

6

Integer Rényi entropy estimation

Recall the classical query complexity of α-Rényi entropy estimation for α ∈ N, α ≥ 2 is Θ(n1−1/α )
[4], which is smaller than non-integer cases. Quantumly, we also provide a more significant speedup.
Given the oracle Op : [S] → [n] in (1.7), we denote the occurrences of 1, 2, . . . , n among Op (1), . . .,
Op (S) as m1 , . . . , mn , respectively. A key observation is that by (1.6), we have
n
n
X
X
α
−α
Pα (p) =
(mi /S) = S
mαi .
i=1

(6.1)

i=1

P
α
Therefore, it suffices to approximate
i∈[n] mi , which is known as the α-frequency moment of
Op (1), . . . , Op (S). Based on the quantum algorithm for α-distinctness [9], Montanaro [42] proved:
Fact 6.1 ([42], Step 3b-step 3e in Algorithm 2; Lemma 4). Fix l where l ∈ {1, . . . , n}. Let
s1 , . . . , sl ∈ [S] be picked uniformly at random, and denote the number of α-wise collisions in
{Op (s1 ), . . . , Op (sl )} as C(s1 , . . . , sl ). Then:
• C(s1 , . . . , sl ) can be computed using O(lν log(l/2 )) queries to Ôp with failure probability at
most O(2 /l), where ν := 1 − 2α−2 /(2α − 1) < 34 ;

• E[C(s1 , . . . , sl )] = αl Pα (p) and Var[C(s1 , . . . , sl )] = O(1).
However, a direct application of [42] will lead to a complexity depending on S (in particular,
l in Fact 6.1 can be as large as S) rather than n. Our solution is Algorithm 6 that is almost the
same as Algorithm 2 in [42] except Line 1 and Line 2, where we set 2dlog2 αne as an upper bound
on l. We claim that such choice of l is valid because by the pigeonhole principle, αn elements
Op (s1 ), . . . , Op (sαn ) in [n] must have an α-collision, so the first for-loop must terminate at some
i ≤ dlog2 αne. With this modification, we have Theorem 6.1 for integer Rényi entropy estimation.
Algorithm 6: Estimate the α-power sum Pα (p) of p = (pi )ni=1 on [n], α > 1, α ∈ N.
1
2
3
4
5
6
7
8
9

10

Set l = 2dlog2 αne ;
for i = 0, . . . , dlog2 αne do
Pick s1 , . . . , s2i ∈ [S] uniformly at random and let S be the sequence Op (s1 ), . . . , Op (s2i );
Apply the α-distinctness algorithm in [9] to S with failure probability 10dlog1 αne ;
If it returns a set of α equal elements, set l = 2i and terminate the loop;

2

Set M = dK/2 e for some K = Θ(1) ;
for r = 1, . . . , M do
Pick s1 , . . . , sl ∈ [S] uniformly at random;
Apply the first bullet in Fact 6.1 to give an estimate C (r) of the number of α-wise
collisions in {Op (s1 ), . . . , Op (sl )};
PM
(r)
Output P̃α (p) = 1 l
r=1 C ;
M ( α)

Theorem 6.1. Assume α > 1, α ∈ N. Algorithm 6 approximates Pα (p) within a multiplicative
3 (1−1/α) 
ν(1−1/α) 
error 0 <  ≤ O(1) with success probability at least 23 using Õ n 2
= o n 4 2
quantum
3
α−2
α
:=
queries to p, where ν
1−2
/(2 − 1) < 4 .
24

Our proof of Theorem 6.1 is inspired by the proof of Theorem 5 in [42].
Proof. Because Op takes values in [n], by pigeonhole principle, for any s1 , . . . , sαn ∈ [S] there exists
a α-wise collision among Op (s1 ), . . . , Op (sαn ). Therefore, Line 5 terminates the first loop with some
l ≤ 2dlog2 αne with probability at least (1 − 1/10dlog2 αne)dlog2 αne ≥ e−1/10 > 0.9.
Moreover, tighter bounds on l are established next. On the one hand, by Chebyshev’s inequality
B
and Fact 6.1, the probability that the first for-loop fails to terminate when l ≤ P (p)
1/α for some
α
constant B > 0 is at most


 1 

 Var[C(s1 , . . . , sl )]
1
=
O
Pr C(s1 , . . . , sl ) = 0 ≤
=
O
.
(6.2)
E[C(s1 , . . . , sl )]2
l2α Pα (p)2
B 2α

1
Therefore, taking a large enough B ensures that l = O P (p)
with failure probability at most
1/α
α
1/20. On the other hand, by Markov’s inequality and Fact 6.1, we have


Pr C(s1 , . . . , sl ) ≥ 1 ≤ E[C(s1 , . . . , sl )] = O(lα Pα (p)).
(6.3)
As a result, the probability that the first for-loop terminates when l ≤
A > 0 is at most


log2

O(Pα (p)) ·

A
Pα (p)1/α

for some constant

A
Pα (p)1/α

X

2iα = O(Aα ).

(6.4)

i=0


1
Therefore, taking a small enough A > 0 ensures that l = Ω P (p)
with failure probability at
1/α
α

1
most 1/20. In all, we have l = Θ P (p)1/α with probability at least 0.9.
α

By Fact 6.1, the output E[P̃α (p)] in Line 10 of Algorithm 6 satisfies
E[P̃α (p)] =

M
X

1
M


l
α

E[C (r) ] = Pα (p),

Var[P̃α (p)] =

r=1

Therefore, by Chebyshev’s inequality and recall l = Θ

M
X

1
(M


l
α

1
Pα (p)1/α

)2


Var[C (r) ] = O



r=1

1 
. (6.5)
M l2α

, we have


1
1
=
O
.
(6.6)
M l2α 2 Pα (p)2
K


Taking a large enough constant K in Line 6 of Algorithm 6, we have Pr |P̃α (p)−Pα (p)| ≤ Pα (p) ≥
0.9. In all, with probability at least 0.9 × 0.9 × 0.9 > 2/3, P̃α (p) approximates Pα (p) within
multiplicative error .
For the rest of the proof, it suffices to compute the quantum query complexity of Algorithm 6.
Because the α-distinctness algorithm on m elements in [9] takes O(mν log(1/δ)) quantum queries
Plog l
when the success probability is 1−δ, the first for-loop in Algorithm 6 takes i=02 O(2νi logdlog2 αne) =
Õ(lν ) = Õ(nν(1−1/α) ) quantum queries because


1
= O(n1−1/α ),
(6.7)
l=Θ
Pα (p)1/α



Pr |P̃α (p) − Pα (p)| ≥ Pα (p) ≤ O

ν(1−1/α)
2
nν(1−1/α)
2

following from Pα (p) ≥ n1−α . The second for-loop takes dK/2 e · O(lν log(l/2 )) = Õ( n
quantum queries by Fact 6.1 and (6.7). In total, the number of quantum queries is Õ(
25



.



ν(1−1/α) 
Remark 6.1. In Theorem 6.1, we regard α as a constant, i.e., the query complexity Õ( n 2
hides the multiple in α. In fact, by analyzing the dependence on α carefully in the above proof, the
query complexity of Algorithm 6 is actually

nν(1−1/α) 
2
.
(6.8)
Õ α8α ·
2
The dependence on α is super-exponential; therefore, Algorithm 6 is not good enough to approximate
min-entropy (i.e., α = ∞). As a result, we give the quantum algorithm for estimating min-entropy
separately (see Section 7).

7

Min-entropy estimation

Since the min-entropy of p is H∞ (p) = − log maxi∈[n] pi by (1.3), it is equivalent to approximate
maxi∈[n] pi within multiplicative error . We propose Algorithm 7 below to achieve this task.
Algorithm 7: Estimate maxi∈[n] pi of a discrete distribution p = (pi )ni=1 on [n].
1
2
3

4

Set λ = 1;
while λ ≤ n do
n
Take M ∼ Poi( 16λlog
). Pick s1 , . . . , sM ∈ [S] uniformly at random and let S be the
2
sequence Op (s1 ), . . . , Op (sM );
n
Apply a d 16 log
e-distinctness quantum algorithm to S with failure probability at most
2

;
2 log n
n
If Line 4 outputs a d 16 log
e-collision of elements i∗ ∈ [n], apply Theorem 2.3 to
2
approximate
pi∗ with multiplicative error  and output its result; if not, set
√
λ ← λ · 1 +  and jump to the start of the loop;

5

6

If λ > n and no output has been given, output 1/n;

A key property of the Poisson distribution is that if we take M ∼ Poi(ν) samples from p (as
in Line 3), then for each j ∈ [n], the number of occurrences of j in Op (s1 ), . . . , Op (sM ) follows the
Poisson distribution Mj ∼ Poi(νpj ), and Mj , Mj 0 are independent for all j 6= j 0 . Furthermore:
Lemma 7.1. Let X ∼ Poi(µ). Then, if µ <

If µ ≥

16 log n
,
2

√1
1+

·

16 log n
,
2

we have

h
16 log n i
1
Pr X ≥
≤ 2;
2

n

(7.1)

h
16 log n i
Pr X ≥
> 0.15.
2

(7.2)

we have

n
n
Based on Lemma 7.1, our strategy is to set 16 log
as a threshold, take ν = 16λlog
as in Line
2
2
3, and gradually increase the parameter λ. For convenience, denote pi∗ = maxi pi . As long as
n
n
ν · pi∗ < 16 log
, with high probability there is no d 16 log
e-collision
in S, the distinctness quantum
2
2
√
algorithm in Line 4 rejects, and λ increases by multiplying 1 +  in Line 5; right after the first
n
n
time when ν · pi∗ ≥ 16 log
, with probability at least 0.15, i∗ has a d 16 log
e-collision in S, while all
2
2
2
other entries in [n] do not (with failure probability at most 1/n ). In this case, with probability at
least Ω(1), the distinctness quantum algorithm in Line 4 captures i∗ , and the quantum counting
(Theorem 2.3) in Line 5 computes pi∗ within multiplicative error .

26

Theorem 7.1. Algorithm 7 approximates maxi∈[n] pi within a multiplicative error 0 <  ≤ 1 with

n
success probability at least Ω(1) using Õ Q(d 16 log
e-distinctness) quantum queries to p, where
2
n
n
Q(d 16 log
e-distinctness) is the quantum query complexity of the d 16 log
e-distinctness problem.
2
2
We first prove Lemma 7.1. output
Proof of Lemma 7.1. First, we prove (7.1)7 . In [23], it is shown that if λ > 0 and X ∼ Poi(λ), then
for any ν > 1 we have
Pr[X ≥ νλ] ≤
Taking λ =

√1
1+

·

16 log n
2

and ν =

√

e−λ λνλ
.
(νλ)!(1 − 1/ν)

(7.3)

1 + , by Sterling’s formula we have

r
h
16 log n i
2
e−λ λνλ
2 1
e−λ λνλ
√
Pr X ≥
≈ √
≈
≤
2
(νλ)!(1 − 1/ν)
 2πνλ(νλ/e)νλ
π λ

e/2
(1 + 2 )1+/2

!λ
.

(7.4)

Because
e/2
(1 + 2 )1+/2

lim

→0

!8/2

 i
4 
ln
1
+
→0

2

2
h4  8
i
4   2
= lim exp
− 2+
−
+ O(3 )
→0


 2
8
= lim exp[−1 + O()] = e−1 ,
= lim exp

h4

−

8

+

→0

(7.5)
(7.6)
(7.7)

we have
e/2
(1 + 2 )1+/2

!λ

2

≈ e− 8 λ ≈

1
.
n2

(7.8)

Plugging (7.8) into (7.4), we have
r
h
16 log n i
2
1
1
1
√
Pr X ≥
.
≤ 2.
2
2

π 16 log n n
n

(7.9)

Now we prove (7.2). A theorem of Ramanujan [28, Question 294] states that for any positive
integer M ,
M
−1
X
1 M
Mm
MM
e =
+ θ(M ) ·
,
2
m!
M!

(7.10)

m=0

where

1
3

≤ θ(M ) ≤

1
2

∀ M ∈ N. Because
∞
X
m=M +1

7

Mm
m=0 m!

P∞

= eM , by (7.10) we have

Mm 2 MM
1
+ ·
≥ eM .
m!
3 M!
2

The tail bound of Poisson distributions is also studied elsewhere, for example, in [40, Exercise 4.7].

27

(7.11)

By Stirling’s formula, M ! ≥

√

2πM


M M
.
e

As a result,

∞
X


1
1
2
MM
1
Mm
√
≥ eM − · √
−
eM .
=

M M
m!
2
3
2
4.5πM
2πM
m=M +1
e

(7.12)

n
We take M = b 16 log
c. By (7.12), we have
2

h
16 log n
16 log n i
Pr X ≥
= e− 2
2


∞
X
m=M +1

n m
( 16 log
)
2
≥ e−M −1
m!

∞
X

1
1
Mm
. (7.13)
≥
− √
m!
2e e 4.5πM
m=M +1

Because 0 <  ≤ 1, we have M ≥ b16 log 2c = 11. Therefore,
h
16 log n i
1
1
Pr X ≥
≥
− √
> 0.15.
2

2e e 4.5π · 11

(7.14)

Proof of Theorem 7.1. Denote σ to be the permutation on [n] such that pσ(1) ≥ pσ(2) ≥ · · · ≥
pσ(1)
pσ(n) . Without loss of generality, we assume that pσ(2) ≤ 1+
; otherwise, pσ(2) is close enough
to pσ(1) in the sense that applying quantum counting to pσ(2) within multiplicative error  gives
an approximation to pσ(1) within multiplicative error 2. We may assume that every call of the
n
n
d 16 log
e-distinctness quantum algorithm in Line 4 of Algorithm 7 succeeds if and only if a d 16 log
e2
2

log√1+ n

−1
collision exists, because this happens with probability at least 1 − 2 log n
≥ e = Ω(1);
for convenience, this is always assumed in the result of the proof.
On the one hand, when
pσ(1) · 16λ log n
1
16 log n
<√
,
(7.15)
·
2

2
1+

n
by Lemma 7.1 we have Pr Mi ≥ 16 log
≤ n12 ∀ i ∈ [n], where Mi is the occurences of i. Therefore,
2
n
-collision in S.
by the union bound, with probability at least 1 − n · n12 = 1 − n1 , there is no 16 log
2
log n
1 log n/
√
Since the while loop only has at most log 1+ n = O(  ) rounds and (1 − n )
= 1 − o(1), we
may assume that as long
as
(7.15)
holds,
Line
4
of
Algorithm
7
always
has
a
negative
output and
√
Line 5 enforces λ ← λ · 1 +  and jumps to the start of the while loop.
The while loop keeps iterating until (7.15) is violated. In the second iteration after (7.15) is
violated, we have
pσ(1) · 16λ log n √
16 log n
16 log n
≤
< 1+·
;
2
2


2
since pσ(2) ≤

pσ(1)
1+ ,

(7.16)

we have
pσ(2) · 16λ log n
1 16 log n
<√
.
2

1 +  2

(7.17)

As a result, by Lemma 7.1 we have
h
16 log n i
> 0.15;
Pr Mσ(1) ≥
2

h
16 log n i
1
Pr Mi ≥
≤ 2
2
n
28

∀ i ∈ [n]/{σ(1)}.

(7.18)



Therefore, Pr Line 4 outputs σ(1) in the second iteration after (7.15) ish violated ≥i 0.15 · 1 −

n
n−1 n−1
. In the first iteration after (7.15) is violated, we still have Pr Mi ≥ 16 log
≤ n12 ∀ i ∈
2
n
2
[n]/{σ(1)}. Therefore,


Pr Line 4 outputs σ(1) in the first or second iteration after (7.15) is violated

n − 1 n−1 0.15
n − 1 n−1 
·
1
−
≥ 2 = Ω(1).
(7.19)
≥ 0.15 · 1 −
n2
n2
e
In all, with probability Ω(1), Line 4 of Algorithm 7 outputs σ(1) correctly in the first or
second iteration after (7.15) is violated; after that, the quantum counting in Line 5 approximates
pσ(1) = maxi∈[n] pi within multiplicative error . This establishes the correctness of Algorithm 7.

n
It remains to show that the quantum query complexity of Algorithm 7 is Õ Q(d 16 log
e-distinctness)
.
2

n
Because there are at most log√1+ n = O( log n ) iterations in the while loop, the d 16 log
e-distinctness
2
n
algorithm in Line 4 is called for at most O( log n ) times; if it gives a d 16 log
e-collision,
because
2
√

maxi∈[n] pi ≥ 1/n, the quantum query complexity caused by Line 5 is O( n ) by Theorem 2.3,
which is smaller than the Ω(n2/3 ) quantum lower bound on the distinctness problems [2]. As a
result, the query complexity of Algorithm 7 in total is at most
 log n 
l 16 log n m

 √n 
 l 16 log n m

O
·Q
-distinctness
+
O
=
Õ
Q
-distinctness
.
(7.20)

2

2

Remark 7.1. In some special cases, Algorithm 7 already demonstrates provable quantum speedup.
Recall the state-of-the-art quantum algorithm for k-distinctness is [9] by Belovs, which has query
2
k−2
k
complexity O(2k n1−2 /(2 −1) ); however, this is superlinear
√ when k = Θ(log n). Nevertheless, if
we are promised that H∞ (p) ≤ f (n) for some f (n) = o( log n), then we can replace the n in
n
Line 2 of Algorithm 7 by ef (n) and replace every d 16 log
e by d 16f2(n) e, and it can be shown that the
2

3
quantum query complexity of min-entropy estimation is Õ e( 4 +o(1))·f (n) , whereas the best classical
algorithm takes Θ̃(ef (n) ) queries. In this case, we obtain a ( 43 + o(1))-quantum speedup, but the
√
√
classical query complexity is already small (e log n = n1/ log n = o(nc ) for any c > 0).

8

0-Rényi entropy estimation

Motivations. Estimating the support size of distributions (i.e., the 0-Rényi entropy) is also important in various fields, ranging from vocabulary size estimation [20, 58], database attribute variation
[26], password and security [22], diversity study in microbiology [31, 36, 51], etc. The study of
support estimation was initiated by naturalist Corbet in 1940s, who spent two years at Malaya for
trapping butterflies and recorded how many times he had trapped various butterfly species. He
then asked the leading statistician at that time, Fisher, to predict how many new species he would
observe if he returned to Malaya for another two years of butterfly trapping. Fisher answered by
alternatively putting plus or minus sign for the number of species that showed up one, two, three
times, and so on, which was proven to be an unbiased estimator [21].
Formally, assuming n independent samples are drawn from an unknown distribution, the goal
of [21] is to estimate the number of hitherto unseen symbols that would be observed if t · n (t
being a pre-determined parameter) additional independent samples were collected from the same
distribution. Reference [21] solved the case t = 1, which was later improved to t ≤ 1 [24] and
29

Problem
Support coverage
Support size

Θ
Θ

n
log n
m
log m

classical bounds

· log 1 [3, 48] [ = Ω(n−0.2 )]

· log2 1 [48, 63] [ = Ω(1/m)]

quantum bounds (this paper)
 1/3 
√ 
Õ 1.5n , Ω n1/6
 1/3 
√ 
m
Õ 1.5
,Ω m
1/6

Table 2: Summary of the classical and quantum query complexity of support coverage and size estimation.

t = O(log n) [48]; the last work also showed that t = Θ(log n) is the largest possible range to give
an estimator with provable guarantee.
However, such estimation always assumes n samples; a more natural question is, can we estimate
the support of a distribution per se? Specifically, given a discrete distribution p over a finite set X
where px denotes the probability of x ∈ X, can we estimate its support, defined by
Supp(p) := |{x : x ∈ X, px > 0}|,

(8.1)

with high precision and success probability?
Unfortunately, this is impossible in general because elements with negligible but nonzero probability will be very unlikely to appear in the samples, while still contribute to Supp(p). As an
evidence, Supp(p) is the exponent of the 0-Rényi entropy of p, but the sample complexity of αRényi entropy goes to infinity when α → 0+ by Theorem 9.1, both classically and quantumly.
To circumvent this difficulty, two related properties have been considered as an alternative to
estimate 0-Rényi entropy:

P
• Support coverage: Sn (p) := x∈X 1 − (1 − px )n , the expected number of elements observed
when taking n samples. To estimate Sn (p) within ±n, [24] showed that n/2 samples from
p suffices for any constant ; recently, [65] improved the sample complexity to O logn n , and

[3, 48] also considered the dependence in  by showing that Θ logn n · log 1 is a tight bound,
as long as  = Ω(n−0.2 ).
• Support size: Supp(p), under the assumption that for any x ∈ X, px = 0 or px ≥ 1/m for some
given m ∈ N. Reference [53] proposed
the problem and gave a lower bound Ω(m1−o(1) ), and

[60] gave an upper bound O logmm · 12 . Recently, [63] and [48] both proved that Θ logmm ·log2 1
is the tight bound for the problem (both optimal in m and ).
Quantumly, we give upper and lower bounds on both support coverage and support size estimation, summarized in Table 2.
Support coverage estimation. We give the following upper bound on support coverage estimation; its lower bound is given in Proposition 9.2.
Algorithm 8: Estimate the support coverage Sn (p).
1
2
3

Regard the following subroutine as A:
Draw a sample i ∈ X according to p;
√
Use EstAmp with M = 2dlog2 ( n/)e queries to obtain an estimation p̃i of pi ;
1−(1−p̃i )n
if p̃i 6= 0; otherwise, output n;
p̃i


3/2 1
1
1
executions in Theorem
 log
 log log 

4

Output x̃i =

5

Use A for Θ
S̃n (p) of Sn (p);

30

2.1 and output an estimation

Theorem 8.1. Algorithm 8 approximates

Sn (p)
n

:=

P

 ≤ O(1) with success probability at least 2/3 using Õ

n
x∈X (1−(1−px ) )

√

n
n

1.5

within an additive error 0 <

quantum queries to p.

Proof. We prove this theorem in two steps.
step is to show that the expectation of
P The first
1−(1−p̃i )n
the subroutine A’s output (denoted Ẽ := i∈X pi ·
) satisfies |Ẽ − E| = O(n), where
p̃i
P
1−(1−pi )n
E := i∈X pi ·
= Sn (p).
pi
To achieve this, it suffices to prove that for each i ∈ X,
h 1 − (1 − p̃ )n 1 − (1 − p )n i
i
i
−
E
= O(n).
p̃i
pi

(8.2)

We write pi = sin2 (θi π). Assume k ∈ Z such that k ≤ M θi < k + 1. By Theorem 2.3, for any
l ∈ {1, 2, . . . , max{k − 1, M − k − 1}}, the output of EstAmp taking M queries satisfies
h
h
(k + l + 1)π i
(k − l − 1)π i
1
Pr p̃i = sin2
, Pr p̃i = sin2
≤ 2.
(8.3)
M
M
4l

for some l ∈ N. For convenience,
We first consider the case when p̃i > pi , and p̃i = sin2 (k+l+1)π
M
1−(1−x)n
where x ∈ (0, 1]. Because
denote f (x) =
x
f 0 (x) =

nx(1 − x)n−1 + (1 − x)n − 1
nx + (1 − nx) − 1
≤
= 0,
x2
x2

(8.4)

f is a decreasing function on (0, 1]. Therefore,

2 (k+l+1)π n

 
1 − (1 − p̃i )n 1 − (1 − pi )n
2 kπ 1 − 1 − sin
2 kπ n
M
≤ sin
·
(8.5)
−
−
1
−
1
−
sin
p̃i
pi
M
M
sin2 (k+l+1)π
M
(k+l+1)π


kπ 1 − cos2n
2n kπ
M
= sin2
·
−
1
−
cos
(8.6)
M
M
sin2 (k+l+1)π
M


2 (k+l+1)π
2 kπ
2n (k+l+1)π
sin2 kπ
−
sin
+ sin2 (k+l+1)π
cos2n kπ
M
M
M
M − sin M cos
M
. (8.7)
=
sin2 (k+l+1)π
M
By Taylor expansion, we have
sin2

 k6 
kπ
k2 π2
=
+
O
,
M
M2
M6

sin2

 (k + l)6 
(k + l + 1)π
(k + l + 1)2 π 2
=
+
O
,
M
M2
M6

(8.8)

and
cos2n


kπ 
k2 π2
k 4 2n 
k2 π2 
k 2 2 2n
= 1−
+
O
=
1
−
+
O
= 1 − k 2 π 2  + O 2 k 2 ; (8.9)
2
4
2
M
2M
M
2n
n

similarly
cos2n


(k + l + 1)π
= 1 − (k + l + 1)2 π 2  + O 2 (k + l)2 .
M

31

(8.10)

Plugging (8.8), (8.9), and (8.10) into (8.7) and noticing that the tail in (8.8) has 1/M 6 , much
smaller than that of (8.9) and (8.10), we have
1 − (1 − p̃i )n 1 − (1 − pi )n
−
p̃i
pi
2 π2
(k+l+1)2 π 2 
k2 π 2
−
+ (k+l+1)
(1 − k 2 π 2  + O(2 k 2 )) −
M2
M2
M2
≤
(k+l+1)2 π 2

k2 π 2
(1
M2


− (k + l + 1)2 π 2  + O(2 (k + l)2 ))

M2

(8.11)
k 2 − (k + l + 1)


2

+ (k + l + 1)2 (1 − k 2 π 2 ) − k 2 (1 − (k + l + 1)2 π 2 )
(k + l + 1)2
k2
+ O(2 k 2 ) −
O(2 (k + l)2 )
(k + l + 1)2

= 0 + O 2 (k + l)2
=

(8.12)
(8.13)

≤ O(n),

(8.14)
p
where (8.14) holds because k + l ≤ M and M = Θ( n/). Similarly, for the case p̃i < pi , we have
1 − (1 − p̃i )n 1 − (1 − pi )n
−
≤ O(n).
p̃i
pi

(8.15)

In all, summing all l ∈ {1, 2, . . . , max{k − 1, M − k − 1}} in cases p̃i > pi and p̃i < pi and by (8.3),
the expectation of the deviation in (8.2) is at most
M
h 1 − (1 − p̃ )n 1 − (1 − p )n i
X
1
π2
i
i
−
≤2·
· O(n) ≤
· O(n) = O(n).
E
2
p̃i
pi
4l
3

(8.16)

l=1

Therefore, (8.2) follows and |Ẽ − E| = O(n). By rescaling M by a constant, without loss of
generality we have |Ẽ − E| ≤ n/2.
The second step is to bound the variance of the random variable, which is
 1 − (1 − p̃ )n 2  X
X
1 − (1 − p̃i )n 2 X
i
pi ·
−
pi ·
≤
pi · n2 = n2 ,
(8.17)
p̃i
p̃i
i∈X

i∈X

i∈X

because 1 − (1 − p̃i )n ≤ np̃i by 0 ≤ p̃i ≤ 1. As a result of Theorem 2.1, we can approximate Ẽ up
to additive error n/2 with failure probability at most 1/3 using
n
n
 n 
 √n 
√
3/2
dlog2 ( n/)e
O
log
log log
·2
= Õ 1.5
(8.18)
n
n
n

quantum queries. Together with |Ẽ − E| ≤ n/2, Algorithm 8 approximates E = Sn (p) up to
additive error n with failure probability at most 1/3; in other words, Algorithm 8 approximates
E = Sn (p)/n up to  with success probability at least 2/3.
Support size estimation. We give the following upper bound on support size estimation; its
lower bound is given in Proposition 9.3.
Theorem 8.2. Under the promise that for any x ∈ X, px = 0 or px ≥ 1/m, Algorithm 9 approximates
Supp(p)/m within an additive error 0 <  ≤ O(1) with success probability at least 2/3 using
√ 
m
Õ 1.5 quantum queries to p.
32

Algorithm 9: Estimate Supp(p), under the promise that px = 0 or px ≥ 1/m for any x ∈ X.
1
2


Call Algorithm 8 with n = dm log(2/)e and error 2 log(2/)
, and denote the output as S̃n (p);
]
]
:= dS̃n (p)e. Output Supp(p)
Denote Supp(p)
as an estimation of Supp(p);

Proof. For convenience, denote X1/m := {x ∈ X : px ≥ 1/m}. Then Supp(p) = |X1/m | by the
promise, and
1−


≤ 1 − (1 − px )n ≤ 1
2
1 − (1 − px )n = 0

∀ x ∈ X1/m ;

(8.19)

∀x ∈
/ X1/m ;

(8.20)

As a result,
Sn (p) =

X

1 − (1 − px )n ∈

h

1−

x∈X

i

Supp(p), Supp(p) .
2

(8.21)

Furthermore, by the correctness of Algorithm 8, with probability at least 2/3 we have
|S̃n (p) − Sn (p)| ≤


m
·n=
.
2 log(2/)
2

Together with (8.21),
h
m
m i h
m i

Supp(p) −
, Supp(p) +
⊆ Supp(p) − m, Supp(p) +
.
S̃n (p) ∈ 1 −
2
2
2
2
dS̃n (p)e
m

Therefore, with probability at least 2/3,
at least 2/3.

9

approximates

Supp(p)
m

(8.22)

(8.23)

up to  with success probability

Quantum lower bounds

In this section, we prove Theorem 1.2, which is rewritten below:
Theorem 9.1. Any quantum algorithm that approximates Hα (p) of distribution p on [n] within
additive error  with success probability at least 2/3 must use
1

1

• Ω(n 3 / 6 ) quantum queries when α = 0, assuming 1/n ≤  ≤ 1.
1

2

• Ω̃(n 7α −o(1) / 7 ) quantum queries when 0 < α < 37 .
1

1

1

1

• Ω(n 3 / 6 ) quantum queries when

3
7

≤ α ≤ 3, assuming 1/n ≤  ≤ 1.

• Ω(n 2 − 2α /) quantum queries when 3 ≤ α < ∞.
√
• Ω( n/) quantum queries when α = ∞.
Because we use different techniques for different ranges of α, we divide the proofs into three
categories.

33

9.1

Reduction from classical lower bounds (0 < α < 37 )

We prove that the quantum lower bound when 0 < α <
Theorem 9.1.

1

2

is indeed Ω(n 7α −o(1) / 7 ), as claimed in

3
7

1

Proof. First, by [4], we know that Ω(n α −o(1) /2 ) is a lower bound on the classical query complexity
of α-Rényi entropy estimation. On the other hand, reference [1] shows that for any problem that is
invariant under permuting inputs and outputs and that has sufficiently many outputs, the quantum
query complexity is at least the seventh root of the classical randomized query complexity (up to
poly-logarithmic factors). Our query oracle Op : [S] → [n] has n outputs with tend to infinity when n
is large; the distribution p is invariant under permutations on [S] since pi = |{s ∈ [S] : Op (s) = i}|/S
is invariant for all i; Rényi entropy is invariant under permutations on [n] since it does not depend
1
2
on the order of pi . Therefore, our problem satisfies the requirements from [1], and Ω(n 7α −o(1) / 7 )
is a lower bound on the quantum query complexity of α-Rényi entropy estimation.

9.2

Exploitation of the collision lower bound (α = 0 and

3
7

≤ α ≤ 3)

We prove lower bounds on entropy estimation by further exploiting the famous collision lower bound
[2, 38]. First, we define the following problem:
Definition 9.1 (l-pairs distinctness). Given positive integers n and l such that 1 ≤ l ≤ n/2, and a
function f : [n] → [n]. Under the promise that either f is 1-to-1 or their exists l pairwise different
pairs (xi1 , yi1 ), . . . , (xil , yil ) ∈ [n] × [n] such that xij 6= yij but f (xij ) = f (yij ) for all j ∈ [l], the
l-pairs distinctness problem is to determine which is the case, with success probability at least 2/3.
Note that when l = 1, l-pairs distinctness reduces to the element distinctness problem, whose
quantum query complexity is Θ(n2/3 ) [2, 5]; when l = n/2, l-pairs distinctness reduces to the
collision problem, whose quantum query complexity is Θ(n1/3 ) [2, 38]. Inspired by the reduction
from the collision lower bound to the element distinctness lower bound in [2], we prove a more
general quantum lower bound for l-pairs distinctness:
Proposition 9.1. The quantum query complexity of l-pairs distinctness is at least Ω(nα ), where
2
lα = n 3 −α .
Proof. Assume the contrary that the quantum query complexity of l-pairs distinctness is o(nα ).
Consider a function f : [n] → [n] that is promised to be either 1-to-1 or 2-to-1. By [38], it takes
Ω(n1/3 ) quantum queries to decide whether f is 1-to-1
or 2-to-1.
√
Denote S to be a subset of [n], where |S| = d2 nle and the elements in S are chosen uniformly
at random. If f is 1-to-1, then f restricted on S, denoted f |S , is still 1-to-1 on S. If f is 2-to-1,
denote the set of its images as {a1 , . . . , an/2 }. For any j ∈ [n/2], denote Xj to be a binary random
variable that equals to 1 when the collision pair of aj appears in S, and equals to 0 otherwise. Then
|S|
2
n
2



Pr[Xj = 1] =
Denote X =

Pn/2

j=1 Xj ,

|S|
4
n
4



, Pr[Xj Xk = 1] =

∀ j, k ∈ [n], j 6= k.

(9.1)

which is the number of collision pairs in S. By linearity of expectation,
E[X] =

n |S|(|S| − 1)
·
& 2l.
2
n(n − 1)

34

(9.2)

On the other hand,
Var[X] = E[X 2 ] − E[X]2
=

n/2
X

E[Xj ] +

j=1

n
≤ ·
2

X

(9.3)
E[Xj Xk ] − E[X]2

(9.4)

j6=k
|S|
2
n
2




nn
+
−1 ·
2 2

|S|
4
n
4



n2
−
·
4


|S| 2
2

n 2
2

. 2l.

(9.5)
(9.6)

Therefore, by Chebyshev’s inequality,
√ 

Pr[X < l] ≤ Pr X ≤ E[X] − 2 2l ≤ 1/4.

(9.7)

In other words, with probability at least 3/4, f |S on S has at least l collision pairs. By our
assumption, it takes o(|S|α ) = o(nα/2 · n1/3−α/2 ) = o(n1/3 ) quantum queries to decide whether f |S
is 1-to-1 or has l collision pairs, which suffices to decide whether f is 1-to-1 or 2-to-1. However,
this contradicts with the Ω(n1/3 ) quantum lower bound for the collision problem [38].
9.2.1

α=0

For 0-Rényi entropy estimation, we use Proposition 9.1 to give quantum lower bounds for both
support coverage estimation and support size estimation (both defined in Section 8).
1/3 
Proposition 9.2. The quantum query complexity of support coverage estimation is Ω n1/6 , for
1
all n1 ≤  ≤ 12
.
1
Proof. Because n1 ≤  ≤ 12
, we may denote  = nr where r ∈ [−1, 0].
Consider two distributions p1 and p2 encoded by Op1 , Op2 : [n] → X (S = n in (1.7)), where
the nonzero probabilities in p1 are 1/n for n times, and the nonzero probabilities in p2 are 2/n for
l = d6ne times and 1/n for n − 2l times. In other words, Op1 is injective, and Op2 has l collision
pairs but otherwise injective. On the one hand, by Proposition 9.1, it takes Ω(nα ) quantum queries
to distinguish between Op1 and Op2 , where
 1  1 r
2
2
+O
≥ −
∀ r ∈ [−1, 0].
(9.8)
lα = n 3 −α ⇒ α =
3(2 + r)
log n
3 6

As a result, nα ≥ n1/3−r/6 =
On the other hand,

n1/3
.
1/6


n · 1 − (1 − 1/n)n
Sn (p1 )
1
=
≈1− ;
n
n
e


l · 1 − (1 − 2/n)n + (n − 2l) · 1 − (1 − 1/n)n
Sn (p2 )
1 l(1 − 1/e)2
=
≈1− −
.
n
n
e
n
As a result,

(9.9)
(9.10)

Sn (p1 ) Sn (p2 )
l(1 − 1/e)2
−
≈
> 2.
(9.11)
n
n
n
Therefore, if a quantum algorithm can estimate support coverage with error , it can distinguish between p1 and p2 with success probability at least 2/3. In conclusion, the quantum query complexity
1/3 
of support coverage estimation is Ω n1/6 .
35

Similar to the proof of Proposition 9.2, we can prove (with details omitted):
Proposition 9.3. The quantum query complexity of support size estimation is Ω
1
1
m ≤  ≤ 4.
9.2.2

3
7

m1/3
1/6



, for all

≤α≤3

Using Proposition 9.1, we show that the quantum query complexity of entropy estimation when
1
1
3
3
6
7 ≤ α ≤ 3 is also Ω(n / ).
Proof. We consider the case α = 1, i.e., Shannon entropy estimation; the proof for other α ∈ [ 37 , 3]
is basically identical.
Consider two distributions p1 and p2 encoded by Op1 , Op2 : [n] → X (S = n in (1.7)), where
the nonzero probabilities in p1 are 1/n for n times, and the nonzero probabilities in p2 are 2/n
for l = dn/ log 2e times and 1/n for n − 2l times. In other words, Op1 is injective, and Op2 has l
collision pairs but otherwise injective. On the one hand, similar to the proof of Proposition 9.2, it
takes it takes Ω(n1/3−/6 ) quantum queries to distinguish between Op1 and Op2 .
On the other hand,
1
log n = log n;
n
2
n
1
2l
H(p2 ) = l · log + (n − 2l) · log n = log n − log 2.
n
2
n
n

H(p1 ) = n ·

(9.12)
(9.13)

As a result,
|H(p1 ) − H(p2 )| =

2l
log 2 ≥ 2.
n

(9.14)

Therefore, if a quantum algorithm can estimate support coverage with error , it can distinguish between p1 and p2 with success probability at least 2/3. In conclusion, the quantum query complexity
1/3 
of support coverage estimation is Ω n1/6 .

9.3

Polynomial method (3 ≤ α ≤ ∞)

We use the polynomial method [8] to show quantum lower bounds for entropy estimation when
3 ≤ α ≤ ∞. Inspired by the symmetrization technique in [38], we obtain a bivariate polynomial
whose degree is at most two times the corresponding quantum query complexity. Next, similar to
[44], we apply Paturi’s lemma [52] to give a lower bound on the degree of the polynomial. To be
more specific, we prove:
√

Proposition 9.4. The quantum query complexity of estimating min-entropy with error  is Ω(

n
 ).

Proposition 9.5. When the constant α satisfies 1 < α < ∞, the quantum query complexity of
1− 1
2α

estimating α-Rényi entropy with error  is Ω( αn 2

).

Without loss of generality, we assume that the oracle Op in (1.7) satisfies n|S, otherwise consider
the oracle Op0 : [Sn] → [n] such that Op0 (s + Sl) = Op (s) for all s ∈ [S] and l ∈ [n]; this gives an
oracle for the same distribution.
We consider the special case where the probabilities {pi }ni=1 takes at most two different values;
to integrate the probabilities, we assume the existence of two integers c, d where c ∈ {1, . . . , n − 1},
such that pi = n1 − Sd for n − c different i’s in {1, . . . , n}, and pi = n1 + (n−c)d
for the other c i’s in
cS
{1, . . . , n}.
36

Proof of Proposition 9.4. Following the symmetrization technique in [38], we obtain a bivariate
polynomial Q(c, d) where such that the degree of Q is at most two times the query complexity of
min-entropy estimation, and:
 Sc 
• c ∈ {1, . . . , n − 1} and d ∈ {− n(n−c)
, . . . , Sn }. This is because pi ≥ 0 for all i ∈ [n].
• 0 ≤ Q(c, d) ≤ 1 if c|nd. Only if c|nd, S ·
is valid under our model in (1.7).

1
n


is an integer and the distribution {pi }ni=1
+ (n−c)d
cS

Furthermore, we consider the property testing problem of determining whether maxi pi = n1 or
maxi pi ≥ 1+
n , where the accept probability should be at most 1/3 for the former case and at least
2/3 for the latter case. As a result,
• 0 ≤ Q(c, 0) ≤ 1/3: In this case, pi =
• 2/3 ≤ Q(c, d) ≤ 1 if c|nd,

(n−c)d
Sc

1
n

for all i ∈ [n].

≥ n : In this case, ∃ i such that pi =

1
n

+

(n−c)d
cS

1
n

−

d
S

≥

• 2/3 ≤ Q(c, d) ≤ 1 if c|nd, d ≤ − S
n : In this case, ∃ i such that pi =

≥

1+
n .

1+
n .

Therefore, we have
 S 
• 0 ≤ Q(1, d) ≤ 1 for d ∈ {− n(n−1)
, . . . , Sn };
• 0 ≤ Q(1, 0) ≤ 1/3;
 S 
 S 
 
S
• 2/3 ≤ Q(1, d) ≤ 1 for d ∈ {− n(n−1)
, . . . , − S
n } ∪ { n(n−1) , . . . , n }.
Using Paturi’s lower bound [52], we have
q

S
n(n−1)



·

S
n


degd Q(1, d) ≥ Ω 
S/n(n − 1)

!

 √n 
=Ω
.


(9.15)

√
Therefore, deg Q(c, d) ≥ degd Q(1, d) = Ω( n/).
Proof of Proposition 9.5. The proof is similar to that of Proposition 9.4. Following the symmetrization technique, we still obtain a bivariate polynomial Q(c, d) where such that the degree of Q is
at most two
the query complexity of min-entropy estimation, and c ∈ {1, . . . , n − 1}, d ∈
 times
Sc
{− n(n−c)
, . . . , Sn }, 0 ≤ Q(c, d) ≤ 1 if c|nd. Furthermore, we consider the property testing probP
P
2
lem of determining whether i∈[n] pαi ≤ nα−1
or i∈[n] pαi ≥ n2+2
α−1 , where the accept probability
should be at most 1/3 for the former case and at least 2/3 for the latter case. We also assume
 1/α

1
c = 1. On the one hand, when 0 ≤ d ≤ n n−1−1 · Sn , we have n1 + (n−1)d
≤ n1−1/α
, and
S
X
i∈[n]

pαi ≤



1
n1−1/α

α


+ (n − 1)

1 
2
1 α
1 − 1−1/α
≤ α−1 .
n−1
n
n

37

(9.16)

On the other hand, because (1 + m)α ≈ 1 + mα when m = o(1), we have
 1 
 1
3 α
3 α 2 + 2
1
+
+
(n
−
1)
−
− α−1
1
−
n−1
n
n1−1/α αn1−1/α
n1−1/α αn1−1/α

3 α 2 + 2
1
3 α
1
1 
− α−1
+
1 − 1−1/α −
= α−1 1 +
n
α
(n − 1)α−1
n
n
αn1−1/α

1 
α
3α
≈ α−1 1 + 3 + 1 − 1−1/α −
− (2 + 2)
n
n
αn1−1/α
1 
α + 3 
= α−1  − 1−1/α
n
n
≥0
for large enough n. As a result, when d ≥
Therefore, we have

 (1+3/α)n1/α −1
n−1

·

S
n



, we have

·

S
n

P

α
i∈[n] pi

≥

(9.17)
(9.18)
(9.19)
(9.20)

2+2
.
nα−1

• 0 ≤ Q(1, d) ≤ 1 for d ∈ {0, . . . , Sn };

 1/α
• 0 ≤ Q(1, d) ≤ 1/3 for d ∈ {0, . . . , n n−1−1 · Sn };


1/α −1
• 2/3 ≤ Q(1, d) ≤ 1 for d ∈ { (1+3/α)n
· Sn , . . . , Sn }.
n−1
Using Paturi’s lower bound [52], we have
q
degd Q(1, d) ≥ Ω

n1/α −1
n−1

·

S
n



S
n

−

 (3/α)n1/α
n−1
1

 n1/α −1
n−1

·

S
n



 !

1 
 αn 12 − 2α
.
=Ω


(9.21)

1

Therefore, deg Q(c, d) ≥ degd Q(1, d) = Ω(αn 2 − 2α /).
Technically, our proofs only focus on the degree in d for c = 1, but in general it is possible to
prove a better lower bound when analyzing the degree of the polynomial in c and d together. We
leave this as an open problem.

Acknowledgements
We thank Andrew M. Childs for discussions that inspired the proof of Theorem 6.1, and general
suggestions on our manuscript; we thank Yanjun Han for introducing us classical references related
to Shannon and Rényi entropy estimation, in particular his papers [27, 33, 34]. We also thank
anonymous reviewers for helpful comments on an earlier version of this paper. TL acknowledges
support from NSF CCF-1526380.

References
[1] Scott Aaronson and Andris Ambainis, The need for structure in quantum speedups, Theory of
Computing 10 (2014), no. 6, 133–166, arXiv:0911.0996.
[2] Scott Aaronson and Yaoyun Shi, Quantum lower bounds for the collision and the element
distinctness problems, Journal of the ACM (JACM) 51 (2004), no. 4, 595–605.
[3] Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh, A unified
maximum likelihood approach for optimal distribution property estimation, (2017).
38

[4] Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi, Estimating
Renyi entropy of discrete distributions, IEEE Transactions on Information Theory 63 (2017),
no. 1, 38–56, arXiv:1408.1000.
[5] Andris Ambainis, Quantum walk algorithm for element distinctness, SIAM Journal on Computing 37 (2007), no. 1, 210–239, arXiv:quant-ph/0311001.
[6] Erdal Arikan, An inequality on guessing and its application to sequential decoding, IEEE Transactions on Information Theory 42 (1996), no. 1, 99–105.
[7] Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld, The complexity of approximating the entropy, SIAM Journal on Computing 35 (2005), no. 1, 132–150.
[8] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf, Quantum lower bounds by polynomials, Journal of the ACM (JACM) 48 (2001), no. 4, 778–797,
arXiv:quant-ph/9802049.
[9] Aleksandrs Belovs, Learning-graph-based quantum algorithm for k-distinctness, 53rd Annual
Symposium on Foundations of Computer Science, pp. 207–216, IEEE, 2012, arXiv:1205.1534.
[10] Aleksandrs Belovs and Ansis Rosmanis, Adversary lower bounds for the collision and the set
equality problems, arXiv:1310.5185 (2013).
[11] Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Ueli M. Maurer, Generalized privacy
amplification, IEEE Transactions on Information Theory 41 (1995), no. 6, 1915–1923.
[12] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305 (2002), 53–74, arXiv:quant-ph/0005055.
[13] Sergey Bravyi, Aram W. Harrow, and Avinatan Hassidim, Quantum algorithms for testing
properties of distributions, IEEE Transactions on Information Theory 57 (2011), no. 6, 3971–
3981, arXiv:0907.3920.
[14] Yuheng Bu, Shaofeng Zou, Yingbin Liang, and Venugopal V. Veeravalli, Estimation of KL
divergence: Optimal Minimax Rate, arXiv:1607.02653 (2016).
[15] Olivier Catoni, Statistical learning theory and stochastic optimization: Ecole d’eté de probabilités de saint-flour xxxi-2001, Springer, 2004.
[16] Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf, New results on quantum property testing, Thirtieth International Conference on Foundations of Software Technology and Theoretical Computer Science, p. 145, 2010, arXiv:1005.0523.
[17] Imre Csiszár, Generalized cutoff rates and Rényi’s information measures, IEEE Transactions
on Information Theory 41 (1995), no. 1, 26–34.
[18] Imre Csiszar and János Körner, Information theory: coding theorems for discrete memoryless
systems, Cambridge University Press, 2011.
[19] Paul Dagum, Richard Karp, Michael Luby, and Sheldon Ross, An optimal algorithm for Monte
Carlo estimation, SIAM Journal on Computing 29 (2000), no. 5, 1484–1496.
[20] Bradley Efron and Ronald Thisted, Estimating the number of unseen species: How many words
did Shakespeare know?, Biometrika 63 (1976), no. 3, 435–447.
39

[21] Ronald A. Fisher, Alexander S. Corbet, and Carrington B. Williams, The relation between the
number of species and the number of individuals in a random sample of an animal population,
The Journal of Animal Ecology (1943), 42–58.
[22] Dinei Florencio and Cormac Herley, A large-scale study of web password habits, Proceedings
of the 16th International Conference on World Wide Web, pp. 657–666, ACM, 2007.
[23] Peter W. Glynn, Upper bounds on Poisson tail probabilities, Operations Research Letters 6
(1987), no. 1, 9–14.
[24] I. J. Good and G. H. Toulmin, The number of new species, and the increase in population
coverage, when a sample is increased, Biometrika 43 (1956), no. 1-2, 45–63.
[25] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu, Sampleoptimal tomography of quantum states, Proceedings of the 48th Annual ACM Symposium on
Theory of Computing, pp. 913–925, ACM, 2016, arXiv:1508.01797.
[26] Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, and Lynne Stokes, Sampling-based estimation
of the number of distinct values of an attribute, Proceedings of 21th International Conference
on Very Large Data Bases, vol. 95, pp. 311–322, 1995.
[27] Yanjun Han, Jiantao Jiao, and Tsachy Weissman, Minimax rate-optimal estimation of divergences between discrete distributions, arXiv:1605.09124 (2016).
[28] Godfrey H. Hardy, P. V. Seshu Aiyar, and Bertram M. Wilson, Collected papers of Srinivasa
Ramanujan, AMS, 1927.
[29] Ralph V. L. Hartley, Transmission of information, Bell Labs Technical Journal 7 (1928), no. 3,
535–563.
[30] Peter Høyer, Troy Lee, and Robert Spalek, Negative weights make adversaries stronger, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 526–535, ACM,
2007, arXiv:quant-ph/0611054.
[31] Jennifer B. Hughes, Jessica J. Hellmann, Taylor H. Ricketts, and Brendan J. M. Bohannan,
Counting the uncountable: statistical approaches to estimating microbial diversity, Applied and
Environmental Microbiology 67 (2001), no. 10, 4399–4406.
[32] Russell Impagliazzo and David Zuckerman, How to recycle random bits, 30th Annual Symposium on Foundations of Computer Science, pp. 248–253, IEEE, 1989.
[33] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman, Maximum likelihood estimation of functionals of discrete distributions, arXiv:1406.6959 (2014).
[34]

, Minimax estimation of functionals of discrete distributions, IEEE Transactions on
Information Theory 61 (2015), no. 5, 2835–2885, arXiv:1406.6956.

[35] Diederik P. Kingma and Max Welling, Auto-encoding variational bayes, arXiv:1312.6114
(2013).
[36] Ian Kroes, Paul W. Lepp, and David A. Relman, Bacterial diversity within the human subgingival crevice, Proceedings of the National Academy of Sciences 96 (1999), no. 25, 14547–14552.
[37] Solomon Kullback, Information theory and statistics, Courier Corporation, 1997.
40

[38] Samuel Kutin, Quantum lower bound for the collision problem with small range, Theory of
Computing 1 (2005), no. 1, 29–36.
[39] Lucien Le Cam, Asymptotic methods in statistical decision theory, Springer Science & Business
Media, 2012.
[40] Michael Mitzenmacher and Eli Upfal, Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis, Cambridge University Press, 2005.
[41] Ashley Montanaro, Quantum speedup of Monte Carlo methods, Proc. R. Soc. A, vol. 471,
p. 20150301, The Royal Society, 2015, arXiv:1504.06987.
[42]

, The quantum complexity of approximating the frequency moments, Quantum Information & Computation 16 (2016), no. 13&14, 1169–1190, arXiv:1505.00113.

[43] Ashley Montanaro and Ronald de Wolf, A survey of quantum property testing, arXiv:1310.2035
(2013).
[44] Ashwin Nayak and Felix Wu, The quantum query complexity of approximating the median and
related statistics, Proceedings of the 31st Annual ACM Symposium on Theory of Computing,
pp. 384–393, ACM, 1999, arXiv:quant-ph/9804066.
[45] Ryan O’Donnell and John Wright, Quantum spectrum testing, Proceedings of the 47th Annual
ACM on Symposium on Theory of Computing, pp. 529–538, ACM, 2015, arXiv:1501.05028.
[46]

, Efficient quantum tomography, Proceedings of the 48th Annual ACM Symposium on
Theory of Computing, pp. 899–912, ACM, 2016, arXiv:1508.01907.

[47]

, Efficient quantum tomography II, Proceedings of the Forty-ninth Annual ACM
SIGACT Symposium on Theory of Computing, pp. 962–974, ACM, 2017, arXiv:1612.00034.

[48] Alon Orlitsky, Ananda Theertha Suresh, and Yihong Wu, Optimal prediction of the number of
unseen species, Proceedings of the National Academy of Sciences 113 (2016), no. 47, 13283–
13288.
[49] Liam Paninski, Estimation of entropy and mutual information, Neural Computation 15 (2003),
no. 6, 1191–1253.
[50]

, Estimating entropy on m bins given fewer than m samples, IEEE Transactions on
Information Theory 50 (2004), no. 9, 2200–2203.

[51] Bruce J. Paster, Susan K. Boches, Jamie L. Galvin, Rebecca E. Ericson, Carol N. Lau, Valerie A. Levanos, Ashish Sahasrabudhe, and Floyd E. Dewhirst, Bacterial diversity in human
subgingival plaque, Journal of Bacteriology 183 (2001), no. 12, 3770–3783.
[52] Ramamohan Paturi, On the degree of polynomials that approximate symmetric Boolean functions (preliminary version), Proceedings of the 24th Annual ACM Symposium on Theory of
Computing, pp. 468–474, ACM, 1992.
[53] Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith, Strong lower bounds for
approximating distribution support size and the distinct elements problem, SIAM Journal on
Computing 39 (2009), no. 3, 813–842.

41

[54] Alfréd Rényi, On measures of entropy and information, Proceedings of the 4th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 547–561, 1961.
[55] Dana Ron, Algorithmic and analysis techniques in property testing, Foundations and Trends
in Theoretical Computer Science 5 (2010), no. 2, 73–205.
[56] Claude E. Shannon, A mathematical theory of communication, Bell System Technical Journal
27 (1948), no. 3, 379–423.
[57] Daniel Štefankovič, Santosh Vempala, and Eric Vigoda, Adaptive simulated annealing: A nearoptimal connection between sampling and counting, Journal of the ACM (JACM) 56 (2009),
no. 3, 18, arXiv:cs/0612058.
[58] Ronald Thisted and Bradley Efron, Did Shakespeare write a newly-discovered poem?,
Biometrika 74 (1987), no. 3, 445–455.
[59] Salil P. Vadhan, Pseudorandomness, Foundations and Trends R in Theoretical Computer Science 7 (2012), no. 1–3, 1–336.
[60] Gregory Valiant and Paul Valiant, Estimating the unseen: an n/log(n)-sample estimator for
entropy and support size, shown optimal via new CLTs, Proceedings of the 43rd Annual ACM
Symposium on Theory of Computing, pp. 685–694, ACM, 2011.
[61] Paul Valiant, Testing symmetric properties of distributions, SIAM Journal on Computing 40
(2011), no. 6, 1927–1968.
[62] Paul C. van Oorschot and Michael J. Wiener, Parallel collision search with cryptanalytic applications, Journal of Cryptology 12 (1999), no. 1, 1–28.
[63] Yihong Wu and Pengkun Yang, Chebyshev polynomials, moment matching, and optimal estimation of the unseen, arXiv:1504.01227 (2015).
[64]

, Minimax rates of entropy estimation on large alphabets via best polynomial approximation, IEEE Transactions on Information Theory 62 (2016), no. 6, 3702–3720, arXiv:1407.0381.

[65] James Zou, Gregory Valiant, Paul Valiant, Konrad Karczewski, Siu-On Chan, Kaitlin
Samocha, Monkol Lek, Shamil Sunyaev, Mark Daly, and Daniel G. MacArthur, Quantifying
unobserved protein-coding variants in human populations provides a roadmap for large-scale
sequencing projects, Nature communications 7 (2016).

A

Theorem 2.2: Multiplicative quantum Chebyshev inequality

The main technique that we use is Lemma 4 in [41], which approximates a random variable with
an additive error as long as its second-moment is bounded:
Lemma A.1 (Lemma 4 in [41]). Assume A is a quantum algorithm that outputs a random variable
X. Then for  where 0 <  < 1/2 (multiplicative error), by using O((1/) log3/2 (1/) log log(1/))
executions of A and A−1 , Algorithm 2 in [41] outputs an estimate Ẽ[X] of E[X] such that8
p


Pr Ẽ[X] − E[X] ≥ ( E[X 2 ] + 1)2 ≤ 1/50.
(A.1)
8

The original error probability in (A.1) is 1/5, but it can be improved to 1/50 by rescaling the parameters in
Lemma 4 in [41] up to a constant.

42

Based on Lemma A.1 and inspired by Algorithm 3 and Theorem 5 in [41], we propose Algorithm 10.
Algorithm 10: Estimate E[X] within multiplicative error .
1
2
3
4

5

6

Run the algorithm that gives a, b such that E[X] ∈ [a, b];
Set A0 = A/σb;
Run A0 once and denote m
e to be the output. Set B = A0 − m;
e
Let B− be the algorithm that calls B once; if B outputs x ≥ 0 then B− outputs 0, and if B
outputs x < 0 then B− outputs x. Similarly, let B+ be the algorithm such that if B outputs
x < 0 then B+ outputs 0, and if B outputs x ≥ 0 then B+ outputs x;
a
Apply Lemma A.1 to −B− /6 and B+ /6 with error 48σb
and failure probability 1/50, and
obtain estimates µ
e− and µ
e+ , respectively;
Output Ẽ[X] = σb(m
e − 6e
µ− + 6e
µ+ );

Proof of Theorem 2.2. Because Var[X] ≤ σ 2 E[X]2 ≤ σ 2 b2 , by Chebyshev’s inequality we have


Pr m
e − E[X/σb] ≥ 4 ≤ 1/16.
(A.2)
X
− m,
e
Therefore, with probability at least 15/16 we have |m
e − E[X/σb]| ≤ 4. Denote XB = σb
which is the random variable output by B; XB,+ := max{XB , 0} is then the output of B+ and
XB,− := min{XB , 0} is the output of B− . Assuming |m
e − E[X/σb]| ≤ 4, we have

h X
 X 
X 
 2 i
2
]=E
E[XB
−E
+ E
−m
e
(A.3)
σb
σb
σb
h  X 
h X
2 i
 X  2 i
+ 2E E
≤ 2E
−E
−m
e
(A.4)
σb
σb
σb
≤ 2(12 + 42 ) = 34.
(A.5)






Therefore, E (XB /6)2 ≤ 34/36 < 1, hence E (XB,+ /6)2 < 1 and E (−XB,− /6)2 < 1. By
Lemma A.1, we have
µ
e− − E[−XB,− /6] ≤

a
12σb

and

µ
e+ − E[XB,+ /6] ≤

a
12σb

both with failure probability at most 1/50. Because


E[X] = σb m
e + E[XB ] = σb m
e + E[XB,+ ] − E[−XB,− ] ,

(A.6)

(A.7)

with probability at least 15/16 · (1 − 1/50)2 > 9/10, we have
Ẽ[X] − E[X] ≤ σb · 6 µ
e− − E[−XB,− /6] + 6 µ
e+ − E[XB,+ /6]
a
≤ σb · 2 · 6 ·
= a ≤ E(X).
12σb

43



(A.8)
(A.9)

