Algebras, CSPs, and Quantum Computing
Abstract: Classical constraint satisfaction problems (CSPs), such as 3SAT and MaxCut, have two important quantum generalizations: the Local Hamiltonian problem and Nonlocal Games. These frameworks offer rich insights into both physical and computational aspects of quantum systems. On the computational side, the Local Hamiltonian problem is complete for the complexity class QMA, consisting of all efficiently verifiable problems, while Nonlocal Games capture RE, a much larger class consisting of all computable problems (and more). Physically, Hamiltonians model interactions between particles in a quantum system, whereas Nonlocal Games is a tool for understanding the set of quantum correlations. In this talk, I will discuss these quantum CSPs, present recent results including my own contributions, and highlight several open problems. A central theme will be the striking divergence between these two notions of constraint satisfaction in the quantum setting, and the insights we gain if we manage to unify them.
Bio: Hamoon Mousavi is a postdoctoral fellow at the Simons Institute at Berkeley hosted by Prof. Umesh Vazirani. He completed my PhD in Computer Science at Columbia University advised by Prof. Henry Yuen. Hisresearch focuses on quantum computing and complexity, with an emphasis on understanding polynomial optimization and constraint satisfaction problems in the noncommutative setting.
To watch online go to the IQUIST youtube channel: https://www.youtube.com/channel/UCCzAySwQXF8J4kRolUzg2ww
For Zoom link you may check the IQUIST calendar weekly email or contact Stephanie Gilmore (stephg1@illinois.edu). To subscribe to our weekly email for event announcements, please go to https://lists.illinois.edu/lists/subscribe/iquist-announcements.