Matrix product operators and states: NP-hardness and undecidability

Abstract

Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.

7 pages, 2 figures; published version with improved presentation

References in corpus (5)

• The density-matrix renormalization group in the age of matrix product states
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Minimally Entangled Typical Thermal State Algorithms
• Spectral functions in one-dimensional quantum systems at T>0

Cited by in corpus (22)

• Variational Matrix Product Operators for the Steady State of Dissipative Quantum Systems
• Quantum dynamics of thermalizing systems
• Tensor Networks for Lattice Gauge Theories beyond one dimension: a Roadmap
• Neural-network quantum states for a two-leg Bose-Hubbard ladder under magnetic flux
• Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor
• Exact Hidden Markovian Dynamics in Quantum Circuits
• Dynamical heterogeneity and large deviations in the open quantum East glass model from tensor networks
• Universal Spreading of Conditional Mutual Information in Noisy Random Circuits
• Undecidability in Physics: a Review
• Many bounded versions of undecidable problems are NP-hard
• Large-scale stochastic simulation of open quantum systems
• Can quantum gravity be both consistent and complete?
• Meson thermalization with a hot medium in the open Schwinger model
• PAC-learning of free-fermionic states is NP-hard
• A Riemannian Approach to the Lindbladian Dynamics of a Locally Purified Tensor Network
• Constructing k-local parent Lindbladians for matrix product density operators
• Parent Lindbladians for Matrix Product Density Operators
• Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations
• New perspectives on quantum kernels through the lens of entangled tensor kernels
• Efficient tomography of microwave photonic cluster states
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Undecidability of the spectral gap in rotationally symmetric Hamiltonians