1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Martin, how did you obtain the expressions for $H$ and $f$? I didn't find them in the link. $\endgroup$ – Davit Khachatryan Apr 23 at 21:12
  • $\begingroup$ @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. $\endgroup$ – Martin Vesely Apr 23 at 21:17
  • $\begingroup$ 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. $\endgroup$ – Davit Khachatryan Apr 23 at 21:20
2
$\begingroup$

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".

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Martin Vesely Apr 23 at 21:36
  • 1
    $\begingroup$ 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$. $\endgroup$ – Martin Vesely Apr 23 at 21:40
  • 1
    $\begingroup$ 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$. $\endgroup$ – Davit Khachatryan Apr 23 at 21:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Vesely Apr 23 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.