Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computational complexity of PEPS zero testing

Giuseppe Scarpa, András Molnár, Yimin Ge, Juan José García‐Ripoll, Norbert Schuch, David Pérez-Garcı́a, S. Iblisdir

Published Feb 22, 2018• 7 citations
OpenAlex

Abstract

Projected entangled pair states aim at describing lattice systems in two spatial dimensions that obey an area law. They are specified by associating a tensor with each site, and they are generated by patching these tensors. We consider the problem of determining whether the state resulting from this patching is null, and prove it to be NP-hard; the PEPS used to prove this claim have a boundary and are homogeneous in their bulk. A variation of this problem is next shown to be undecidable. These results have various implications: they question the possibility of a 'fundamental theorem' for PEPS; there are PEPS for which the presence of a symmetry is undecidable; there exist parent hamiltonians of PEPS for which the existence of a gap above the ground state is undecidable. En passant, we identify a family of classical Hamiltonians, with nearest neighbour interactions, and translationally invariant in their bulk, for which the commuting 2-local Hamiltonian problem is NP-complete.

Related papers

PEPS as unique ground states of local Hamiltonians

David Pérez-Garcı́a, Frank Verstraete, J. I. Cirac +1 more

In this paper we consider projected entangled pair states (PEPS) on arbitrary lattices. We construct local parent Hamiltonians for each PEPS and isolate a condition under which the state is the unique ground state of the Hamiltonian. This condition, verified by generic PEPS and examples like the AKLT model, is an injective relation between the boundary and the bulk of any local region. While it implies the existence of an energy gap in the 1D case we will show that in certain cases (e.g., on a 2D hexagonal lattice) the parent Hamiltonian can be gapless with a critical ground state. To show this we invoke a mapping between classical and quantum models and prove that in these cases the injectivity relation between boundary and bulk solely depends on the lattice geometry.

arXiv:0707.2260•Jul 16, 2007•1 citation

Peps as unique ground states of local hamiltonians

David Pérez-Garcı́a, Frank Verstraete, Michael M. Wolf +1 more

In this paper we consider projected entangled pair states (PEPS) on arbitrary lattices. We construct local parent Hamiltonians for each PEPS and isolate a condition under which the state is the unique ground state of the Hamiltonian. This condition, verified by generic PEPS and examples like the AKLT model, is an injective relation between the boundary and the bulk of any local region. While it implies the existence of an energy gap in the 1D case we will show that in certain cases (e.g., on a 2D hexagonal lattice) the parent Hamiltonian can be gapless with a critical ground state. To show this we invoke a mapping between classical and quantum models and prove that in these cases the injectivity relation between boundary and bulk solely depends on the lattice geometry.

Quantum Information and Computation•Jul 1, 2008•83 citations

Computational complexity of injective projected entangled pair states

Dylan Harley, Freek Witteveen, Daniel Malz

