Help us understand the problem. What is going on with this article?

QAOAで社会問題

はじめに

前回まではQAOAの使い方を確認しました。イジングモデルでは-1と+1を変数として使いますが、QUBOでは0と1を使うため、より産業利用に近いです。

「量子コンピュータの量子ゲートで組合せ最適、2020年2月まとめ(QAOA/VQE使い方もフォロー)」
https://qiita.com/YuichiroMinato/items/9b167190b582acd22694

おさらい

おさらいです。

blueqatのインストール

pip install blueqat

です。

QAOA使い方

from strangeworks.blueqat import StrangeworksBackend #quantumcomputing.comを利用する時に必要

from blueqat import vqe
from blueqat.pauli import qubo_bit as q

cost = -3*q(0)-3*q(1)-2*q(0)*q(1)
step = 2

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

ツールを読み込み、定式化をしてステップ数を決め、実行します。今回はこのcostにあたる定式化をみてみます。

交通最適化

交通最適化は度々出てくるテーマです。

youtubeでは、
交通最適化
https://www.youtube.com/watch?v=JU2omOzuOQg

がわかりやすいです。記事は、

「D-WaveでVW社の交通最適化アプリケーションの実装を解く」
https://qiita.com/YuichiroMinato/items/19dd89e381f14ad24134

「交通最適化問題を量子アニーリングで解く」
https://qiita.com/sychocola1/items/646d2c9504e34ed1589f

今回は、交通最適をときます。やることは、

1、1台の車に3つのルート選択を許容する(古典)
2、現在の選択ルートから混雑状況を計算(古典)
3、混雑度を最小にするようにルート選択を最小化(QAOA)

となります。問題は使い回しをして、上記のリンクから。

「Quantum Computing at Volkswagen:
Traffic Flow Optimization using the D-Wave Quantum Annealer」
引用:https://www.dwavesys.com/sites/default/files/VW.pdf

一つ目は混雑度をコスト関数として、

(q_0+q_1+q_3+q_4)^2+(q_0+q_1+q_3+q_4)^2+(q_0+q_3)^2+(q_0+q_3)^2+(q_1+q_4)^2+(q_1+q_2+q_4+q_5)^2+(q_2+q_5)^2+(q_2+q_5)^2+(q_2+q_5)^2\\ 
=2(q_0+q_1+q_3+q_4)^2+2(q_0+q_3)^2+(q_1+q_4)^2+(q_1+q_2+q_4+q_5)^2+3(q_2+q_5)^2\\ 
=4q_0^2+4q_0q_1+8q_0q_3+4q_0q_4+4q_1^2+2q_1q_2+4q_1q_3+8q_1q_4+2q_1q_5+4q_2^2 +2q_2q_4+8q_2q_5+4q_3^2+4q_3q_4+4q_4^2+2q_4q_5+4q_5^2\\
=4q_0+4q_0q_1+8q_0q_3+4q_0q_4+4q_1+2q_1q_2+4q_1q_3+8q_1q_4+2q_1q_5+4q_2 +2q_2q_4+8q_2q_5+4q_3+4q_3q_4+4q_4+2q_4q_5+4q_5

3つのルートのうちに1つをえらぶ制約条件をこちらに、

K(q_0+q_1+q_2-1)^2+K(q_3+q_4+q_5-1)^2 = -Kq_0+2Kq_0q_1+2Kq_0q_2-Kq_1+2Kq_1q_2-Kq_2-Kq_3+2Kq_3q_4+2Kq_3q_5-Kq_4+2Kq_4q_5-Kq_5+2K
from blueqat import vqe
from blueqat.pauli import qubo_bit as q

K=2
cost2 = -K*q(0)+2*K*q(0)*q(1)+2*K*q(0)*q(2)-K*q(1)+2*K*q(1)*q(2)-K*q(2)-K*q(3)+2*K*q(3)*q(4)+2*K*q(3)*q(5)-K*q(4)+2*K*q(4)*q(5)-K*q(5)

step = 4

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

この二つを繋げてQUBO式とします。

そして、実行します。

from strangeworks.blueqat import StrangeworksBackend #quantumcomputing.comを利用する時に必要

from blueqat import vqe
from blueqat.pauli import qubo_bit as q

