2
$\begingroup$

According to paper Ising formulations of many NP problems, Vertex Cover problem has the following Ising formulation:

$$\underset{x}{\text{min }} f(x) = a\sum_{(i,j) \in E}(1-x_i)(1-x_j) + b\sum_{i \in V} x_i.$$

I'd like to share some doubts of mine.

Ising formulation has spin variables $\{+1,-1\}$, not logical variable $\{0,1\}$. Shouldn't it be considered a QUBO problem?

By considering this formulation as a QUBO problem, then I should get the Ising formulation by mapping $x_i \rightarrow \frac{1 - \text{Z}_i}{2}$ as follows: $$H = \frac{a}{4}\sum_{(i,j) \in E}(\text{Z}_i + \text{Z}_j + \text{Z}_i\text{Z}_j) - \frac{b}{2}\sum_{i \in V}\text{Z}_i + |V|.$$

However, from qiskit library authors consider the following hamiltonian:

$$H = a\sum_{(i,j) \in E}(1-\text{X}_i)(1-\text{X}_j) +b\sum_{i \in V}\text{Z}_i.$$ which seems different from both previous formulations. Are the two hamiltonians somehow equivalent?

Improve this question
$\endgroup$
2
$\begingroup$

First, I agree with the fact that this is actually a QUBO form and not an Ising model, I think they allow themselves the shortcut from one to the other because of the mapping from bits to spins.

Second, notice that in the Qiskit documentation you pointed, they use the mapping $X_i = \frac{Z_i+1}{2}$. Now, if I didn't make mistakes, by replacing $x_i$ with this mapping in the QUBO form of the first paper, you end up with this : $$ \frac{a}{4}\sum\limits_{ij \in E}(1-Z_i)(1-Z_j) +\frac{b}{2}\sum_iZ_i +\frac{b}{2}|V| $$

And if you replace $X_I$ in the hamiltonian form from Qiskit (I believe $A = 5$ here): $$ \frac{A}{4}\sum\limits_{ij \in E}(1-Z_i)(1-Z_j)+\sum_i Z_i $$

As you can see, they have the same form, with a few different details but irrelevant in the resolution of the problem.

Hope this clears your question, please tell me if you need something else ;)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your answer! I agree with you. Two questions arise: (1) why that mapping? And (2) why are those different details irrelevant? $\endgroup$ – Daniele Cuomo Feb 18 at 10:32
  • $\begingroup$ (1) Not sure about why they chose this precise mapping here, but both mappings are valid of course, the one you pointed first is even used in the max-cut tutorial. I just wanted to point that when using the same mapping, you have equivalent forms of hamiltonians. $\endgroup$ – Lena Feb 18 at 10:57
  • $\begingroup$ (2) First detail : we have a constant in the first form but not the second. When solving the min/max, this constant won't have any impact on the form of the solution, by that I mean the constant will not have any influence on the values we assign at the bits/spins, it is just an offset that we need to add in the end to have the value of the studied function. Second, the first form from the paper has $A$ and $B$ constants with the only constraint $B<A$, and in Qiskit since it is an implementation they chose values for $A$ and $B$. $\endgroup$ – Lena Feb 18 at 11:04
  • $\begingroup$ (2) totally agree, thank you. (I believe there's just a typo from Qiskit docs) (1) may you explain why they are both valid mappings? $\endgroup$ – Daniele Cuomo Feb 18 at 11:23
  • 1
    $\begingroup$ Glad you agree! About the mappings, what I meant by that is both will map spins into bits : $\{-1, 1\} \mapsto \{0,1\}$, the difference will be there : $$ x = \frac{1-z}{2} : \left\{ \begin{array}{l} z = 1 \Rightarrow x=0 \\ z = -1 \Rightarrow x=1\end{array} \right.$$ $$ x = \frac{1+z}{2} : \left\{ \begin{array}{l} z = 1 \Rightarrow x=1 \\ z = -1 \Rightarrow x=0\end{array} \right.$$ $\endgroup$ – Lena Feb 18 at 13:08

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.