Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1801.01072 · IEEE Transactions on Information Theory

Randomized Linear Algebra Approaches to Estimate the Von Neumann Entropy of Density Matrices

Eugenia-Maria Kontopoulou, Gregory Dexter, Wojciech Szpankowski, Ananth Y. Grama, Petros Drineas B

Published Jun 1, 2018• 22 citations
arXivHTMLPDF

Abstract

The von Neumann entropy, 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.

DOI
10.1109/tit.2020.2971991

Related papers

RANDOMIZED METHOD FOR ESTIMATING THE VON NEUMANN ENTROPY OF LARGE-SCALE DENSITY MATRICES

Hayoung Choi, Xuming Song, Yuanming Shi

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.

IEEE Global Conference on Signal and Information Processing•Nov 1, 2018•3 citations

Sublinear quantum algorithms for estimating von Neumann entropy

Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian

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: $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac{1+η}{2γ^2}}\right)$-query quantum algorithm that outputs a $γ$-multiplicative approximation of the Shannon entropy $H(\mathbf{p})$ of a classical probability distribution $\mathbf{p} = (p_1,\ldots,p_n)$; $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac12+\frac{1+η}{2γ^2}}\right)$-query quantum algorithm that outputs a $γ$-multiplicative approximation of the von Neumann entropy $S(ρ)$ of a density matrix $ρ\in\mathbb{C}^{n\times 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 $Ω\left(n^{\frac{1}{3γ^2}}\right)$ 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.

arXiv:2111.11139•Nov 22, 2021•44 citations

New Quantum Algorithms for Computing Quantum Entropies and Distances

Qisheng Wang, Ji Guan, Junyi Liu +2 more

We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances, including the von Neumann entropy, quantum Rényi entropy, trace distance, and fidelity. The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case, some of which achieve exponential speedups. In particular, forN-dimensional quantum states of rankr, our proposed quantum algorithms for computing the von Neumann entropy, trace distance and fidelity within additive error ε have time complexity of Õ(r/ε2), Õ(r5/ε6) and Õ(r6.5/ε7.5), respectively. By contrast, prior quantum algorithms for the von Neumann entropy and trace distance usually have time complexity Ω(N), and the prior best one for fidelity has time complexity Õ(r12.5/ε13.5). The key idea of our quantum algorithms is to extend block-encoding from unitary operators in previous work to quantum states (i.e., density operators). It is realized by developing several convenient techniques to manipulate quantum states and extract information from them. The advantage of our techniques over the existing methods is that no restrictions on density operators are required; in sharp contrast, the previous methods usually require a lower bound on the minimal non-zero eigenvalue of density operators.

arXiv:2203.13522•IEEE Transactions on Information Theory•May 13, 2024•79 citations

Quantum entropies of nonprobabilistic matrices

Guy Jumarie

Von Neumann defined the informational entropy of a density matrix ρ by the expression S(ρ)=−tr(ρ ln ρ). [J. Von Neumann, Die Mathematischen Grundlagen der Quantummechanik (Springer-Verlag, Berlin, 1932)]. Here, starting from the definitions of Shannon entropy and of Renyi entropy of random variables, and using some (reasonable) rules of inference, two expressions are obtained for the quantum entropy of a given square (deterministic) matrix, irrespective of any probabilistic framework and/or any randomization technique. These definitions apply directly to linear operators on Hilbert spaces even when they are not of positive trace class, and they contain Von Neumann entropy as a special case. These new measures of uncertainty could provide new approaches to some problems related to structure complexity.

Journal of Mathematical Physics•Nov 1, 1991•5 citations

Entropy in Quantum Probability I

Dėnes Petz

The notion of entropy was introduced by Clausius in order to discuss the thermal behavior of physical systems. After the work of Clausius, Boltzmann, Gibbs and others, the beginning of the exact treatment of entropy was due to von Neumann and Shannon. Their starting point was very di erent, von Neumann was motivated by quantum mechanics and Shannon founded communication theory. The entropy of a state describing a physical system is a quantity expressing the uncertainty or randomness of the system. Shannon regarded this uncertainty attached to a physical system as the amount of information carried by the system, so that the entropy of a state can be read as the information carried by the state. His idea comes from the following consideration: If a physical system has a large uncertainty and one receives information on the system by some procedure, then the so obtained information is more valuable than that received from a system having less uncertainty. It is understood in probability theory that the notion of (Shannon or measure theoretic) entropy has successful applications in a variety of subjects because it determines the asymptotic behavior of certain probabilities in the course of independent trials. First we will discuss this phenomena for nite quantum systems. By a nite quantum system we mean an algebra of matrices which is stable under taking adjoint. (In other words, a nite quantum system is a nite dimensional C*algebra.) If A is such an algebra then there is a linear functional Tr which takes the value 1 at each minimal projection. It is "tracial " in the sense that Tr ab = Tr ba (a; b 2 A) Every functional! on A is determined by a density operator D! 2 A in the form!(a) = Tr D! a (a 2 A): The entropy S(!) of a functional! is de ned by means of its density operator as S(!) = Tr (D!): This notion was introduced by von Neumann in 1927 and we term it von Neumann's entropy or shortly entropy (cf. [1]). In fact, von Neumann de ned the entropy such

QP-PQ, quantum probability and white noise analysis•Jul 1, 1992•2 citations

Quantum Algorithms for Spectral Sums

Alessandro Luongo, Changpeng Shao

We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. For a matrix A and a function f, the spectral sum is the trace of f(A), equivalently the sum over eigenvalues of A of f applied to each eigenvalue. Typical examples of spectral sums are the von Neumann entropy, the trace of the inverse of A, the log-determinant, and the Schatten p-norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees in a graph.

Proceedings of the AAAI Conference on Artificial Intelligence•Mar 14, 2026•1 citation
The von Neumann entropy, 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.
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γ>1γ>1 of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum states. Our main results are: ∙\quad\bullet∙ an O~(n1+η2γ2)\widetilde{\mathcal{O}}\left( n^{\frac{1+η}{2γ^2}}\right)O(n2γ21+η​)-query quantum algorithm that outputs a γγγ-multiplicative approximation of the Shannon entropy H(p)H(\mathbf{p})H(p) of a classical probability distribution p=(p1,…,pn)\mathbf{p} = (p_1,\ldots,p_n)p=(p1​,…,pn​); ∙\quad\bullet∙ an O~(n12+1+η2γ2)\widetilde{\mathcal{O}}\left( n^{\frac12+\frac{1+η}{2γ^2}}\right)O(n21​+2γ21+η​)-query quantum algorithm that outputs a γγγ-multiplicative approximation of the von Neumann entropy S(ρ)S(ρ)S(ρ) of a density matrix ρ∈Cn×nρ\in\mathbb{C}^{n\times n}ρ∈Cn×n. In both cases, the input is assumed to have entropy bounded away from zero by a quantity determined by the parameter η>0η>0η>0, since, as we prove, no polynomial query algorithm can multiplicatively approximate the entropy of distributions with arbitrarily low entropy. In addition, we provide Ω(n13γ2)Ω\left(n^{\frac{1}{3γ^2}}\right)Ω(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.
We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances, including the von Neumann entropy, quantum Rényi entropy, trace distance, and fidelity. The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case, some of which achieve exponential speedups. In particular, forN-dimensional quantum states of rankr, our proposed quantum algorithms for computing the von Neumann entropy, trace distance and fidelity within additive error ε have time complexity of Õ(r/ε2), Õ(r5/ε6) and Õ(r6.5/ε7.5), respectively. By contrast, prior quantum algorithms for the von Neumann entropy and trace distance usually have time complexity Ω(N), and the prior best one for fidelity has time complexity Õ(r12.5/ε13.5). The key idea of our quantum algorithms is to extend block-encoding from unitary operators in previous work to quantum states (i.e., density operators). It is realized by developing several convenient techniques to manipulate quantum states and extract information from them. The advantage of our techniques over the existing methods is that no restrictions on density operators are required; in sharp contrast, the previous methods usually require a lower bound on the minimal non-zero eigenvalue of density operators.
Von Neumann defined the informational entropy of a density matrix ρ by the expression S(ρ)=−tr(ρ ln ρ). [J. Von Neumann, Die Mathematischen Grundlagen der Quantummechanik (Springer-Verlag, Berlin, 1932)]. Here, starting from the definitions of Shannon entropy and of Renyi entropy of random variables, and using some (reasonable) rules of inference, two expressions are obtained for the quantum entropy of a given square (deterministic) matrix, irrespective of any probabilistic framework and/or any randomization technique. These definitions apply directly to linear operators on Hilbert spaces even when they are not of positive trace class, and they contain Von Neumann entropy as a special case. These new measures of uncertainty could provide new approaches to some problems related to structure complexity.
The notion of entropy was introduced by Clausius in order to discuss the thermal behavior of physical systems. After the work of Clausius, Boltzmann, Gibbs and others, the beginning of the exact treatment of entropy was due to von Neumann and Shannon. Their starting point was very di erent, von Neumann was motivated by quantum mechanics and Shannon founded communication theory. The entropy of a state describing a physical system is a quantity expressing the uncertainty or randomness of the system. Shannon regarded this uncertainty attached to a physical system as the amount of information carried by the system, so that the entropy of a state can be read as the information carried by the state. His idea comes from the following consideration: If a physical system has a large uncertainty and one receives information on the system by some procedure, then the so obtained information is more valuable than that received from a system having less uncertainty. It is understood in probability theory that the notion of (Shannon or measure theoretic) entropy has successful applications in a variety of subjects because it determines the asymptotic behavior of certain probabilities in the course of independent trials. First we will discuss this phenomena for nite quantum systems. By a nite quantum system we mean an algebra of matrices which is stable under taking adjoint. (In other words, a nite quantum system is a nite dimensional C*algebra.) If A is such an algebra then there is a linear functional Tr which takes the value 1 at each minimal projection. It is "tracial " in the sense that Tr ab = Tr ba (a; b 2 A) Every functional! on A is determined by a density operator D! 2 A in the form!(a) = Tr D! a (a 2 A): The entropy S(!) of a functional! is de ned by means of its density operator as S(!) = Tr (D!): This notion was introduced by von Neumann in 1927 and we term it von Neumann's entropy or shortly entropy (cf. [1]). In fact, von Neumann de ned the entropy such
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. For a matrix A and a function f, the spectral sum is the trace of f(A), equivalently the sum over eigenvalues of A of f applied to each eigenvalue. Typical examples of spectral sums are the von Neumann entropy, the trace of the inverse of A, the log-determinant, and the Schatten p-norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees in a graph.