@yuichirominato 2019.02.13更新 52views

[QAOA]QAOA+maxcut


Introduction

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

Steps

Steps is very simple.

  1. prepare the problem
  2. mapping the problem on the ising model
  3. use QAOA to solve ising model
  4. set params for the accuracy
  5. 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
$

Programming with blueqat

Installing is easy just command on the terminal,

pip install blueqat

Or you can get from here.
https://github.com/mdrft/Blueqat

import vqe and pauli module from blueqat

Write the ising hamiltonian on Z operator and decide the params on accuracy. Finally adopt vqe/qaoa algrithm.

from blueqat import vqe
from blueqat.pauli import *

hamiltonian = 0.5*Z[0]*Z[1]+0.5*Z[0]*Z[3]+0.5*Z[1]*Z[2]+0.5*Z[2]*Z[3]+0.5*Z[3]*Z[4]+0.5*Z[2]*Z[4]
step = 2

result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step)).run()
print(result.most_common(12))


(((1, 0, 1, 0, 1), 0.0875936132919655), ((1, 0, 1, 0, 0), 0.0875936132919655), ((0, 1, 0, 1, 1), 0.0875936132919655), ((0, 1, 0, 1, 0), 0.0875936132919655), ((1, 0, 1, 1, 0), 0.07344565024381726), ((0, 1, 0, 0, 1), 0.07344565024381726), ((1, 0, 0, 0, 1), 0.07344565024381723), ((0, 1, 1, 1, 0), 0.07344565024381723), ((0, 0, 1, 1, 0), 0.06382328839510434), ((1, 1, 0, 0, 1), 0.06382328839510434), ((1, 0, 0, 1, 0), 0.026885288693200914), ((0, 1, 1, 0, 1), 0.026885288693200914))

Finally we get the best answer with least cost. The simulator can get the state vector instead of the sampling method.

It is solved.

1,0,1,0,1
1,0,1,0,0
0,1,0,1,1
0,1,0,1,0

These 4 are answers.

Recommend


CONTACT

info@mdrft.com

Back To Top

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方