Skip to content

NP-completeness of Hartree-Fock

October 6, 2012

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 |\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}

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: