We describe a quantum algorithm to estimate the $\ensuremath{\alpha}$-Renyi entropy of an unknown density matrix $\ensuremath{\rho}\ensuremath{\in}{\mathbb{C}}^{d\ifmmode\times\else\texttimes\fi{}d}$ for $\ensuremath{\alpha}\ensuremath{\ne}1$ by combining the recent technique of quantum singular value transformations with the method of estimating normalized traces in the one clean qubit model. We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be nonsingular. Our method outputs an estimate of the $\ensuremath{\alpha}$-Renyi entropy to additive precision $\ensuremath{\epsilon}$, using an expected total number $O(\frac{1}{{(x\ensuremath{\epsilon})}^{2}})$ of independent applications of a quantum circuit which coherently queries the input unitary $O(\frac{1}{\ensuremath{\delta}}log\frac{d}{\ensuremath{\epsilon}})$ times, in each case measuring a single output qubit. Here $\ensuremath{\delta}$ is a lower cutoff on the smallest eigenvalue of $\ensuremath{\rho}$ and $x=\frac{1}{d}\mathrm{Tr}({\ensuremath{\rho}}^{\ensuremath{\alpha}})$. The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require $\mathrm{\ensuremath{\Theta}}(\frac{{d}^{2}}{{\ensuremath{\epsilon}}^{2}})$ samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension $d$.
We describe a quantum algorithm to estimate the \ensuremathα-Renyi entropy of an unknown density matrix \ensuremathρ\ensuremath∈Cd\ifmmode×\else\texttimes\fid for \ensuremathα\ensuremath=1 by combining the recent technique of quantum singular value transformations with the method of estimating normalized traces in the one clean qubit model. We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be nonsingular. Our method outputs an estimate of the \ensuremathα-Renyi entropy to additive precision \ensuremathϵ, using an expected total number O((x\ensuremathϵ)21) of independent applications of a quantum circuit which coherently queries the input unitary O(\ensuremathδ1log\ensuremathϵd) times, in each case measuring a single output qubit. Here \ensuremathδ is a lower cutoff on the smallest eigenvalue of \ensuremathρ and x=d1Tr(\ensuremathρ\ensuremathα). The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require \ensuremathΘ(\ensuremathϵ2d2) samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension d.
Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating Rényi entropies as specific examples. In particular, given a quantum oracle that prepares ann-dimensional quantum state Σni=1√pi|i⟩, for α > 1 and 0Hα(p) to within additive error ϵ with probability at least 2/3 using Õ(n1-1/2α/ϵ + √n/ϵ1+ 1/2α) and Õ(n1/2α/ϵ1+ 1/2α) queries, respectively. This improves the best known dependence in ϵ as well as the joint dependence betweennand 1/ϵ. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications.
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy S(ρ) and Rényi entropy S_α(ρ) of an N-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following quantum estimators. - A quantum estimator for S(ρ) with time complexity Õ(N²), improving the prior best time complexity Õ(N⁶) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). - A quantum estimator for S_α(ρ) with time complexity Õ(N^{4/α-2}) for 0 < α < 1 and Õ(N^{4-2/α}) for α > 1, improving the prior best time complexity Õ(N^{6/α}) for 0 < α < 1 and Õ(N⁶) for α > 1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound Ω(max{N/ε, N^{1/α-1}/ε^{1/α}}) for estimating S_α(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle U block-encodes a mixed quantum state ρ, any quantum query algorithm using Q queries to U can be samplized to a δ-close (in the diamond norm) quantum algorithm using Θ~(Q²/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.
The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error ε, rank upper bound R, and fixed order α. Tsallis entropy estimation has near-optimal rank-independent query complexity O(ε−1/(α−1)) for 1<α<2, when the allowed dimension and rank accommodate the lower-bound instances, and O(1/ε) for α≥2, where O suppresses logarithmic factors. The first saves a factor 1/ε; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from O(R/ε2) to O(R/ε) and obtain O(R/ε) for noninteger Rényi orders 1<α<3, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using O(R/ε) queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy S(ρ) and Rényi entropy Sα(ρ) of an N-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following: 1. A quantum estimator for S(ρ) with time complexity O~(N2), improving the prior best time complexity O~(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for Sα(ρ) with time complexity O~(N4/α−2) for 0<α<1 and O~(N4−2/α) for α>1, improving the prior best time complexity O~(N6/α) for 0<α<1 and O~(N6) for α>1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound for estimating Sα(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle U block-encodes a mixed quantum state ρ, any quantum query algorithm using Q queries to U can be samplized to a δ-close (in the diamond norm) quantum algorithm using Θ~(Q2/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.
Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy Hα(p) for any distribution p=(pi)i=1n given its purified quantum query-access. For non-integer α>1, our algorithm estimates Hα(p) to within additive error ε using only O(nmax{1/2,1−1/α}/ε) queries, which improves the best known upper bound for dependence on both n and 1/ε. For 0<α<1, our algorithm has query complexity O(n1/(2α)/εmax{1,1/(2α)}), which improves the dependence on 1/ε of the current best upper bound without incresing its n dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to Ω(1/εmax{1,1/(2α)}) for 0<α<1, which identifies the optimal precision dependence of our algorithm.
Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the problem of obtaining estimates to within a multiplicative factor γ>1 of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum states. Our main results are: ∙ an O(n2γ21+η)-query quantum algorithm that outputs a γ-multiplicative approximation of the Shannon entropy H(p) of a classical probability distribution p=(p1,…,pn); ∙ an O(n21+2γ21+η)-query quantum algorithm that outputs a γ-multiplicative approximation of the von Neumann entropy S(ρ) of a density matrix ρ∈Cn×n. In both cases, the input is assumed to have entropy bounded away from zero by a quantity determined by the parameter η>0, since, as we prove, no polynomial query algorithm can multiplicatively approximate the entropy of distributions with arbitrarily low entropy. In addition, we provide Ω(n3γ21) lower bounds on the query complexity of γ-multiplicative estimation of Shannon and von Neumann entropies. We work with the quantum purified query access model, which can handle both classical probability distributions and mixed quantum states, and is the most general input model considered in the literature.