  Thevon 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.
