Markovian Matrix Product Density Operators : Efficient computation of global entropy

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.

arXiv comment16 pages, no figures, references updated

References in corpus (10)

• An Area Law for One Dimensional Quantum Systems
• Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
• Quantum conditional mutual information and approximate Markov chains
• The power of quantum systems on a line
• Exponential Decay of Correlations Implies Area Law
• Renyi generalizations of the conditional quantum mutual information
• Markov entropy decomposition: a variational dual for quantum belief propagation
• Almost all quantum channels are equidistant
• One-dimensional quantum systems at finite temperatures can be simulated efficiently on classical computers
• Thermal States as Convex Combinations of Matrix Product States

Cited by in corpus (6)

• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• Matrix product states and the decay of quantum conditional mutual information
• Oracle complexity classes and local measurements on physical Hamiltonians
• Entropy scaling law and the quantum marginal problem: simplification and generalization
• Robust decompositions of quantum states