Computer Science/Discrete Mathematics Seminar I

A central goal of physics is to understand the low-energy solutions of quantum interactions between particles. This talk will focus on the complexity of describing low-energy solutions; I will show that we can construct quantum systems for which the low-energy solutions are highly complex and unlikely to exhibit succinct classical descriptions. I will discuss the implications these results have for robust entanglement at constant temperature and the quantum PCP conjecture. En route, I will discuss our positive resolution of the No Low-energy Trivial States (NLTS) conjecture on the existence of robust complex entanglement.

Mathematically, for an n-particle system, the low-energy states are the eigenvectors corresponding to small eigenvalues of an exp(n)-sized matrix called the Hamiltonian, which describes the interactions between the particles. Low-energy states are the quantum generalizations of approximate solutions to satisfiability problems such as 3-SAT. In this talk, I will discuss the theoretical computer science techniques used to prove circuit lower bounds for all low-energy states. This morally demonstrates the existence of Hamiltonian systems whose entire low-energy subspace is robustly entangled.