The computational complexity of PEPS

Abstract

We determine the computational power of preparing Projected Entangled Pair States (PEPS), as well as the complexity of classically simulating them, and generally the complexity of contracting tensor networks. While creating PEPS allows to solve PP problems, the latter two tasks are both proven to be #P-complete. We further show how PEPS can be used to approximate ground states of gapped Hamiltonians, and that creating them is easier than creating arbitrary PEPS. The main tool for our proofs is a duality between PEPS and postselection which allows to use existing results from quantum compexity.

5 pages, 1 figure. Published version, plus a few extras

References in corpus (2)

• Criticality, the area law, and the computational power of PEPS
• Valence Bond Solids for Quantum Computation

Cited by in corpus (230)

• Area laws for the entanglement entropy - a review
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Tensor-Entanglement-Filtering Renormalization Approach and Symmetry Protected Topological Order
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Towards Practical Quantum Variational Algorithms
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Tensor networks for complex quantum systems
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Renormalization and tensor product states in spin chains and lattices
• Efficient Representation of Quantum Many-body States with Deep Neural Networks
• Orbital Optimization in the Density Matrix Renormalization Group, with applications to polyenes and β-carotene
• PEPS as ground states: degeneracy and topology
• Novel schemes for measurement-based quantum computation
• Unsupervised Generative Modeling Using Matrix Product States
• Simulation methods for open quantum many-body systems
• Neural-Network Quantum States, String-Bond States, and Chiral Topological States
• Real- and imaginary-time evolution with compressed quantum circuits
• A positive tensor network approach for simulating open quantum many-body systems
• Review on novel methods for lattice gauge theories
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Lecture Notes of Tensor Network Contractions
• Computational advantage of quantum random sampling
• Entanglement Spectrum, Critical Exponents and Order Parameters in Quantum Spin Chains
• Advances on Tensor Network Theory: Symmetries, Fermions, Entanglement, and Holography
• Finite automata for caching in matrix product algorithms
• Quantum Hamiltonian Complexity
• The Tensor Networks Anthology: Simulation techniques for many-body quantum lattice systems
• Tensor Network Algorithms: a Route Map
• Strings, Projected Entangled Pair States, and variational Monte Carlo methods
• Unifying Projected Entangled Pair States contractions
• Multi-scale Entanglement Renormalization Ansatz in Two Dimensions: Quantum Ising Model
• Quantum Circuits assisted by LOCC: Transformations and Phases of Matter
• Parallel Quantum Simulation of Large Systems on Small Quantum Computers
• Beyond-classical computation in quantum simulation
• Diagonalizing transfer matrices and matrix product operators: a medley of exact and computational methods
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Excitations and the tangent space of projected entangled-pair states
• Quantum Neural Network States: A Brief Review of Methods and Applications
• Neural tensor contractions and the expressive power of deep neural quantum states
• Slow quantum thermalization and many-body revivals from mixed phase space
• Holographic quantum algorithms for simulating correlated spin systems
• Scaling of the entanglement spectrum near quantum phase transitions
• Tensor-Network Simulations of the Surface Code under Realistic Noise
• A tensor network annealing algorithm for two-dimensional thermal states
• Matrix product operators and states: NP-hardness and undecidability
• Tensor network techniques for the computation of dynamical observables in 1D quantum spin systems
• General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Gapped Two-body Hamiltonian whose Unique Ground State is Universal for One-way Quantum Computation
• A canonical form for Projected Entangled Pair States and applications
• Twisted Injectivity in PEPS and the Classification of Quantum Phases
• Computational Complexity in Electronic Structure
• Efficient Representation of Topologically Ordered States with Restricted Boltzmann Machines
• Two-dimensional Rydberg gases and the quantum hard squares model
• Encoding Hypergraphs into Quantum States
• Completeness of the classical 2D Ising model and universal quantum computation
• Efficient Tensor Network ansatz for high-dimensional quantum many-body problems
• Unifying variational methods for simulating quantum many-body systems
• Supervised Learning with Projected Entangled Pair States
• Computations in Quantum Tensor Networks
• Isometric Tensor Network representation of string-net liquids
• Sequentially generated states for the study of two dimensional systems
• Contracting projected entangled pair states is average-case hard
• Decoding algorithms for surface codes
• Tensor product representation of topological ordered phase: necessary symmetry conditions
• Sequential generation of projected entangled-pair states
• Efficient simulation of Grassmann Tensor Product States
• Preparing projected entangled pair states on a quantum computer
• Tropical Tensor Network for Ground States of Spin Glasses
• Validating Quantum-Classical Programming Models with Tensor Network Simulations
• Probabilistic Nonunitary Gate in Imaginary Time Evolution
• Tensor network states in time-bin quantum optics
• Persistence of the gapless spin liquid in the breathing kagome Heisenberg antiferromagnet
• Hybrid convolutional neural network and PEPS wave functions for quantum many-particle states
• Quantum time crystals with programmable disorder in higher dimensions
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Assessing the accuracy of projected entangled-pair states on infinite lattices
• Linear-time general decoding algorithm for the surface code
• Existence of a Spectral Gap in the Affleck-Kennedy-Lieb-Tasaki Model on the Hexagonal Lattice
• Anyonic entanglement renormalization
• Direct sampling of projected entangled-pair states
• Entanglement Renormalization for Weakly Interacting Fields
• From Tensor Network Quantum States to Tensorial Recurrent Neural Networks
• Efficient Simulation of Dynamics in Two-Dimensional Quantum Spin Systems with Isometric Tensor Networks
• Quantum Computation Beyond the Circuit Model
• Practical learning method for multi-scale entangled states
• Non-equilibrium phase transitions in $(1+1)$-dimensional quantum cellular automata with controllable quantum correlations
• Quantum many-body systems in thermal equilibrium
• Gauging tensor networks with belief propagation
• Tensor Networks contraction and the Belief Propagation algorithm
• Infinite Projected Entangled-Pair State algorithm for ruby and triangle-honeycomb lattices
• Variational methods for contracting projected entangled-pair states
• Concatenated tensor network states
• Efficient Machine Learning Representations of Surface Code with Boundaries, Defects, Domain Walls and Twists
• Charge and statistics of lattice quasiholes from density measurements: a Tree Tensor Network study
• Measuring the Loschmidt amplitude for finite-energy properties of the Fermi-Hubbard model on an ion-trap quantum computer
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• Renormalization Group Circuits for Weakly Interacting Continuum Field Theories
• Holographic quantum simulation of entanglement renormalization circuits
• Finding the ground state of a lattice gauge theory with fermionic tensor networks: a $2+1d$ ${\mathbb{Z}}_2$ demonstration
• Preparing Valence-Bond-Solid states on noisy intermediate-scale quantum computers
• Three-dimensional isometric tensor networks
• Entangled and sequential quantum protocols with dephasing
• Symmetry-protected dissipative preparation of matrix product states
• Fixed-Point Quantum Circuits for Quantum Field Theories
• Optimal sampling of dynamical large deviations in two dimensions via tensor networks
• Enhancing Detection of Topological Order by Local Error Correction
• Plaquette Renormalization Scheme for Tensor Network States
• Entanglement and precession in two-dimensional dynamical quantum phase transitions
• A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Complexity phase diagram for interacting and long-range bosonic Hamiltonians
• Encoding graphs into quantum states: an axiomatic approach
• Tensor Networks for Lattice Gauge Theories beyond one dimension: a Roadmap
• Approximating local observables on projected entangled pair states
• Tensor networks for quantum computing
• Entanglement estimation in tensor network states via sampling
• Importance of the spectral gap in estimating ground-state energies
• An introduction to infinite projected entangled-pair state methods for variational ground state simulations using automatic differentiation
• Finite-temperature symmetric tensor network for spin-1/2 Heisenberg antiferromagnets on the square lattice
• Language Design as Information Renormalization
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Mathematical open problems in Projected Entangled Pair States
• Fermionic algebraic quantum spin liquid in an octa-kagome frustrated antiferromagnet
• Efficient evaluation of high-order moments and cumulants in tensor network states
• Ab initio optimization principle for the ground states of translationally invariant strongly correlated quantum lattice models
• Optimization at the boundary of the tensor network variety
• Block belief propagation algorithm for two-dimensional tensor networks
• Quantum State Tomography with Locally Purified Density Operators and Local Measurements
• Relationship among locally maximally entanglable states, W states and hypergraph states under local unitary transformations
• Density of Yang-Lee zeros in the thermodynamic limit from tensor network methods
• Approximating the ground state of gapped quantum spin systems
• Locally Purified Density Operators for Symmetry-Protected Topological Phases in Mixed States
• Preparation and verification of tensor network states
• Many body physics from a quantum information perspective
• On exploring the potential of quantum auto-encoder for learning quantum systems
• The minimal canonical form of a tensor network
• A brief introduction to multipartite entanglement
• Isometric tensor network representations of two-dimensional thermal states
• Certifying ground-state properties of quantum many-body systems
• From Tree Tensor Network to Multiscale Entanglement Renormalization Ansatz
• An algorithmic proof for the completeness of two-dimensional Ising model
• Collective Monte Carlo updates through tensor network renormalization
• Multipartite Entanglement and Hypergraph states of three qubits
• Sharp complexity phase transitions generated by entanglement
• Computational complexity of non-equilibrium steady states of quantum spin chains
• Quantum Merlin Arthur with Exponentially Small Gap
• Entanglement Hamiltonian of the quantum Néel state
• Tensor network methods with graph enhancement
• Noise-resilient preparation of quantum many-body ground states
• How local is the information in MPS/PEPS tensor networks?
• Simulating 2D topological quantum phase transitions on a digital quantum computer
• Gauged Gaussian PEPS -- A High Dimensional Tensor Network Formulation for Lattice Gauge Theories
• Locally purified density operators for noisy quantum circuits
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions
• AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states
• Entropy scaling law and the quantum marginal problem
• Random insights into the complexity of two-dimensional tensor network calculations
• Sign problem in tensor network contraction
• Diagrammatics for SU(2) invariant matrix product states
• Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder
• Dynamics of disordered quantum systems with two- and three-dimensional tensor networks
• Matrix product state approximations to quantum states of low energy variance
• Ising Meson Spectroscopy on a Noisy Digital Quantum Simulator
• Fermionic Isometric Tensor Network States in Two Dimensions
• Two-dimensional local Hamiltonian problem with area laws is QMA-complete
• Loop Series Expansions for Tensor Networks
• Dual-isometric Projected Entangled Pair States
• Shortcut Matrix Product States and its applications
• Combination of Tensor Network States and Green's function Monte Carlo
• Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
• Generation of photonic tensor network states with Circuit QED
• The resource theory of tensor networks
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
• On Stability of Tensor Networks and Canonical Forms
• Tensor networks and efficient descriptions of classical data
• On efficiently solvable cases of Quantum k-SAT
• Quantum Phase Transitions between Symmetry-Enriched Fracton Phases
• Variational Neural and Tensor Network Approximations of Thermal States
• Disentanglement Approach to Quantum Spin Ground States: Field Theory and Stochastic Simulation
• A generic quantum Wielandt's inequality
• Entropic measure and hypergraph states
• A construction of Combinatorial NLTS
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• Two Dimensional Isometric Tensor Networks on an Infinite Strip
• Importance Sampling Scheme for the Stochastic Simulation of Quantum Spin Dynamics
• Tensor network non-zero testing
• Survey on Computational Applications of Tensor Network Simulations
• Variational Microcanonical Estimator
• Time-dependent variational principle for open quantum systems with artificial neural networks
• Finite temperature tensor network algorithm for frustrated two-dimensional quantum materials
• Efficient simulation of many-body localized systems
• Time Evolution and Deterministic Optimisation of Correlator Product States
• Bounds on Autonomous Quantum Error Correction
• Simulation of Quantum Many-Body Systems on Amazon Cloud
• Tensor networks for $p$-spin models
• Stacked tree construction for free-fermion projected entangled pair states
• Positive bias makes tensor-network contraction tractable
• Scalable projected entangled-pair state representation of random quantum circuit states
• On Computational Complexity of Unitary and State Design Properties
• Studies on the Role of Entanglement in Mixed-state Quantum Computation
• A Practical Introduction to Tensor Network Renormalization with TNRKit.jl
• An Extensible Quantum Network Simulator Built on ns-3: Q2NS Design and Evaluation
• A recipe for local simulation of strongly-correlated fermionic matter on quantum computers: the 2D Fermi-Hubbard model
• Efficient certification and simulation of local quantum many-body Hamiltonians
• PAC-learning of free-fermionic states is NP-hard
• Realization of Two-dimensional Discrete Time Crystals with Anisotropic Heisenberg Coupling
• Learning out-of-time-ordered correlators with classical kernel methods
• Efficient 2D Tensor Network Simulation of Quantum Systems
• SpinGlassPEPS.jl: Tensor-network package for Ising-like optimization on quasi-two-dimensional graphs
• A Generalised Haldane Map from the Matrix Product State Path Integral to the Critical Theory of the $J_1$-$J_2$ Chain
• Pseudoentanglement from tensor networks
• Variational optimization of projected entangled-pair states on the triangular lattice
• Projected Entangled Pair States for Lattice Gauge Theories with Dynamical Fermions
• Tensor Network Efficiently Representing Schmidt Decomposition of Quantum Many-Body States
• Effects of Topological Boundary Conditions on Bell Nonlocality
• Single-layer framework of variational tensor network states
• Neuralized Fermionic Tensor Networks for Quantum Many-Body Systems
• Algorithmic Aspects of Gauged Gaussian Fermionic PEPS: Gauge Fixing and Translation Invariance
• Topological crystals and soliton lattices in a Gross-Neveu model with Hilbert-space fragmentation
• Trajectory-Resolved Weiss Fields for Quantum Spin Dynamics
• A quantum eigenvalue solver based on tensor networks
• Group Convolutional Neural Network for the Low-Energy Spectrum in the Quantum Dimer Model
• Using matrix-product states for time-series machine learning
• Superselection-Resolved Entanglement in Lattice Gauge Theories: A Tensor Network Approach
• On traces of tensor representations of diagrams
• Tensor network states for the description of quantum many-body systems
• Locally accurate tensor networks for thermal states and time evolution
• Skeleton of isometric Tensor Network States for Abelian String-Net Models
• Tensorization of neural networks for improved privacy and interpretability