QUBO and Ising Equivalence
QUBO and Ising are binary quadratic models used in Quantum Annealing. We show that they are isomorphic, thus, both formulations provide the same level of information and can be used interchangeably.
For a introduction to Quantum Annealing, including Ising and QUBO, see my other article:
We show that the Ising model and QUBO formulation are isomorphic. Consider the Hamiltonian of the Ising Model:
Using the spin-binary bijection σ → 2x − 1 (1 is a vector whose components are all one), we are able to transform the equation into the equivalent QUBO problem as described in reverse in [1]:
where nbr(i) denotes the neighbors of vertex i. In the last step, we defined:
This way, we obtained the QUBO representation out of the Ising model, hence they are equivalent. Note that we can drop the constant c as it does not change the position of the optimum x*.
Sources
[1] Choi, V. Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem. April 30, 2008. Visited on February 17, 2022.
More about me
If you found this article helpful, feel free to share it with your friends and leave a comment. You can find more about me here:
GitHub | YouTube (music)| Website (music)
