2017/09/22 by Isaac H. Kim, Kim, Isaac H. · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #FOS: Physical sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum many-body systems #quant-ph
paper · pdf · doi:10.48550/arxiv.1709.07828
16 pages, no figures, references updated
openalex publication_date 2017/09/22 · arxiv created 2017/09/27 · arxiv updated 2017/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.