Projected entangled pair states (PEPS) constitute a variational family of quantum states with area-law entanglement. PEPS are particularly relevant and successful for studying ground states of spatially local Hamiltonians. However, computing local expectation values in these states is known to be \postBQP-hard. Injective PEPS, where all constituent tensors fulfil an injectivity constraint, are generally believed to be better behaved, because they are unique ground states of spatially local Hamiltonians. In this work, we therefore examine how the computational hardness of contraction depends on the injectivity. We establish that below a constant positive injectivity threshold, evaluating local observables remains \postBQP-complete, while above a different constant nontrivial threshold there exists an efficient classical algorithm for the task, resolving an open question from (Anshu et al., STOC `24). We do this by proving that noisy postselected quantum computation can be made fault-tolerant.

arXiv:2509.19963•Sep 24, 2025•0 citations

PEPS as unique ground states of local Hamiltonians

David Pérez-Garcı́a, Frank Verstraete, J. I. Cirac +1 more

In this paper we consider projected entangled pair states (PEPS) on arbitrary lattices. We construct local parent Hamiltonians for each PEPS and isolate a condition under which the state is the unique ground state of the Hamiltonian. This condition, verified by generic PEPS and examples like the AKLT model, is an injective relation between the boundary and the bulk of any local region. While it implies the existence of an energy gap in the 1D case we will show that in certain cases (e.g., on a 2D hexagonal lattice) the parent Hamiltonian can be gapless with a critical ground state. To show this we invoke a mapping between classical and quantum models and prove that in these cases the injectivity relation between boundary and bulk solely depends on the lattice geometry.

Quantum Information and Computation•Jul 1, 2008•76 citations

Criticality, the Area Law, and the Computational Power of Projected Entangled Pair States

Frank Verstraete, M. M. Wolf, David Pérez-Garcı́a +1 more

The projected entangled pair state (PEPS) representation of quantum states on two-dimensional lattices induces an entanglement based hierarchy in state space. We show that the lowest levels of this hierarchy exhibit a very rich structure including states with critical and topological properties. We prove, in particular, that coherent versions of thermal states of any local 2D classical spin model correspond to such PEPS, which are in turn ground states of local 2D quantum Hamiltonians. This correspondence maps thermal onto quantum fluctuations, and it allows us to analytically construct critical quantum models exhibiting a strict area law scaling of the entanglement entropy in the face of power law decaying correlations. Moreover, it enables us to show that there exist PEPS which can serve as computational resources for the solution of NP-hard problems.

arXiv:quant-ph/0601075•Physical Review Letters•Jun 6, 2006•580 citations

Tensor network states for the description of quantum many-body systems

Thorsten B. Wahl

This thesis is divided into two mainly independent parts: In the first part, we derive a criterion to determine when a translationally invariant Matrix Product State (MPS) has long range localizable entanglement, which indicates that the corresponding state has some kind of non-local hidden order. We give examples fulfilling this criterion and eventually use it to obtain all such MPS with bond dimension 2 and 3. In the second part, we show that Projected Entangled Pair States (PEPS) in two spatial dimensions can describe chiral topological states by explicitly constructing a family of such states with a non-trivial Chern number. We demonstrate that such free fermionic PEPS must necessarily be non-injective and have gapless parent Hamiltonians. Moreover, we provide numerical evidence that they can nevertheless approximate well the physical properties of Chern insulators with local Hamiltonians at arbitrary temperatures. We also construct long range, topological Hamiltonians with a flat energy spectrum for which those PEPS are unique ground states. As for non-chiral topological PEPS, the non-trivial, topological properties can be traced down to the existence of a symmetry on the virtual level of the PEPS tensor that is used to build the state. We use the special properties of PEPS to build the boundary theory and show how the symmetry results in the appearance of chiral modes, a ground state degeneracy of the parent Hamiltonian on the torus and a universal correction to the area law for the zero Rényi entropy. Finally, we show that PEPS can also describe chiral topologically ordered phases. For that, we construct a simple PEPS for spin-1/2 particles in a two-dimensional lattice. We reveal a symmetry of the PEPS tensor that gives rise to the global topological character. We also extract characteristic quantities of the edge Conformal Field Theory using the bulk-boundary correspondence.

arXiv:1509.05984•Sep 20, 2015•0 citations
Projected entangled pair states aim at describing lattice systems in two spatial dimensions that obey an area law. They are specified by associating a tensor with each site, and they are generated by patching these tensors. We consider the problem of determining whether the state resulting from this patching is null, and prove it to be NP-hard; the PEPS used to prove this claim have a boundary and are homogeneous in their bulk. A variation of this problem is next shown to be undecidable. These results have various implications: they question the possibility of a 'fundamental theorem' for PEPS; there are PEPS for which the presence of a symmetry is undecidable; there exist parent hamiltonians of PEPS for which the existence of a gap above the ground state is undecidable. En passant, we identify a family of classical Hamiltonians, with nearest neighbour interactions, and translationally invariant in their bulk, for which the commuting 2-local Hamiltonian problem is NP-complete.
In this paper we consider projected entangled pair states (PEPS) on arbitrary lattices. We construct local parent Hamiltonians for each PEPS and isolate a condition under which the state is the unique ground state of the Hamiltonian. This condition, verified by generic PEPS and examples like the AKLT model, is an injective relation between the boundary and the bulk of any local region. While it implies the existence of an energy gap in the 1D case we will show that in certain cases (e.g., on a 2D hexagonal lattice) the parent Hamiltonian can be gapless with a critical ground state. To show this we invoke a mapping between classical and quantum models and prove that in these cases the injectivity relation between boundary and bulk solely depends on the lattice geometry.
In this paper we consider projected entangled pair states (PEPS) on arbitrary lattices. We construct local parent Hamiltonians for each PEPS and isolate a condition under which the state is the unique ground state of the Hamiltonian. This condition, verified by generic PEPS and examples like the AKLT model, is an injective relation between the boundary and the bulk of any local region. While it implies the existence of an energy gap in the 1D case we will show that in certain cases (e.g., on a 2D hexagonal lattice) the parent Hamiltonian can be gapless with a critical ground state. To show this we invoke a mapping between classical and quantum models and prove that in these cases the injectivity relation between boundary and bulk solely depends on the lattice geometry.
Projected entangled pair states (PEPS) constitute a variational family of quantum states with area-law entanglement. PEPS are particularly relevant and successful for studying ground states of spatially local Hamiltonians. However, computing local expectation values in these states is known to be \postBQP-hard. Injective PEPS, where all constituent tensors fulfil an injectivity constraint, are generally believed to be better behaved, because they are unique ground states of spatially local Hamiltonians. In this work, we therefore examine how the computational hardness of contraction depends on the injectivity. We establish that below a constant positive injectivity threshold, evaluating local observables remains \postBQP-complete, while above a different constant nontrivial threshold there exists an efficient classical algorithm for the task, resolving an open question from (Anshu et al., STOC `24). We do this by proving that noisy postselected quantum computation can be made fault-tolerant.
In this paper we consider projected entangled pair states (PEPS) on arbitrary lattices. We construct local parent Hamiltonians for each PEPS and isolate a condition under which the state is the unique ground state of the Hamiltonian. This condition, verified by generic PEPS and examples like the AKLT model, is an injective relation between the boundary and the bulk of any local region. While it implies the existence of an energy gap in the 1D case we will show that in certain cases (e.g., on a 2D hexagonal lattice) the parent Hamiltonian can be gapless with a critical ground state. To show this we invoke a mapping between classical and quantum models and prove that in these cases the injectivity relation between boundary and bulk solely depends on the lattice geometry.
The projected entangled pair state (PEPS) representation of quantum states on two-dimensional lattices induces an entanglement based hierarchy in state space. We show that the lowest levels of this hierarchy exhibit a very rich structure including states with critical and topological properties. We prove, in particular, that coherent versions of thermal states of any local 2D classical spin model correspond to such PEPS, which are in turn ground states of local 2D quantum Hamiltonians. This correspondence maps thermal onto quantum fluctuations, and it allows us to analytically construct critical quantum models exhibiting a strict area law scaling of the entanglement entropy in the face of power law decaying correlations. Moreover, it enables us to show that there exist PEPS which can serve as computational resources for the solution of NP-hard problems.
This thesis is divided into two mainly independent parts: In the first part, we derive a criterion to determine when a translationally invariant Matrix Product State (MPS) has long range localizable entanglement, which indicates that the corresponding state has some kind of non-local hidden order. We give examples fulfilling this criterion and eventually use it to obtain all such MPS with bond dimension 2 and 3. In the second part, we show that Projected Entangled Pair States (PEPS) in two spatial dimensions can describe chiral topological states by explicitly constructing a family of such states with a non-trivial Chern number. We demonstrate that such free fermionic PEPS must necessarily be non-injective and have gapless parent Hamiltonians. Moreover, we provide numerical evidence that they can nevertheless approximate well the physical properties of Chern insulators with local Hamiltonians at arbitrary temperatures. We also construct long range, topological Hamiltonians with a flat energy spectrum for which those PEPS are unique ground states. As for non-chiral topological PEPS, the non-trivial, topological properties can be traced down to the existence of a symmetry on the virtual level of the PEPS tensor that is used to build the state. We use the special properties of PEPS to build the boundary theory and show how the symmetry results in the appearance of chiral modes, a ground state degeneracy of the parent Hamiltonian on the torus and a universal correction to the area law for the zero Rényi entropy. Finally, we show that PEPS can also describe chiral topologically ordered phases. For that, we construct a simple PEPS for spin-1/2 particles in a two-dimensional lattice. We reveal a symmetry of the PEPS tensor that gives rise to the global topological character. We also extract characteristic quantities of the edge Conformal Field Theory using the bulk-boundary correspondence.