Polynomially-large ground-state energy gaps are rare in many-body quantum systems, but required for adiabatic quantum computing. We show analytically that the gap is generically polynomially-large for quadratic fermionic Hamiltonians, first considered by Lieb et al. 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 to show that our results can be restated with Pauli operators in a surprisingly simple manner.
Citation: Physical Review A (Atomic, Molecular and Optical Physics)
Pub Type: Journals
adiabatic quantum computing, fermionic interaction lattices, Jordan-Wigner transformation, Pauli operators, quadratic fermionic Hamiltonians