K=10
cost1 = 4*q(0)+4*q(0)*q(1)+8*q(0)*q(3)+4*q(0)*q(4)+4*q(1)+2*q(1)*q(2)+4*q(1)*q(3)+8*q(1)*q(4)+2*q(1)*q(5)+4*q(2)+2*q(2)*q(4)+8*q(2)*q(5)+4*q(3)+4*q(3)*q(4)+4*q(4)+2*q(4)*q(5)+4*q(5)
cost2 = -K*q(0)+2*K*q(0)*q(1)+2*K*q(0)*q(2)-K*q(1)+2*K*q(1)*q(2)-K*q(2)-K*q(3)+2*K*q(3)*q(4)+2*K*q(3)*q(5)-K*q(4)+2*K*q(4)*q(5)-K*q(5)

step = 8

result = vqe.Vqe(vqe.QaoaAnsatz(cost1+cost2, step)).run()
print(result.most_common(12))

なかなか答えが出ませんが、、、、

(((0, 1, 0, 0, 0, 1), 0.12986970172628198), ((0, 0, 1, 0, 1, 0), 0.1298697017262819), ((0, 0, 0, 0, 0, 0), 0.08232027492914641), ((0, 1, 0, 0, 1, 0), 0.05463053577530196), ((0, 0, 0, 1, 0, 0), 0.04609411831952029), ((1, 0, 0, 0, 0, 0), 0.04609411831952023), ((0, 0, 1, 1, 0, 1), 0.037740176136034545), ((1, 0, 1, 0, 0, 1), 0.0377401761360345), ((1, 0, 0, 0, 1, 1), 0.03131986281902896), ((0, 1, 1, 1, 0, 0), 0.031319862819028946), ((0, 0, 1, 0, 0, 1), 0.03071276141604334), ((1, 0, 0, 1, 0, 0), 0.02140326399538612))

うまくいけば制約条件を満たす解を与えます。

タンパク質折りたたみ

ハミルトニアンは下記です。

H = −q2 + 8q1q2 + 15q2q3 − 18q1q2q3 − 3q1q4 + 12q1q2q4 + 4q3q4 + 3q1q3q4 − 6q2q3q4 − 12q1q2q3q4 + 4q2q5 + 3q1q2q5 − 15q2q3q5 + 15q4q5 + 3q1q4q5 − 6q2q4q5 − 12q1q2q4q5 − 15q3q4q5 + 28q2q3q4q5 − 2q1q2q6 − 4q3q6 + 2q2q3q6 + 13q1q2q3q6 − 2q1q4q6 + 4q1q2q4q6 + 2q3q4q6 + 13q1q3q4q6 + 4q2q3q4q6 − 37q1q2q3q4q6 + 7q5q6 + 2q2q5q6 + 13q1q2q5q6 + 4q3q5q6 + 9q2q3q5q6 − 33q1q2q3q5q6 − 20q4q5q6 + 13q1q4q5q6 + 4q2q4q5q6 − 37q1q2q4q5q6 + 9q3q4q5q6 − 33q1q3q4q5q6 − 37q2q3q4q5q6 + 99q1q2q3q4q5q6 − 4q2q7 + 4q2q3q7 + 7q4q7 + 2q2q4q7 + 13q1q2q4q7 + 4q3q4q7 + 9q2q3q4q7 − 33q1q2q3q4q7 + 4q2q5q7 − 18q4q5q7 + 9q2q4q5q7 − 33q1q2q4q5q7 − 33q2q3q4q5q7 + 62q1q2q3q4q5q7 + 7q6q7 + 2q2q6q7 + 13q1q2q6q7 + 4q3q6q7 + 9q2q3q6q7 − 33q1q2q3q6q7 − 20q4q6q7 + 13q1q4q6q7 + 4q2q4q6q7 − 37q1q2q4q6q7 + 9q3q4q6q7 − 33q1q3q4q6q7 − 37q2q3q4q6q7 + 99q1q2q3q4q6q7 − 18q5q6q7 + 9q2q5q6q7 − 33q1q2q5q6q7 − 33q2q3q5q6q7 + 62q1q2q3q5q6q7 + 53q4q5q6q7 − 33q1q4q5q6q7 − 37q2q4q5q6q7 + 99q1q2q4q5q6q7 − 33q3q4q5q6q7 + 62q1q3q4q5q6q7 + 99q2q3q4q5q6q7 − 190q1q2q3q4q5q6q7

