Robust Polynomial Method and a Sub-Volume Law for Locally Gapped Frustration-Free Spin Systems

Anurag Anshu (IQC)
The Quantum Wave in Computing
Seminar, Apr. 14, 2020

The robust polynomial method (Sherstov [2012]) was developed for the composition of polynomial approximations to boolean functions, inspired by questions on the composition of quantum query algorithms. In this talk, we discuss how it can be used to study polynomial approximations to the AND function, reproducing some known improvements over the Chebyshev-based approximation. Using these ideas and the tool of Approximate Ground Space Projectors developed in prior works , we study the entanglement entropy of frustration-free ground states on a two dimensional lattice. Under the assumption of a local spectral gap (also referred to as a uniform spectral gap), we show a sub-volume scaling of the entanglement entropy.

Simons Institute,theoretical computer science,UC Berkeley,Computer Science,Theory of Computation,Theory of Computing,