The complexity of ground states of local Hamiltonians is the quantum analog of the theory of NP-Completeness. It features the two most important open questions in quantum complexity theory: the quantum PCP conjecture and the Area Law for 2D gapped Hamiltonians. Recent progress on the first question has been a direct consequence of the discovery of good quantum LDPC codes, while progress on the second question has relied on fault-tolerant polynomials. In a very exciting development, ideas from quantum error correction and quantum complexity theory play an unexpected and deep role in current attempts to understand quantum gravity. These connections even suggest the possibility that quantum gravity could violate the quantum extended Church-Turing thesis. This workshop will bring together researchers from TCS, information and coding theory, mathematics, physics to share recent progress, exchange ideas and make progress on these questions.


Registration is required to attend this workshop. Space may be limited, and you are advised to register early.

For additional information please visit: https://simons.berkeley.edu/participating-workshop.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

Register Now