<jupyter_start><jupyter_text>Traffic Flow Optimization with XYmixer on QAOAThe traffic optimization problem is one of the most famous optimization problems in quantum computing.  ReferencesTraffic flow optimization using a quantum annealer  <NAME>, <NAME>, <NAME>, <NAME>, <NAME>, <NAME>   https://arxiv.org/abs/1708.01625  ExampleConsider a network of 9 intersections and 12 streets.<jupyter_code>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()<jupyter_output><empty_output><jupyter_text>2 Cars and 3 possible routes for each carNow 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 levelThe 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 $(Q0+Q2+Q3+Q5)^2$. The whole cost is,$$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$$<jupyter_code>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<jupyter_output><empty_output><jupyter_text>Hard constraintsThere 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<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>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<jupyter_code>result.circuit.run(backend="draw")<jupyter_output><empty_output><jupyter_text>Solve using IonQ and Rigetti<jupyter_code>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)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15893243568165424, 'fraction_numerical': 0.06828564558788171, 'mean_word_length': 5.753246753246753, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 27, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '282695', 'license': 'Apache-2.0', 'n_tokens_mistral': 1750, 'n_tokens_neox': 1630, 'n_words': 483, 'path': 'tutorial/316_trafficflow.ipynb', 'repo_name': 'Blueqat/blueqat-tutorials', 'size': '4213'}