I'm learning about connection between QUBO and The Ising Model.

It says

Take the base Hamiltonian of an adiabatic process as $\sum_i \big(\frac{1-\sigma_i^x}{2}\big)$

to implement Hamiltonian for Ising Model. Is there any specific reason or standard for selecting this hamiltonian? Or what material will help me? Thank you.


While a general QUBO task has form $$ \sum_{i=1}^n b_ix_i + \sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j \rightarrow \min, $$ where $x_i \in \{0;1\}$ and $a_{ij},b_{i} \in \mathbb{R}$, an Ising Hamiltonian has form $$ \sum_{i=1}^n b_iZ_i + \sum_{i=1}^n\sum_{j=1}^na_{ij}Z_i\otimes Z_j, $$ where $Z_i$ is $Z$-gate applied on $i$th qubit while identity operators are applied on other qubits.

As you can see in the equation for a QUBO task, it is a polynom of second order. Ising Hamiltonian describes at maximum two-body interaction. So, there is a clear resemblance between both expression. As a result, finding minimum of QUBO task can be translated to finding a ground state of Ising Hamiltonian.

Concerning the base Hamiltonian in your question. The ground state of this Hamiltonian is well known, it is a equally distributed superposition of $n$ qubits, i.e. $\frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}|i\rangle$. This superposition can be prepared easily. As a result, a quantum annealer is in ground state at the beginning. Then the Hamiltonian of the system is slowly changed to Ising one. But the system remains in the ground state of combined Hamiltonian (base + Ising) - this is known as adiabatic theorem. In the end, the system is described by Ising Hamiltonian only and it is still in the ground state . This means that you have found minimum of the QUBO taks equivalent to the Ising Hamiltonian.

You can learn more in paper Ising formulations of many NP problems.


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.