Optimizing sparse fermionic Hamiltonians: guarantees and obstructions

CS/Math Seminar - Yaroslav Herasymenko, TU Delft (whiteboard presentation)

Fermionic optimization is a quantum extension of constraint satisfaction that is a distinct alternative to the qubit Hamiltonian problem. Extremal eigenvalues of fermionic Hamiltonians can sometimes be approximated via so-called Gaussian states, which are classically simulable. The accuracy of such an approximation depends on the structure of the Hamiltonian. From the mathematical perspective, this dependence is not very well understood.

I will present two recent works that focus on fermions with sparse interactions. The first result is a guarantee: the ground energy of such a Hamiltonian can always be found within a constant factor using a Gaussian state. The second result is an obstruction – a fermionic version of the NLTS Theorem. Namely, we give sparse fermionic Hamiltonians whose low-energy states can’t be prepared with shallow fermionic circuits, even given free access to Gaussian unitaries. Some open directions, as well as the relation of these results to SYK physics and the quantum PCP theorem, will be discussed.

The talk will be based on these two papers:
https://quantum-journal.org/papers/q-2023-08-10-1081/
https://arxiv.org/abs/2307.13730