Given a large real symmetric, positive semidefinite matrix, the goal of this paper is to show how a numerical approximation of the von Neumann entropy of the matrix can be computed in an efficient way, without relying on matrix diagonalization. An application from quantum optics dealing with the entanglement between photons illustrates the new algorithm.
Given a large real symmetric, positive semidefinite matrix, the goal of this paper is to show how a numerical approximation of the von Neumann entropy of the matrix can be computed in an efficient way, without relying on matrix diagonalization. An application from quantum optics dealing with the entanglement between photons illustrates the new algorithm.
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.
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.
A real symmetric matrix is separable if it can be written as a sum of Kronecker products of positive semidefinite matrices. This talk concerns how to check if a matrix is separable or not. We propose a numerical algorithm, based on Lasserre type semidefinite relaxations, for solving the question. To check the separability of a matrix, we construct a hierarchy of semidefinite relaxations. If it is not separable, we can get a mathematical certificate for that; if it is, we can get a decomposition for the separability. This is a joint work with Xinzhen Zhang.
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.
Abstract Many quantum information measures can be written as an optimization of the quantum relative entropy between sets of states. For example, the relative entropy of entanglement of a state is the minimum relative entropy to the set of separable states. The various capacities of quantum channels can also be written in this way. We propose a unified framework to numerically compute these quantities using off-the-shelf semidefinite programming solvers, exploiting the approximation method proposed in Fawzi, Saunderson and Parrilo (2017 arXiv: 1705.00812). As a notable application, this method allows us to provide numerical counterexamples for a proposed lower bound on the quantum conditional mutual information in terms of the relative entropy of recovery.