Vertex Cover mappings from QUBO to Ising and vice versa

Question

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?

Answer 1

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