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.

arXiv comment7 pages, 2 figures; published version with improved presentation

References in corpus (17)

• The density-matrix renormalization group in the age of matrix product states
• Area laws for the entanglement entropy - a review
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Efficient simulation of one-dimensional quantum many-body systems
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
• A class of ansatz wave functions for 1D spin systems and their relation to DMRG
• The computational complexity of PEPS
• Minimally Entangled Typical Thermal State Algorithms
• Algebraic versus exponential decoherence in dissipative many-particle systems
• Spectral functions in one-dimensional quantum systems at T>0
• Lifts of convex sets and cone factorizations
• All reversible dynamics in maximally non-local theories are trivial
• Purifications of multipartite states: limitations and constructive methods
• Quantum measurement occurrence is undecidable
• Undecidability in Tensor Network States

Cited by in corpus (62)

• Lattice gauge theories simulations in the quantum information era
• Undecidability of the Spectral Gap (short version)
• Simulation methods for open quantum many-body systems
• Variational Matrix Product Operators for the Steady State of Dissipative Quantum Systems
• A positive tensor network approach for simulating open quantum many-body systems
• Review on novel methods for lattice gauge theories
• Quantum Machine Learning for Chemistry and Physics
• A Matrix-Product-Operator Approach to the Nonequilibrium Steady State of Driven-Dissipative Quantum Arrays
• Quantum dynamics of thermalizing systems
• A tensor network annealing algorithm for two-dimensional thermal states
• One-dimensional many-body entangled open quantum systems with tensor network methods
• Variational Quantum Algorithm for Non-equilibrium Steady States
• Tensor Network Contractions for #SAT
• Fundamental limitations in the purifications of tensor networks
• Undecidability of the Spectral Gap in One Dimension
• Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians
• Matrix Product States for Quantum Stochastic Modelling
• Simulating the out-of-equilibrium dynamics of local observables by trading entanglement for mixture
• Computable Rényi mutual information: Area laws and correlations
• Quantum learning of classical stochastic processes: The Completely-Positive Realization Problem
• Tensor Networks for Lattice Gauge Theories beyond one dimension: a Roadmap
• Simulating topological tensor networks with Majorana qubits
• Renormalising entanglement distillation
• Extracting work from correlated many-body quantum systems
• Matrix Product States with Backflow correlations
• Entanglement of formation of mixed many-body quantum states via Tree Tensor Operators
• Neural-network quantum states for a two-leg Bose-Hubbard ladder under magnetic flux
• Undecidability of the Spectral Gap (full version)
• Approximating local properties by tensor network states with constant bond dimension
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
• Computational complexity of non-equilibrium steady states of quantum spin chains
• Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor
• Exact Hidden Markovian Dynamics in Quantum Circuits
• Matrix Product Density Operators: when do they have a local parent Hamiltonian?
• Measures of distinguishability between stochastic processes
• Dynamical heterogeneity and large deviations in the open quantum East glass model from tensor networks
• Halos and undecidability of tensor stable positive maps
• Undecidability in Physics: a Review
• Universal Spreading of Conditional Mutual Information in Noisy Random Circuits
• Petz recovery versus matrix reconstruction
• Many bounded versions of undecidable problems are NP-hard
• A bipartite separable ball and its applications
• Entanglement and thermalization in open fermion systems
• Quantum Information Theory and Free Semialgebraic Geometry: One Wonderland Through Two Looking Glasses
• 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
• Properties of thermal quantum states: locality of temperature, decay of correlations, and more
• Tensor network non-zero testing
• Optimal bounds on the positivity of a matrix from a few moments
• Quantum Tensor Networks, Stochastic Processes, and Weighted Automata
• Dynamics of two-dimensional open quantum lattice models with tensor networks
• PAC-learning of free-fermionic states is NP-hard
• Polynomial decompositions with invariance and positivity inspired by tensors
• A Riemannian Approach to the Lindbladian Dynamics of a Locally Purified Tensor Network
• Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations
• Constructing k-local parent Lindbladians for matrix product density operators
• Parent Lindbladians for Matrix Product Density Operators
• New perspectives on quantum kernels through the lens of entangled tensor kernels
• Undecidability of the spectral gap in rotationally symmetric Hamiltonians
• Efficient tomography of microwave photonic cluster states
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings