量子コンピュータで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>

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$ と計算できます。すべての道の混雑度を合計して全体の混雑を求めます。

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)^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>

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)