common.title

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

Yuichiro Minato 14 days ago

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

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

参考文献

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の順番に通りを通ります。

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

車2の経路探索 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+(Q1Q4)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

ハード制約

取りうる経路は1台の車につき1つです。これを実現するのはハード制約と呼ばれる制約条件です。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>