Revision 1

Accepted · first revision · record

Title: Efficient contraction of PEPS for gapped two-dimensional ground states
Plain: Two-dimensional quantum states can be written compactly as networks of small tensors (PEPS, projected entangled pair states), but extracting numbers from these networks is in general very hard. Whether it becomes easy for physically relevant states with an energy gap is open.
Precise: For an injective PEPS of bond dimension $\chi = O(1)$ on an $L$ x L lattice whose parent Hamiltonian is gapped uniformly in L, is there a classical algorithm computing a local expectation value to additive error $\epsilon$ in time $\operatorname{poly}(L, 1/\epsilon)$? Exact contraction of general PEPS is #P-hard (Schuch et al. 2007) and random PEPS are average-case hard to contract (Haferkamp et al. 2020). Schwarz, Buerschaper and Eisert (Phys. Rev. A 95, 060102, 2017, arXiv:1606.06301) give a quasi-polynomial algorithm under additional assumptions (a gapped transfer operator and conditions on the boundary state); the open question is polynomial time from the bulk gap alone.
Settled by: A provably efficient contraction algorithm under the gap assumption, or a hardness proof for gapped injective PEPS.
Kind: well-posed
Answer type: yes-no
References: (empty)
Literature status: partially-resolved
Status note: Quasi-polynomial contraction is known under extra assumptions (2017); polynomial time from the gap alone is open.
Posed since: (empty)