# How to convert QUBO problem to Ising Hamiltonian?

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?

• Martin, how did you obtain the expressions for $H$ and $f$? I didn't find them in the link. Apr 23, 2020 at 21:12
• @DavitKhachatryan: function $f(x)$ is general formulation of QUBO problem. Hamiltonian is based on eq. (3). But it seems that my misunderstanding comes from the fact that there are variables $s_i = \pm 1$ instead of $x_i \in \{0;1\}$. I will go through your answer as it seems I understand now where my mistake is. Apr 23, 2020 at 21:17
• Ok. The problem is that I think the $J_i$ and $h_i$ coefficients in those expressions should be different if my answer is right. Apr 23, 2020 at 21:20

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:

$$$$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)$$$$

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.

• I think I see where my misunderstanding is. The Ising Hamiltonian for spin glasses is based on variables $s_i = \pm 1$ which are eigenvalues of Pauli $Z$. However, for QUBO we need binary variables $x_i \in \{0;1\}$. These are eigenvalues of $\frac{I-Z}{2}$ with corresponding eigenstates $|0\rangle$ and $|1\rangle$. So, to use Ising Hamiltonian for QUBO task, we need to switch from $Z$ to $\frac{I-Z}{2}$. Right? Apr 23, 2020 at 21:36
• Just note that there is probably mistake in the article. They stated that operator $\frac{I+Z}{2}$ has eigenvalues 0 and 1 with eigenstates $|0\rangle$ and $|1\rangle$, respectively. However 1 is connected with $|0\rangle$. This also confused me. After your explanation, it seems clearer to me. I will try to play with some $H$ and $f$. Apr 23, 2020 at 21:40
• I will rather say, that to obtain Ising Hamiltonian for the QUBO task, we need to switch from $x_i$ to $\frac{I - Z_i}{2}$. If you have the Hamiltonian from the link with spin variables, you can just switch from $s_i$ to $Z_i$. Apr 23, 2020 at 21:52
• Yes, I see. Last note, if you use operator $\frac{I+Z}{2}$, you get inverted results because of switched eigenvalues in comparison with $\frac{I-Z}{2}$. Anyway, thanks for help. Apr 23, 2020 at 21:56

It seems that $$f(x_1,x_2)=5 x_1 + x_2 − 2x_1 x_2$$ has the minimal value 0 when $$x_1 = 0$$ and $$x_2 = 0$$, instead of minimal value 1 when $$x_1 = 0$$ and $$x_2 = 1$$.

The Hamiltonian is $$H = f(\frac{I - Z_1}{2}, \frac{I - Z_2}{2}) = diag(0, 1, 5, 4)$$ The eigenvector corresponding to minimal eigenvalue (energy) is $$|00\rangle$$.

• Thanks, your are right. How could I make such mistake! Mar 29, 2023 at 5:56