First we should check Hartree-Fock is in NP, to do this we notice the ground state is $|\phi_0\rangle =(n!)^{-1/2}det|\phi_a(1)\phi_b(2)...\phi_z(n)|$. 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 $b_N^{\dagger}b_{N-1}^{\dagger}...b_1^{\dagger}|\Omega\rangle$ where $b_i=\Sigma u_{ij}a_j$ and $latex |\Omega\rangle$ is the vacuum. Note that $b_i$ is a fermion creater which is antisymmetric and satisfy $b_i^{\dagger}b_i^{\dagger}$ is 0. So it’s equivalent to the determinant expression.
Basically what we do is add $\lambda n_{2i}n_{2i+1}(\lambda=\theta(N^2))$ to penalize double occupancy and convert $J_{ij}S_iS_j$ to $J_{ij}\sum_{p,q=0,1}(-1)^{p+q}n_{2i+p}n_{2j+q}$. Only one of the four terms actually appear since we add the penalty for double occupancy previously. $(-1)^{p+q}$ represents the sign of the product $S_iS_j$. The ground state mapping is $S_i=1$ to $b_i=a_{2i}$ and $S_i=-1$ to $b_i=a_{2i+1}$