これをイジング式に落として、

from blueqat.vqe import *
from blueqat.pauli import *

hamiltonian = 5.890625*I - 0.15625*Z[0]*Z[1] + 2.890625*Z[0]*Z[1]*Z[2] - 0.359375*Z[0]*Z[1]*Z[2]*Z[3] - 1.03125*Z[0]*Z[1]*Z[2]*Z[3]*Z[4] + 0.0625*Z[0]*Z[1]*Z[2]*Z[3]*Z[4]*Z[5] + 1.484375*Z[0]*Z[1]*Z[2]*Z[3]*Z[4]*Z[5]*Z[6] - 0.515625*Z[0]*Z[1]*Z[2]*Z[3]*Z[4]*Z[6] - 0.453125*Z[0]*Z[1]*Z[2]*Z[3]*Z[5] + 0.0625*Z[0]*Z[1]*Z[2]*Z[3]*Z[5]*Z[6] + 0.96875*Z[0]*Z[1]*Z[2]*Z[4] - 0.515625*Z[0]*Z[1]*Z[2]*Z[4]*Z[5]*Z[6] - 0.453125*Z[0]*Z[1]*Z[2]*Z[4]*Z[6] + 0.171875*Z[0]*Z[1]*Z[2]*Z[5] - 0.0625*Z[0]*Z[1]*Z[2]*Z[6] + 0.34375*Z[0]*Z[1]*Z[3] - 0.359375*Z[0]*Z[1]*Z[3]*Z[4] - 0.453125*Z[0]*Z[1]*Z[3]*Z[4]*Z[5] + 0.0625*Z[0]*Z[1]*Z[3]*Z[4]*Z[5]*Z[6] - 0.0625*Z[0]*Z[1]*Z[3]*Z[5] - 0.453125*Z[0]*Z[1]*Z[3]*Z[5]*Z[6] + 0.171875*Z[0]*Z[1]*Z[3]*Z[6] + 0.265625*Z[0]*Z[1]*Z[4] + 0.171875*Z[0]*Z[1]*Z[4]*Z[5] - 0.0625*Z[0]*Z[1]*Z[4]*Z[6] + 0.171875*Z[0]*Z[1]*Z[5]*Z[6] + 0.109375*Z[0]*Z[1]*Z[6] - 2.796875*Z[0]*Z[2] + 0.265625*Z[0]*Z[2]*Z[3] + 0.96875*Z[0]*Z[2]*Z[3]*Z[4] - 0.515625*Z[0]*Z[2]*Z[3]*Z[4]*Z[5]*Z[6] - 0.453125*Z[0]*Z[2]*Z[3]*Z[4]*Z[6] + 0.171875*Z[0]*Z[2]*Z[3]*Z[5] - 0.0625*Z[0]*Z[2]*Z[3]*Z[6] - 0.90625*Z[0]*Z[2]*Z[4] - 0.0625*Z[0]*Z[2]*Z[4]*Z[5] - 0.453125*Z[0]*Z[2]*Z[4]*Z[5]*Z[6] + 1.421875*Z[0]*Z[2]*Z[4]*Z[6] + 0.109375*Z[0]*Z[2]*Z[5] - 0.0625*Z[0]*Z[2]*Z[5]*Z[6] + 0.125*Z[0]*Z[2]*Z[6] - 0.28125*Z[0]*Z[3] + 0.265625*Z[0]*Z[3]*Z[4] + 0.171875*Z[0]*Z[3]*Z[4]*Z[5] - 0.0625*Z[0]*Z[3]*Z[4]*Z[6] + 0.171875*Z[0]*Z[3]*Z[5]*Z[6] + 0.109375*Z[0]*Z[3]*Z[6] - 0.171875*Z[0]*Z[4] + 0.109375*Z[0]*Z[4]*Z[5] - 0.0625*Z[0]*Z[4]*Z[5]*Z[6] + 0.125*Z[0]*Z[4]*Z[6] + 0.0625*Z[0]*Z[5] + 0.109375*Z[0]*Z[5]*Z[6] - 0.390625*Z[0]*Z[6] + 0.09375*Z[0] - 0.15625*Z[1]*Z[2] + 0.34375*Z[1]*Z[2]*Z[3] + 2.140625*Z[1]*Z[2]*Z[3]*Z[4] - 0.453125*Z[1]*Z[2]*Z[3]*Z[4]*Z[5] + 0.0625*Z[1]*Z[2]*Z[3]*Z[4]*Z[5]*Z[6] - 0.0625*Z[1]*Z[2]*Z[3]*Z[5] - 0.453125*Z[1]*Z[2]*Z[3]*Z[5]*Z[6] - 0.078125*Z[1]*Z[2]*Z[3]*Z[6] + 0.265625*Z[1]*Z[2]*Z[4] - 0.078125*Z[1]*Z[2]*Z[4]*Z[5] - 0.0625*Z[1]*Z[2]*Z[4]*Z[6] - 0.078125*Z[1]*Z[2]*Z[5]*Z[6] + 0.109375*Z[1]*Z[2]*Z[6] - 0.921875*Z[1]*Z[3] + 0.34375*Z[1]*Z[3]*Z[4] - 0.0625*Z[1]*Z[3]*Z[4]*Z[5] - 0.453125*Z[1]*Z[3]*Z[4]*Z[5]*Z[6] - 0.078125*Z[1]*Z[3]*Z[4]*Z[6] + 1.234375*Z[1]*Z[3]*Z[5] - 0.0625*Z[1]*Z[3]*Z[5]*Z[6] - 0.28125*Z[1]*Z[4] - 0.078125*Z[1]*Z[4]*Z[5]*Z[6] + 0.109375*Z[1]*Z[4]*Z[6] + 0.234375*Z[1]*Z[5] + 0.0625*Z[1]*Z[6] - 3.046875*Z[1] - 0.28125*Z[2]*Z[3] + 0.265625*Z[2]*Z[3]*Z[4] - 0.078125*Z[2]*Z[3]*Z[4]*Z[5] - 0.0625*Z[2]*Z[3]*Z[4]*Z[6] - 0.078125*Z[2]*Z[3]*Z[5]*Z[6] + 0.109375*Z[2]*Z[3]*Z[6] - 2.171875*Z[2]*Z[4] + 0.109375*Z[2]*Z[4]*Z[5] - 0.0625*Z[2]*Z[4]*Z[5]*Z[6] + 0.125*Z[2]*Z[4]*Z[6] + 0.0625*Z[2]*Z[5] + 0.109375*Z[2]*Z[5]*Z[6] + 0.359375*Z[2]*Z[6] + 0.09375*Z[2] - 0.28125*Z[3]*Z[4] + 2.671875*Z[3]*Z[4]*Z[5]*Z[6] + 0.109375*Z[3]*Z[4]*Z[6] - 2.515625*Z[3]*Z[5] + 0.0625*Z[3]*Z[6] - 0.671875*Z[3] + 0.0625*Z[4]*Z[5] + 0.109375*Z[4]*Z[5]*Z[6] - 2.390625*Z[4]*Z[6] + 0.21875*Z[4] + 0.0625*Z[5]*Z[6] - 0.203125*Z[5] - 0.125*Z[6]

result = Vqe(QaoaAnsatz(hamiltonian,8)).run()    
print(result.most_common(10))

答えは、

(((0, 0, 0, 1, 0, 1, 1), 0.0526207005085115), ((0, 1, 0, 1, 0, 1, 1), 0.0509613913647074), ((0, 0, 1, 0, 1, 0, 0), 0.04083238349765797), ((0, 1, 0, 1, 0, 1, 0), 0.03858710306550349), ((1, 0, 1, 0, 0, 1, 0), 0.03797289965489858), ((1, 0, 0, 0, 0, 0, 1), 0.03159655384832289), ((1, 1, 1, 0, 1, 0, 0), 0.028299534909668748), ((1, 0, 0, 0, 0, 0, 0), 0.026228368428091498), ((1, 0, 1, 1, 1, 1, 0), 0.025016295668237147), ((1, 1, 1, 0, 1, 0, 1), 0.02392454173189753))
313.90521216392517

まとめ

QAOAは結構大変そうです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした