How to convert QUBO problem to Ising Hamiltonian?

Question

According to paper Ising formulations of many NP problems an unconstrained quadratic programming problem $$ f(x_1, x_2,\dots, x_n) = \sum_{i}^N h_ix_i + \sum_{i < j} J_ix_ix_j $$ can be expressed as Hamiltonian $$ H(x_1, x_2,\dots, x_n) = -\sum_{i}^N h_i\sigma^z_i - \sum_{i < j} J_i\sigma^z_i\sigma^z_j, $$ where $\sigma^z_i$ is Pauli $Z$ gate applied on $i$th qubit whereas other qubits are left without change.

I tried to prepare Hamiltonian for simple function $$ f(x_1,x_2) = 5x_1+x_2-2x_1x_2 $$

as $$ H = -(5 Z \otimes I + I \otimes Z - 2 Z \otimes Z) = \text{diag}(-4,-6,2,8). $$

So the minimal eigenvalue is -6 and associated ground state is $|01\rangle = (0, 1, 0, 0)^T$ which is correct as $f(x_1,x_2)$ minimal value is 1 for $x_1 = 0$ and $x_2 = 1$.

However, when I changed $-2x_1x_2$ to $-7x_1x_2$ and the Hamiltonian changed to $\text{diag}(1,-11,-3,13)$, the ground state remainded $|01\rangle$, however, in this case the function has minimum in $x_1 = 1$ and $x_2 = 1$ (i.e. the ground state should be $|11\rangle = (0,0,0,1)^T$).

What did I do (or understand) wrong?

Answer 1

Maybe this will help. Let's take a simple case:

$$f(x_1, x_2) = -2x_1 x_2$$

Then it is minimum when $x_1 = x_2 = 1$. Now let's take this Hamiltonian:

$$H_f = -2Z \otimes Z$$

The Hamiltonian is minimum when we have either $|00\rangle$ or $|11\rangle$ states. So this Hamiltonian doesn't correspond to the $f(x_1, x_2)$. Instead this one looks better:

$$H_f = -2 \left(\frac{I - Z}{2}\right) \otimes \left(\frac{ I - Z}{2}\right)$$

Because in this case, $f(x_1, x_2)$ is equal to the $H_f$'s eigenvalue for the $|x_1 x_2\rangle$ eigenstate. And, consequently, if $x_1$ and $x_2$ correspond to the minimum value of $f(x_1, x_2)$, then $|x_1 x_2\rangle$ will be the eigenstate with the minimum eigenvalue for $H_f$. This is right, because the operator $\frac{I - Z}{2}$ has $|x=0 \rangle$ and $|x=1 \rangle$ eigenstates with corresponding $0$ and $1$ eigenvalues.

So, for the $f(x_1, x_2) = 5 x_1 + x_2 - 2 x_1 x_2$ we can introduce the following Hamiltonian:

\begin{equation} H_f = 5 \frac{I - Z}{2} \otimes I + I \otimes \frac{I - Z}{2} - 2 \frac{I - Z}{2} \otimes \frac{I - Z}{2} = \\ =\frac{5}{2} I \otimes I - 2 Z \otimes I - \frac{1}{2} Z \otimes Z = \text{diag}(0, 1, 5, 4) \end{equation}

Note that $H_f|x_1 x_2\rangle = f(x_1, x_2) |x_1 x_2\rangle$. For optimization problems we can ignore $\frac{5}{2}I \otimes I$ term. In that case all eigenvalues will be shifted with the same $-\frac{5}{2}$ value. With or without $\frac{5}{2}I \otimes I$ term the eigenstates with minimum or maximum eigenvalues will stay at the same "places".

---

This procedure will also work for more general cost functions $f(x)$ (not necessarily QUBO $\rightarrow$ Ising Hamiltonian). Here is an answer about this.