common.title
Cloud support

Nobisuke

Dekisugi

RAG

autoQAOA
RAG for dev
Fortune telling app
Annealing
DEEPSCORE
Translation
Overview
Service overview
Terms of service

Privacy policy

Contact
Research
Sign in
Sign up
common.title

量子コンピュータでQAOAとミキサーを使った交通最適化（簡略化版）

Yuichiro Minato

2022/05/14 01:15

ミキサーを使った交通最適化（簡略化版）

コードが短くなったので再掲します。

参考文献

Traffic flow optimization using a quantum annealer
Florian Neukart, Gabriele Compostella, Christian Seidel, David von Dollen, Sheir Yarkoni, Bob Parney
https://arxiv.org/abs/1708.01625

例題

9つの交差点と12本の通りがあるモデルを考えます。0地点から8地点へ車を渋滞させずに経路最適をします。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_nodes_from([i for i in range(9)])
G.add_edges_from([[0,1],(1,2),(0,3),(1,4),(2,5),(3,4),(4,5),(3,6),(4,7),(5,8),(6,7),(7,8)])
options = {'node_size': 1200,'with_labels':'True'}
pos = nx.spring_layout(G)
nx.draw(G, pos, **options, node_color='#efefef')

edge_labels={(0,1):'s0',(1,2):'s1',(0,3):'s2',(1,4):'s3',(2,5):'s4',(3,4):'s5',(4,5):'s6',(3,6):'s7',(4,7):'s8',(5,8):'s9',(6,7):'s10',(7,8):'s11'}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
<Figure size 432x288 with 1 Axes>output

2台の車、3つの経路を設定

こちらで提案経路を自動車ごとに設定します。それぞれ適当にきめます。たとえば、Q0はs0,s3,s8,s11の順番に通りを通ります。

車１の経路探索 Q0 : s0,s3,s8,s11
Q1 : s2,s7,s10,s11
Q2 : s0,s1,s4,s9

車２の経路探索 Q3 : s0,s3,s8,s11
Q4 : s2,s7,s10,s11
Q5 : s0,s1,s4,s9

渋滞混雑を設定します

渋滞の混雑具合は経路の出現回数によって計算します。たとえば、s0の混雑は、(Q0+Q2+Q3+Q5)2(Q0+Q2+Q3+Q5)^2と計算できます。すべての道の混雑度を合計して全体の混雑を求めます。

H=(Q0+Q2+Q3+Q5)2+(Q2+Q5)2+(Q1+Q4)2+(Q0+Q3)2+(Q2+Q5)2+(Q1∗Q4)2+(Q0+Q3)2+(Q2+Q5)2+(Q1+Q4)2+(Q0+Q1+Q3+Q4)2H = (Q0+Q2+Q3+Q5)^2 + (Q2+Q5)^2 + (Q1+Q4)^2 + (Q0+Q3)^2 + (Q2+Q5)^2 + (Q1*Q4)^2 + (Q0+Q3)^2 + (Q2+Q5)^2 + (Q1+Q4)^2 + (Q0+Q1+Q3+Q4)^2

blueqatでは、このまま式を実装して終わりです。

from blueqat.pauli import qubo_bit as q

hamiltonian = (q(0)+q(2)+q(3)+q(5))**2 + (q(2)+q(5))**2 + (q(1)+q(4))**2 + (q(0)+q(3))**2 + (q(2)+q(5))**2 + (q(1)*q(4))**2 + (q(0)+q(3))**2 + (q(2)+q(5))**2 + (q(1)+q(4))**2 + (q(0)+q(1)+q(3)+q(4))**2

ハード制約

取りうる経路は１台の車につき１つです。これを実現するのはハード制約と呼ばれる制約条件です。XYmixerを利用すると、Q0,Q1,Q2から一つ。Q3,Q4,Q5から一つとハード制約を作ることができます。

Quantum Alternating Operator Ansatz

式の実装です。先ほどの混雑度の式に加え、XYmixerを利用したハード制約を実装します。

from blueqat import vqe, Circuit
from blueqat.pauli import X, Y

step = 4

#mixer and init state
mixer = 0.5*X[0]*X[1] + 0.5*Y[0]*Y[1] + 0.5*X[1]*X[2] + 0.5*Y[1]*Y[2] + 0.5*X[2]*X[0] + 0.5*Y[2]*Y[0]
mixer += 0.5*X[3]*X[4] + 0.5*Y[3]*Y[4] + 0.5*X[4]*X[5] + 0.5*Y[4]*Y[5] + 0.5*X[5]*X[3] + 0.5*Y[5]*Y[3]
init = Circuit(6).x[0].x[3]

result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step, init, mixer)).run()
result.most_common(10)
(((0, 1, 0, 0, 0, 1), 0.4434926334413086),

 ((0, 0, 1, 0, 1, 0), 0.4434926334413085),

 ((0, 1, 0, 1, 0, 0), 0.035112578038535035),

 ((1, 0, 0, 0, 1, 0), 0.035112578038535),

 ((0, 0, 1, 1, 0, 0), 0.014419387138927743),

 ((1, 0, 0, 0, 0, 1), 0.014419387138927736),

 ((0, 0, 1, 0, 0, 1), 0.007406870192776883),

 ((1, 0, 0, 1, 0, 0), 0.004346020684804994),

 ((0, 1, 0, 0, 1, 0), 0.002197911884856614),

 ((0, 1, 1, 0, 0, 1), 9.754608247073196e-32))

これで終わりです。制約を満たしながら解を導いています。

result.circuit.run(backend="draw")
<Figure size 1800x7560 with 1 Axes>output

IonQ や Rigetti へのタスクの投入

from bqcloud import load_api
from blueqat import Circuit
from bqcloud import Device

api = load_api()

# Circuit, Device, Number of shots, Group name(Optional) for IonQ
task_ionq = api.execute(result.circuit, Device.IonQDevice, 10)

# Circuit, Device, Number of shots, Group name(Optional) for Rigetti
task_rigetti = api.execute(result.circuit, Device.Aspen11, 10)

© 2024, blueqat Inc. All rights reserved