Spectral Certificates and Non-commutative Sum-of-Squares Lower Bounds for Hamiltonians
The paper presents a classical spectral algorithm that certifies ground energy for semirandom Hamiltonian k-XOR instances within 1/2 + ε, achieving an efficient time complexity of n O(ℓ). It establishes a tradeoff between time and the number of local terms, linking the problem to refutation models and showing entanglement structure is not robust to internal noise.