Kareem Diab

We investigate whether classical sum-of-squares (SoS) integrality gaps can be lifted to non-commutative SoS (ncSoS) integrality gaps for local Hamiltonians built from the same underlying constraint structure. Our primary object of study is a family of two-basis Hamiltonians H = H_Z + H_X, where each summand encodes a 3-XOR instance over a different Pauli basis, forming a CSS-type Hamiltonian. This construction provides a natural quantization of Max-3XOR in which the classical hardness of the underlying CSP and the quantum geometry of the code coexist in a single object. We make preliminary progress toward establishing such a lifting. We formulate a noncommutative analogue of Grigoriev's theorem for CSS-type Hamiltonians, and show that such a result would give unconditional algorithmic lower bounds against the NPA hierarchy for a natural class of quantum optimization problems. As a first step, we establish tight bounds on the maximum eigenvalue of H in terms of the number of clauses and the unsatisfiability of the underlying instance. We additionally observe that the Lovász theta function of the conflict graph of H gives a natural SDP upper bound on the maximum eigenvalue, and we have identified the underlying conflict graph as a bipartite induced subgraph of a Johnson-scheme graph. We are making progress toward a concrete bound on the Lovász theta function of this graph, which we expect to provide further insight into the integrality gap. The expander graphs underlying the hard CSP instances in Grigoriev's theorem share key structural properties with the Tanner codes used in recent NLTS constructions. We observe that the two-basis Hamiltonians studied here sit naturally at this intersection, raising the possibility of obtaining NLTS Hamiltonians with additional provable hardness guarantees against efficient classical algorithms.