Quadratic fermionic interactions yield effective Hamiltonians for adiabatic quantum computing

Polynomially-large ground-state energy gaps are rare in many-body quantum
systems, but useful for adiabatic quantum computing. We show analytically that
the gap is generically polynomially-large for quadratic fermionic Hamiltonians.
We then prove that adiabatic quantum computing can realize the ground states of
Hamiltonians with certain random interactions, as well as the ground states of
one, two, and three-dimensional fermionic interaction lattices, in polynomial
time. Finally, we use the Jordan-Wigner transformation and a related
transformation for spin-3/2 particles to show that our results can be restated
using spin operators in a surprisingly simple manner. A direct consequence is
that the one-dimensional cluster state can be found in polynomial time using
adiabatic quantum computing.