The entropy of a quantum system is a measure of its randomness and is useful in quantifying entanglement. We study the problem of measuring the von Neumann and Rényi entropies of an unknown mixed quantum state given access to independent copies of the state. For Rényi entropy of integral order exceeding one, we determine the order-optimal copy complexity and show that it is strictly lower than the number of copies required to learn the underlying state. The main technical innovation is a concentration result for certain polynomials that arise in the Kerov algebra of Young diagrams, which is proven using the cycle structure of compositions of certain types of permutations. For von Neumann entropy and Rényi entropy of non-integral orders, we provide upper and lower bounds on the sample complexity of the Empirical Young Diagram (EYD) algorithm, which is the analogue of the empirical plug-in estimator in classical estimation.
The entropy of a quantum system is a measure of its randomness and is useful in quantifying entanglement. We study the problem of measuring the von Neumann and Rényi entropies of an unknown mixed quantum state given access to independent copies of the state. For Rényi entropy of integral order exceeding one, we determine the order-optimal copy complexity and show that it is strictly lower than the number of copies required to learn the underlying state. The main technical innovation is a concentration result for certain polynomials that arise in the Kerov algebra of Young diagrams, which is proven using the cycle structure of compositions of certain types of permutations. For von Neumann entropy and Rényi entropy of non-integral orders, we provide upper and lower bounds on the sample complexity of the Empirical Young Diagram (EYD) algorithm, which is the analogue of the empirical plug-in estimator in classical estimation.
The entropy of a quantum system is a measure of its randomness, and has applications in measuring quantum entanglement. We study the problem of estimating the von Neumann entropy, S(ρ), and Rényi entropy, Sα(ρ) of an unknown mixed quantum state ρ in d dimensions, given access to independent copies of ρ. We provide algorithms with copy complexity O(d2/α) for estimating Sα(ρ) for α2) for estimating S(ρ), and Sα(ρ) for non-integral α > 1. These bounds are at least quadratic in d, which is the order dependence on the number of copies required for estimating the entire state ρ. For integral α > 1, on the other hand, we provide an algorithm for estimating Sα(ρ) with a sub-quadratic copy complexity of O(d2-2/α), and we show the optimality of the algorithms by providing a matching lower bound.
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 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 entropyS(ρ) and Rényi entropySα(ρ) of anN-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following quantum estimators. • A quantum estimator forS(ρ) with time complexity Õ (N2),1improving the prior best time complexity Õ(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). • A quantum estimator forSα(ρ) with time complexity Õ (N4/α−2) for 0N4−2/α) for α > 1, improving the prior best time complexity Õ(N6/α) for 0N6) 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/ε,N1/α−1/ε1/α}) for estimatingSα(ρ). 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 calledsamplizer, which can “samplize” a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a new framework for estimating quantum entropies. Specifically, when a quantum oracleUblockencodes a mixed quantum state ρ, any quantum query algorithm usingQqueries toUcan 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 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.
Entropy measures quantify the amount of information and correlation present in a quantum system. In practice, when the quantum state is unknown and only copies thereof are available, one must resort to the estimation of such entropy measures. Here we propose a variational quantum algorithm for estimating the von Neumann and R\'enyi entropies, as well as the measured relative entropy and measured R\'enyi relative entropy. Our approach first parametrizes a variational formula for the measure of interest by a quantum circuit and a classical neural network and then optimizes the resulting objective over parameter space. Numerical simulations of our quantum algorithm are provided, using a noiseless quantum simulator. The algorithm provides accurate estimates of the various entropy measures for the examples tested, which renders it a promising approach for usage in downstream tasks.
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.