# NP-completeness of Hartree-Fock

The reduction is from Ising spin glasses. This post is an excerpt from Schuch’s paper with my comments.

First we should check Hartree-Fock is in NP, to do this we notice the ground state is . And since the determinant can be computed in polynomial time, we can efficiently evaluate whether a ground state is below a threshold. Another way of writing the ground state is where and $latex |\Omega\rangle$ is the vacuum. Note that $b_i$ is a fermion creater which is antisymmetric and satisfy is 0. So it’s equivalent to the determinant expression.

Basically what we do is add to penalize double occupancy and convert to . Only one of the four terms actually appear since we add the penalty for double occupancy previously. represents the sign of the product . The ground state mapping is to and to