In this article the randomized algorithm for estimating the von Neumann entropy of large-scale density matrices is considered. By capturing the dominant eigenspace via a k-rank approximation of the density matrix we estimate the entropy. We analyze the error bound with the eigenvalues of density matrix. Numerical experiments show that the proposed method is extensively efficient for large-scale density matrices.
In this article the randomized algorithm for estimating the von Neumann entropy of large-scale density matrices is considered. By capturing the dominant eigenspace via a k-rank approximation of the density matrix we estimate the entropy. We analyze the error bound with the eigenvalues of density matrix. Numerical experiments show that the proposed method is extensively efficient for large-scale density matrices.
, named after John von Neumann, is an extension of the classical concept of entropy to the field of quantum mechanics. From a numerical perspective, von Neumann entropy can be computed simply by computing all eigenvalues of a density matrix, an operation that could be prohibitively expensive for large-scale density matrices. We present and analyze three randomized algorithms to approximate von Neumann entropy of real density matrices: our algorithms leverage recent developments in the Randomized Numerical Linear Algebra (RandNLA) literature, such as randomized trace estimators, provable bounds for the power method, and the use of random projections to approximate the eigenvalues of a matrix. All three algorithms come with provable accuracy guarantees and our experimental evaluations support our theoretical findings showing considerable speedup with small loss in accuracy.
In this paper, we show how the entropy (including the von Neumann entropy obtained by tracing across various sizes of subsystems, the entanglement gap, as well as different degrees of Rényi entropy) of the random reduced density matrices are related to their dominant eigenvalue. Analytical results are deduced from Random Matrix Theory (RMT) for decentralized Wishart matrices and backed up by computer simulations. The correlation between our study and entanglement generated by quantum computing is provided with various examples.
We show that the von Neumann entropy of an unknown d-dimensional quantum state ρ can be estimated to within additive error ε using Θ(εlog2(d)(1+εlog2(d))d2+ε2log2(d)) samples of ρ, matching the lower bound due to Wang (2026). Our estimator is based on a high-degree approximation polynomial and the main technical challenge is bounding its variance despite the large polynomial degree. We overcome this using a quantum Hoeffding decomposition, which preserves cancellations between different polynomial terms and reduces the analysis to derivative bounds for the approximation polynomial.
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.