Kareem Diab

My research interests are primarily about two different areas of theoretical computer science. The first is the study of powerful optimization algorithms called semidefinite programming hierarchies, which are among the best known tools for solving hard combinatorial problems. The Sum-of-Squares Hierarchy(SoS) is one such algorithm, which aims to prove that a given polynomial is nonnegative, by expressing it as a sum of squares. A central question is: when does SoS fundamentally fail, and why?

The second area is quantum complexity theory, which is the study of the capabilities and limitations of quantum computers. A landmark recent result called the NLTS theorem, showed that there exist hamiltonians (quantum systems), with low-energy states that no shallow quantum circuit can prepare. Surprisingly, the proof uses the same mathematical structure (expander graphs) that explains why SoS fails on certain hard instances.

My current work explores this connection. I construct quantum Hamiltonians directly from the hard instances that break SoS, and ask whether the classical hardness survives in the quantum setting. If it does, these Hamiltonians may be hard for both shallow quantum circuits and powerful classical optimization algorithms simultaneously. This question is deeply motivated by the quantum PCP conjecture.