Contracting projected entangled pair states is average-case hard

Abstract

An accurate calculation of the properties of quantum many-body systems is one of the most important yet intricate challenges of modern physics and computer science. In recent years, the tensor network ansatz has established itself as one of the most promising approaches enabling striking efficiency of simulating static properties of one-dimensional systems and abounding numerical applications in condensed matter theory. In higher dimensions, however, a connection to the field of computational complexity theory has shown that the accurate normalization of the two-dimensional tensor networks called projected entangled pair states (PEPS) is #P-complete. Therefore, an efficient algorithm for PEPS contraction would allow to solve exceedingly difficult combinatorial counting problems, which is considered highly unlikely. Due to the importance of understanding two- and three-dimensional systems the question currently remains: Are the known constructions typical of states relevant for quantum many-body systems? In this work, we show that an accurate evaluation of normalization or expectation values of PEPS is as hard to compute for typical instances as for special configurations of highest computational hardness. We discuss the structural property of average-case hardness in relation to the current research on efficient algorithms attempting tensor network contraction, hinting at a wealth of possible further insights into the average-case hardness of important problems in quantum many-body theory.

References in corpus (61)

• The density-matrix renormalization group in the age of matrix product states
• The density-matrix renormalization group
• Area laws for the entanglement entropy - a review
• Quark Gluon Plasma an Color Glass Condensate at RHIC? The perspective from the BRAHMS experiment
• 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
• Measurement-based quantum computation with cluster states
• Continuous-time Monte Carlo methods for quantum impurity models
• Entanglement spectrum of a topological phase in one dimension
• Spin Liquid Ground State of the $S=1/2$ Kagome Heisenberg Model
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Unbounded growth of entanglement in models of many-body localization
• Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gas
• Tensor-Entanglement-Filtering Renormalization Approach and Symmetry Protected Topological Order
• Strange Quark Matter and Compact Stars
• Matrix product states represent ground states faithfully
• Functional renormalization group approach to correlated fermion systems
• The European Quantum Technologies Roadmap
• Many-body localization: an introduction and selected topics
• Tensor renormalization group approach to 2D classical lattice models
• Criticality, the area law, and the computational power of PEPS
• Classical simulation of quantum many-body systems with a tree tensor network
• Open XXZ spin chain: Nonequilibrium steady state and strict bound on ballistic transport
• Quantum dynamics of a single, mobile spin impurity
• The iTEBD algorithm beyond unitary evolution
• Simulating quantum computation by contracting tensor networks
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Simulation of two dimensional quantum systems on an infinite lattice revisited: corner transfer matrix for tensor contraction
• Gapless spin-liquid ground state in the $S=1/2$ kagome antiferromagnet
• Simulation of strongly correlated fermions in two spatial dimensions with fermionic Projected Entangled-Pair States
• Strongly correlated fermions after a quantum quench
• The computational complexity of PEPS
• Expansion dynamics of interacting bosons in homogeneous lattices in one and two dimensions
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Real-time dynamics in spin-1/2 chains with adaptive time-dependent DMRG
• Density Matrix Renormalization Group Method for 2D Classical Models
• Novel schemes for measurement-based quantum computation
• Second Renormalization of Tensor-Network States
• Stripes in the two-dimensional t-J model with infinite projected entangled-pair states
• Finite temperature dynamical DMRG and the Drude weight of spin-1/2 chains
• Corner Transfer Matrix Algorithm for Classical Renormalization Group
• Gradient methods for variational optimization of projected entangled-pair states
• Renormalization of tensor-network states
• Magnetization of SrCu2(BO3)2 in ultrahigh magnetic fields up to 118 T
• Loop optimization for tensor network renormalization
• Automorphic Equivalence within Gapped Phases of Quantum Lattice Systems
• Faster Methods for Contracting Infinite 2D Tensor Networks
• Unifying Projected Entangled Pair States contractions
• Exploring corner transfer matrices and corner tensors for the classical simulation of quantum lattice systems
• Spin-S Kagome quantum antiferromagnets in a field with tensor networks
• Algorithms for tensor network renormalization
• Numerical Renormalization Group at Criticality
• A tensor network annealing algorithm for two-dimensional thermal states
• Non-Abelian chiral spin liquid in a quantum antiferromagnet revealed by an iPEPS study
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Chiral topological spin liquids with projected entangled pair states
• Efficient representation of fully many-body localized systems using tensor networks
• A tensor network study of the complete ground state phase diagram of the spin-1 bilinear-biquadratic Heisenberg model on the square lattice
• The spin-1/2 Kagome XXZ model in a field: competition between lattice nematic and solid orders
• Approximating local observables on projected entangled pair states
• How local is the information in MPS/PEPS tensor networks?

Cited by in corpus (46)

• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Simulation methods for open quantum many-body systems
• Computational advantage of quantum random sampling
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Neural tensor contractions and the expressive power of deep neural quantum states
• Lattice Quantum Electrodynamics in (3+1)-dimensions at finite density with Tensor Networks
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Efficient Tensor Network ansatz for high-dimensional quantum many-body problems
• Two-dimensional quantum-link lattice Quantum Electrodynamics at finite density
• Probabilistic Nonunitary Gate in Imaginary Time Evolution
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Quantum time crystals with programmable disorder in higher dimensions
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Quantum many-body systems in thermal equilibrium
• Non-equilibrium phase transitions in $(1+1)$-dimensional quantum cellular automata with controllable quantum correlations
• Investigating Topological Order using Recurrent Neural Networks
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Complexity phase diagram for interacting and long-range bosonic Hamiltonians
• Entanglement estimation in tensor network states via sampling
• An introduction to infinite projected entangled-pair state methods for variational ground state simulations using automatic differentiation
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Optimization at the boundary of the tensor network variety
• Preparation and verification of tensor network states
• The minimal canonical form of a tensor network
• Random insights into the complexity of two-dimensional tensor network calculations
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions
• Dynamics of disordered quantum systems with two- and three-dimensional tensor networks
• Capturing long-range memory structures with tree-geometry process tensors
• Two-dimensional local Hamiltonian problem with area laws is QMA-complete
• Dual-isometric Projected Entangled Pair States
• Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
• The resource theory of tensor networks
• A generic quantum Wielandt's inequality
• Quantum subspace expansion approach for simulating dynamical response functions of Kitaev spin liquids
• Time-dependent variational principle for open quantum systems with artificial neural networks
• Unifying non-Markovian characterisation with an efficient and self-consistent framework
• Finite temperature tensor network algorithm for frustrated two-dimensional quantum materials
• Two Dimensional Isometric Tensor Networks on an Infinite Strip
• Positive bias makes tensor-network contraction tractable
• Tensor Network Efficiently Representing Schmidt Decomposition of Quantum Many-Body States
• Variational optimization of projected entangled-pair states on the triangular lattice
• Evaluating Sample-Based Krylov Quantum Diagonalization for Heisenberg Models with Applications to Materials Science
• A quantum eigenvalue solver based on tensor networks
• Using matrix-product states for time-series machine learning
• Tensorization of neural networks for improved privacy and interpretability
• Locally accurate tensor networks for thermal states and time evolution