Let’s solve maxcut problem using QAOA algorithm on universal gate model quantum computer (simulator).

Steps

Steps is very simple.

prepare the problem

mapping the problem on the ising model

use QAOA to solve ising model

set params for the accuracy

check the answer. if you are using simulator you have option to check the state vector.

What is ising model?

Ising model is physics based mode to solve optimization problem.

What is QAOA?

QAOA is adiabatic quantum computation inspired quantum algorithm to solve classical optimization problem.

What is VQE?

This time we are using VQE with QAOA to find out the global minimum with variational principle. We are using quantum and classical hybrid system for solving the problem.

Example

Let’s think about maxcut prbolem.

We solve 5 nodes of maxcut problem on the network. To make 2 groups of the nodes, we find the maximum cut between 2 groups.

The cost function is,

$H = -\sum_{i,j} \frac{1}{2}(1-q_iq_j)$

We have 5 nodes.

$ H = -\frac{1}{2}\bigl[(1-q_0q_1)+(1-q_0q_3)+(1-q_1q_2)+(1-q_2q_3)+(1-q_3q_4)+(1-q_2q_4) \bigr]\\ =\frac{1}{2}(q_0q_1+q_0q_3+q_1q_2+q_2q_3+q_3q_4+q_2q_4)-3 $