# Eigenvalue of the adiabatic Hamiltonian of Farhi's three qubit 2-SAT problem

I was trying to reproduce example 3.3 of Quantum Computation by Adiabatic Evolution by Edward Farhi et. al. This is an adiabatic algorithm to solve an instance of three qubits 2-SAT problem.

I think I have created the initial Hamiltonian, $H_B$ correctly. It is just an $8 \times 8$ Hadamard matrix.

$$H_B = \left( \begin{array}{cccccccc} \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} \\ \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} \\ \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} \\ \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} \\ \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} \\ \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} \\ \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} \\ \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & \frac{1}{2 \sqrt{2}} & -\frac{1}{2 \sqrt{2}} \\ \end{array} \right)$$

According to the example, the unique satisfying assignment is $011$. The problem Hamiltonian is a sum of three sub-Hamiltonians each correspond to a clause.

$$H_P = I_8 - H^{12}_{imply} - H^{13}_{disagree}-H^{23}_{agree}$$

Here are my results for sub-Hamiltonians.

$H^{12}_{imply}$ clause can be satisfied with any of $00$, $01$ or $11$. So,

$$H^{12}_{imply} = \left(\left(\frac{1}{\sqrt{6}}\right)\left(|000\rangle+|001\rangle+|010\rangle+|011\rangle+|110\rangle+|111\rangle\right)\right) \left(\left(\left(\frac{1}{\sqrt{6}}\right)\left(|000\rangle+|001\rangle+|010\rangle+|011\rangle+|110\rangle+|111\rangle\right)\right)\right)^{\dagger}$$

The ground state of this Hamiltonian satisfies the assignment constraint.

$H^{13}_{disagree}$ clause can be satisfied with any of $01$ or $10$. So,

$$H^{13}_{disagree} = \left(\left(\frac{1}{2}\right)\left(|001\rangle+|011\rangle+|100\rangle+|110\rangle\right)\right) \left(\left(\left(\frac{1}{2}\right)\left(|001\rangle+|011\rangle+|100\rangle+|110\rangle\right)\right)\right)^{\dagger}$$

The ground state of this Hamiltonian satisfies the assignment constraint.

$H^{23}_{agree}$ clause can be satisfied with any of $00$ or $11$. So,

$$H^{23}_{agree} = \left(\left(\frac{1}{2}\right)\left(|001\rangle+|011\rangle+|100\rangle+|110\rangle\right)\right) \left(\left(\left(\frac{1}{2}\right)\left(|001\rangle+|011\rangle+|100\rangle+|110\rangle\right)\right)\right)^{\dagger}$$

The ground state of this Hamiltonian satisfies the assignment constraint.

So, $$H_P = \left( \begin{array}{cccccccc} \frac{17}{6} & -\frac{1}{6} & -\frac{1}{6} & -\frac{1}{6} & 0 & 0 & -\frac{1}{6} & -\frac{1}{6} \\ -\frac{1}{6} & \frac{7}{3} & -\frac{1}{6} & -\frac{2}{3} & -\frac{1}{2} & 0 & -\frac{2}{3} & -\frac{1}{6} \\ -\frac{1}{6} & -\frac{1}{6} & \frac{17}{6} & -\frac{1}{6} & 0 & 0 & -\frac{1}{6} & -\frac{1}{6} \\ -\frac{1}{6} & -\frac{2}{3} & -\frac{1}{6} & \frac{7}{3} & -\frac{1}{2} & 0 & -\frac{2}{3} & -\frac{1}{6} \\ 0 & -\frac{1}{2} & 0 & -\frac{1}{2} & \frac{5}{2} & 0 & -\frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 \\ -\frac{1}{6} & -\frac{2}{3} & -\frac{1}{6} & -\frac{2}{3} & -\frac{1}{2} & 0 & \frac{7}{3} & -\frac{1}{6} \\ -\frac{1}{6} & -\frac{1}{6} & -\frac{1}{6} & -\frac{1}{6} & 0 & 0 & -\frac{1}{6} & \frac{17}{6} \\ \end{array} \right)$$

This Hamiltonian, which represents the instance of the problem is expected to be satisfied only with the assignment 011. So, the ground state should be $|011\rangle$.

But in reality, the ground eigenvalue is greater than $0$ and the ground state is $\left(1,4,1,4,3,0,4,1\right)^{\dagger}$.

Here, $I_n$ is the $n \times n$ identity matrix.

What was I doing wrong? My Mathematica code is available here.

• Jeffrey Goldstone replied to my email. He suggested to use an $8 \times 8$ Hadamard matrix as $H_B$. For $H_P$ he suggested to use the projector $I - |ground-state-of-H-imply><ground-state-of-H-imply| - |ground-state-of-H-disagree><ground-state-of-H-disagree| - |ground-state-of-H-agree><ground-state-of-H-agree|$. I am going to fix accordingly. – Omar Shehab Oct 9 '14 at 6:31
• You should factor those $1/2\sqrt{2}$'s out of that first matrix. – DanielSank Oct 9 '14 at 7:24