Traffic Flow Optimization with XYmixer on QAOA
Yuichiro Minato
2022/01/30 17:45
Traffic Flow Optimization with XYmixer on QAOA
The traffic optimization problem is one of the most famous optimization problems in quantum computing.
References
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
Example
Consider a network of 9 intersections and 12 streets.
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 Cars and 3 possible routes for each car
Now there are two cars, going from point 0 to point 8. We propose three routes for each car to take, and consider the cost of each route to be counted as congestion if the cars take the same street. Then assign a qubit to each proposed route from Q0 to Q5.
route for car1
Q0 : s0,s3,s8,s11
Q1 : s2,s7,s10,s11
Q2 : s0,s1,s4,s9
route for car2
Q3 : s0,s3,s8,s11
Q4 : s2,s7,s10,s11
Q5 : s0,s1,s4,s9
Calculation of congestion level
The level of congestion is determined by whether the street appears within the proposed route or not. We can calculate the congestion for the roads from s0 to s11 and add them together to get the overall congestion level. For example, s0 appears in Q0, Q2, Q3, and Q5 of the proposed routes, so the cost is . The whole cost is,
Expanding the expression and substituting the value with a binary rule yields
from sympy import *
Q0 = Symbol('Q0')
Q1 = Symbol('Q1')
Q2 = Symbol('Q2')
Q3 = Symbol('Q3')
Q4 = Symbol('Q4')
Q5 = Symbol('Q5')
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
H = expand(H)
H = H.subs(Q0**2, Q0)
H = H.subs(Q1**2, Q1)
H = H.subs(Q2**2, Q2)
H = H.subs(Q3**2, Q3)
H = H.subs(Q4**2, Q4)
H = H.subs(Q5**2, Q5)
H2*Q0*Q1 + 2*Q0*Q2 + 8*Q0*Q3 + 2*Q0*Q4 + 2*Q0*Q5 + 4*Q0 + 2*Q1*Q3 + 7*Q1*Q4 + 3*Q1 + 2*Q2*Q3 + 8*Q2*Q5 + 4*Q2 + 2*Q3*Q4 + 2*Q3*Q5 + 4*Q3 + 3*Q4 + 4*Q5Now the Hamiltonian is ready. We use QAOA to find the expectation value of the minimum of this equation.
Hard constraints
There is one constraint that must be observed here. That is the constraint that each car should choose only one route. This can be easily solved by using XYmixer. The XYmixer is a Hamiltonian that determines how the problem is explored; the search is performed in such a way that the 01 and 10 state vectors are swapped. Here, car 1 and car 2 choose only one of the three routes, so only one of the three qubits, Q0, Q1, Q2, will be 1 and the rest will be 0. Likewise, only one of the qubits Q3, Q4, and Q5 will be 1. To maintain this state, a mechanism for exchanging qubits, called 2opt, is used. For the initial state, choose any state that satisfies the constraints.
Quantum Alternating Operator Ansatz
from blueqat import vqe, Circuit
from blueqat.pauli import X, Y
from blueqat.pauli import qubo_bit as q
hamiltonian = 2*q(0)*q(1)+2*q(0)*q(2)+8*q(0)*q(3)+2*q(0)*q(4)+2*q(0)*q(5)+4*q(0)+2*q(1)*q(3)+7*q(1)*q(4)+3*q(1)+2*q(2)*q(3)+8*q(2)*q(5)+4*q(2)+2*q(3)*q(4)+2*q(3)*q(5)+4*q(3)+3*q(4)+4*q(5)
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.37291765538289845),
((0, 0, 1, 0, 1, 0), 0.3729176553828979),
((0, 0, 1, 1, 0, 0), 0.08145920498348241),
((1, 0, 0, 0, 0, 1), 0.0814592049834823),
((1, 0, 0, 1, 0, 0), 0.02375992120568354),
((0, 1, 0, 0, 1, 0), 0.022701464389553148),
((0, 0, 1, 0, 0, 1), 0.017478879274962108),
((0, 1, 0, 1, 0, 0), 0.013653007198510678),
((1, 0, 0, 0, 1, 0), 0.013653007198510647),
((0, 0, 0, 0, 1, 0), 1.1219347803421538e-31))In the end, the combination of either Q2 and Q4 or Q1 and Q5 resulted in the least congestion. These solutions are considered correct because they do not go through the same road
Solve using IonQ and 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