QLunch: Dylan Harley

Speaker: Dylan Harley from QMATH

Title: Computational complexity of projected entangled pair states

Abstract: Projected entangled pair states (PEPS) are a family of quantum states used widely and successfully for the classical simulation of quantum many-body physics. Though they can be described efficiently, computing their local properties is hard in general — even for quantum computers! In this work, we examine how this hardness persists for the somewhat more well-behaved subclass of injective PEPS. We show that below a constant non-trivial injectivity threshold, evaluating local observables remains postBQP-hard, whilst above a different non-trivial threshold the task can be solved efficiently classically. This resolves an open question from (Anshu et al., STOC ’24).