arXiv:1709.07828

Markovian Matrix Product Density Operators : Efficient computation of global entropy

Isaac H. Kim

Published Sep 22, 2017• 8 citations

Abstract

We introduce the Markovian matrix product density operator, which is a special subclass of the matrix product density operator. We show that the von Neumann entropy of such ansatz can be computed efficiently on a classical computer. This is possible because one can efficiently certify that the global state forms an approximate quantum Markov chain by verifying a set of inequalities. Each of these inequalities can be verified in time that scales polynomially with the bond dimension and the local Hilbert space dimension. The total number of inequalities scale linearly with the system size. We use this fact to study the complexity of computing the minimum free energy of local Hamiltonians at finite temperature. To this end, we introduce the free energy problem as a generalization of the local Hamiltonian problem, and study its complexity for a class of Hamiltonians that describe quantum spin chains. The corresponding free energy problem at finite temperature is in NP if the Gibbs state of such Hamiltonian forms an approximate quantum Markov chain with an error that decays exponentially with the width of the conditioning subsystem.

DOI: 10.48550/arxiv.1709.07828

Related papers

Computing energy density in one dimension

Yichen Huang

We study the problem of computing energy density in one-dimensional quantum systems. We show that the ground-state energy per site or per bond can be computed in time (i) independent of the system size and subexponential in the desired precision if the ground state satisfies area laws for the Renyi entanglement entropy (this is the first rigorous formulation of the folklore that area laws imply efficient matrix-product-state algorithms); (ii) independent of the system size and polynomial in the desired precision if the system is gapped. As a by-product, we prove that in the presence of area laws (or even an energy gap) the ground state can be approximated by a positive semidefinite matrix product operator of bond dimension independent of the system size and subpolynomial in the desired precision of local properties.

arXiv:1505.00772May 4, 201514 citations

A new product entropy

Jiaju Zhang, Zhuo-Yu Xian, René Meyer +2 more

We propose a new product entropy, defined as the Rényi (or von Neumann) entropy of a normalized product operator constructed from two density matrices. We establish a duality showing that the SVD entanglement entropy of a subsystem for two pure states is exactly equivalent to the product entropy of the complementary subsystem. This connection provides both a transparent physical interpretation in terms of the spectral diversity of the subsystem state product and a computationally efficient route that bypasses the reduced transition matrix. For low-lying eigenstates, we derive analytical expressions for the subsystem product entropy between the ground state and primary excitations in two-dimensional conformal field theories, explicitly verified against the critical Ising chain. In quantum quench dynamics, the quasiparticle picture yields time evolution in the scaling limit: following a global quench, the subsystem product entropy exhibits distinct sequences of thermalization and revivals, whereas under a local operator quench, it develops characteristic plateaus whose constant values are determined by the inserted operator. Extensive numerical calculations on the critical Ising chain confirm the analytical predictions with excellent accuracy.

hep-thCross-listedarXiv:2609.13994Sep 15, 20260 citations

Computational Difficulty of Global Variations in the Density Matrix Renormalization Group

Jens Eisert

The density matrix renormalization group approach is arguably the most successful method to numerically find ground states of quantum spin chains. It amounts to iteratively locally optimizing matrix-product states, aiming at better and better approximating the true ground state. To date, both a proof of convergence to the globally best approximation and an assessment of its complexity are lacking. Here we establish a result on the computational complexity of an approximation with matrix-product states: The surprising result is that when one globally optimizes over several sites of local Hamiltonians, avoiding local optima, one encounters in the worst case a computationally difficult NP-hard problem (hard even in approximation). The proof exploits a novel way of relating it to binary quadratic programming. We discuss intriguing ramifications on the difficulty of describing quantum many-body systems.

arXiv:quant-ph/0609051Physical Review LettersDec 28, 200636 citations

Entropy Scaling Law and the Quantum Marginal Problem

Isaac H. Kim

Quantum many-body states that frequently appear in physics often obey an entropy scaling law, meaning that an entanglement entropy of a subsystem can be expressed as a sum of terms that scale linearly with its volume and area, plus a correction term that is independent of its size.We conjecture that these states have an efficient dual description in terms of a set of marginal density matrices on bounded regions, obeying the same entropy scaling law locally.We prove a restricted version of this conjecture for translationally invariant systems in two spatial dimensions.Specifically, we prove that a translationally invariant marginal obeying three nonlinear constraints-all of which follow from the entropy scaling law straightforwardlymust be consistent with some global state on an infinite lattice.Moreover, we derive a closed-form expression for the maximum-entropy density compatible with those marginals, deriving a variational upper bound on the thermodynamic free energy.The main assumptions of our construction are satisfied exactly by solvable models of topological order and approximately by finite-temperature Gibbs states of certain quantum spin Hamiltonians.

arXiv:2010.07424Physical Review XMay 20, 202112 citations

Markov Entropy Decomposition: A Variational Dual for Quantum Belief Propagation

David Poulin, Matthew B. Hastings

We present a lower bound for the free energy of a quantum many-body system at finite temperature. This lower bound is expressed as a convex optimization problem with linear constraints, and is derived using strong subadditivity of von Neumann entropy and a relaxation of the consistency condition of local density operators. The dual to this minimization problem leads to a set of quantum belief propagation equations, thus providing a firm theoretical foundation to that approach. The minimization problem is numerically tractable, and we find good agreement with quantum Monte Carlo calculations for spin-1/2 Heisenberg antiferromagnet in two dimensions. This lower bound complements other variational upper bounds. We discuss applications to Hamiltonian complexity theory and give a generalization of the structure theorem of [P. Hayden et al., Commun. Math. Phys. 246, 359 (2004).] to trees in an appendix.

arXiv:1012.2050Physical Review LettersFeb 24, 201156 citations

Matrix product simulations of non-equilibrium steady states of quantum spin chains

Tomaž Prosen

Time-dependent density matrix renormalization group method with a matrix product ansatz is employed for explicit computation of non-equilibrium steady state density operators of several integrable and non-integrable quantum spin chains, which are driven far from equilibrium by means of Markovian couplings to external baths at the two ends. It is argued that even though the time-evolution can not be simulated efficiently due to fast entanglement growth, the steady states in and out of equilibrium can be typically accurately approximated, so that chains of length of the order n ~ 100 are accessible. Our results are demonstrated by performing explicit simulations of steady states and calculations of energy/spin densities/currents in several problems of heat and spin transport in quantum spin chains. Previously conjectured relation between quantum chaos and normal transport is re-confirmed with high acurracy on much larger systems.

Jan 1, 2008216 citations