QAOA for TSP on QISKIT

[VIta197]

Dear Github Community,

I'm brand new to quantum computing. In particular, I looked at Qiskit and, in this regard, especially the mathematical backgrounds. I also tried to understand common algorithms. I find the QAOA Algortihmus particularly interesting. This is also very easy to understand for the MAXCUT problem.

But now I wanted to dedicate myself to the TSP. Unfortunately I don't find any clues for the QAOA algortihmus. That's why I wanted to ask if anyone had any ideas that I could use as a guide.

I find this platform very interesting, and I would also like to thank you for it.

Best regards

[woodsp-ibm]

Hi, you can look at this tutorial https://qiskit.org/documentation/optimization/tutorials/06_examples_max_cut_and_tsp.html which shows TSP. You should be easily able to switch out VQE there for QAOA.

I will note that Aqua is now deprecated and it contents have been moved elsewhere. Core algorithms, including QAOA went to qiskit-terra, and the optimization logic here, that included TSP, was moved to qiskit-optimization where the above tutorial exists, though I linked you to the published version of it in our documentation; the original is in the folder here if you want it https://github.com/Qiskit/qiskit-optimization/tree/master/docs/tutorials

Hope this helps.

[VIta197]

Good afternoon dear community. And many thanks to "woodsp-ibm".

My experiment now looks like this:

import networkx as nx
import numpy as np

from qiskit import Aer
from qiskit.aqua import aqua_globals, QuantumInstance
from qiskit.aqua.algorithms import QAOA, VQE, NumPyMinimumEigensolver
from qiskit.aqua.components.optimizers import SPSA, COBYLA
from qiskit.optimization.applications.ising.common import sample_most_likely
from qiskit.optimization.applications.ising import tsp
#from qiskit.optimization.converters import IsingToQuadraticProgram
from qiskit.optimization.problems import QuadraticProgram
from qiskit.optimization.algorithms import MinimumEigenOptimizer, RecursiveMinimumEigenOptimizer

from qiskit.circuit.library import TwoLocal
import logging
from qiskit.aqua import set_qiskit_aqua_logging

n = 3
num_qubits = n ** 2
ins = tsp.random_tsp(n)
print('distance\n', ins.w)

def draw_graph(G, colors, pos):
    default_axes = plt.axes(frameon=True)
    nx.draw_networkx(G, node_color=colors, node_size=600, alpha=.8, ax=default_axes, pos=pos)
    edge_labels = nx.get_edge_attributes(    nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=edge_labels)
G, 'weight')

G = nx.Graph()
G.add_nodes_from(np.arange(0, ins.dim, 1))
colors = ['r' for node in G.nodes()]

for i in range(0, ins.dim):
    for j in range(i+1, ins.dim):
        G.add_edge(i, j, weight=ins.w[i,j])

pos = {k: v for k, v in enumerate(ins.coord)}

draw_graph(G, colors, pos)

qubitOp, offset = tsp.get_operator(ins, penalty = 1000)
print("needed Qubits: ",qubitOp.num_qubits)

qubitOp, offset = tsp.get_operator(ins)
print('Offset:', offset)
print('Ising Hamiltonian:')
print(qubitOp.print_details())

qp = QuadraticProgram()
qp.from_ising(qubitOp, offset, linear=True)
backend = quantum_instance = Aer.get_backend('qasm_simulator')
optimizer = COBYLA(maxiter=300, rhobeg=2, tol=1.5, disp=True)
qaoa_mes = QAOA(optimizer=optimizer, reps=1, quantum_instance = backend)

TypeError Traceback (most recent call last)

in ----> 1 qaoa_mes = QAOA(optimizer=optimizer, reps=1, quantum_instance = backend) 2 3 4 5 TypeError: __init__() got an unexpected keyword argument 'reps' ``` qaoa = MinimumEigenOptimizer(qaoa_mes) qaoa_result = qaoa.solve(qp) print("Result QAOA with QP: ",qaoa_result.x) if(tsp.tsp_feasible(qaoa_result.x)): print(tsp.get_tsp_solution(qaoa_result.x)) ``` ``` from itertools import permutations

def brute_force_tsp(w, N): a=list(permutations(range(1,N))) last_best_distance = 1e10 for i in a: distance = 0 pre_j = 0 for j in i: distance = distance + w[j,pre_j] pre_j = j distance = distance + w[pre_j,0] order = (0,) + i if distance < last_best_distance: best_order = order last_best_distance = distance print('order = ' + str(order) + ' Distance = ' + str(distance)) return last_best_distance, best_order

best_distance, best_order = brute_force_tsp(ins.w, ins.dim) print('Best order from brute force = ' + str(best_order) + ' with total distance = ' + str(best_distance))

def draw_tsp_solution(G, order, colors, pos): G2 = nx.DiGraph() G2.add_nodes_from(G) n = len(order) for i in range(n): j = (i + 1) % n G2.add_edge(order[i], order[j], weight=G[order[i]][order[j]]['weight']) default_axes = plt.axes(frameon=True) nx.draw_networkx(G2, node_color=colors, edge_color='b', node_size=600, alpha=.8, ax=default_axes, pos=pos) edge_labels = nx.get_edge_attributes(G2, 'weight') nx.draw_networkx_edge_labels(G2, pos, font_color='b', edge_labels=edge_labels)

draw_tsp_solution(G, best_order, colors, pos)

I now have two more questions about this. Maybe someone can help me there.

1. You can see an error message in the code above. I list them again here:

qaoa_mes = QAOA(optimizer=optimizer, reps=1, quantum_instance = backend)

> TypeError                                 Traceback (most recent call last)
> <ipython-input-65-73cb16ffa91b> in <module>
> ----> 1 qaoa_mes = QAOA(optimizer=optimizer, reps=1, quantum_instance = backend)
>       2 
>       3 
>       4 
>       5 
> 
> TypeError: __init__() got an unexpected keyword argument 'reps'

Does anyone have an idea how I can vary the variable "p", in this case "reps"? From my point of view it would be very interesting to look at the reaction of the results here.

2. Does anyone have an idea how I can finally display the resulting circuit? I mean the individual qubit strands and gates.

Thank you very much. I wish you a great weekend. And best regards.

[woodsp-ibm]

Hi, QAOA here in Aqua that variable was called p. When the code was moved to qiskit-terra it was changed to reps to be consistent with other ansatzes there which have similar layer control parameter and that is what it was called - short for repetitions. Here is the current QAOA doc for Aqua https://qiskit.org/documentation/stubs/qiskit.aqua.algorithms.QAOA.html

I will note once again that Aqua, this repository, is deprecated, meaning that we will support it for a short period longer but then it will be archived and not used. I would suggest at some point upgrading to the new version so that you are no longer using Aqua - i.e. do a pip install -U qiskit[optimzation] or pip install -U qiskit[all] where all will get you machine learning etc as well. This way you can directly run the tutorial I referenced.

You can get the circuit of QAOA if you call its construct circuit method. Once you have that you can call the quantum circuit draw() method i.e.

cct = qaoa.construct_circuit(.....
cct.draw()

[VIta197]

Thanks for your comments, it helped me a lot.

Now I have one more question. I'm sorry if this sounds a bit stupid. Am really a beginner.

How can I plot a histrogram for my results, which shows the individual routes with their probabilities / number of shots? Unfortunately I cannot find any method / attributes for this.

Edit: And was there a command in the old version that did the same as "optimizer_time" to get the execution time?

Thank you very much again!

2nd Edit: This is my result trying to plot. I think it is not the plot of the qaoa result.

[woodsp-ibm]

You can get the state of QAOA at when it completes and returns its result via result.eigenstate. This would be a state vector or dictionary of counts, the latter when you are using qasm simulator or real device.

result.optimizer_time is still there

[VIta197]

Thank you woodsp-ibm,

When I try it with the result of Qaoa, I get the following error:

qaoa_result.eigenstate

AttributeError Traceback (most recent call last)

in ----> 1 qaoa_result.eigenstate AttributeError: 'MinimumEigenOptimizationResult' object has no attribute 'eigenstate'

I think MinimumEigensolverResult has this attribute. Where Qaoa is a MinimumEigenOptimizerResult.

Is there a other option?

[woodsp-ibm]

Ok you are not running QAOA directly you are running MinimumEigenOptimizer and passing it an instance of QAOA as the MinimumEigenSolver. If you look at MinimumEigenOptimizer result you will see it has a field to retrieve the result object from the MinimumEigenSolver used, if that is of interest, which it is for you https://github.com/Qiskit/qiskit-aqua/blob/1f2c316c3a1aca1296f45241d14ad8ae5fbe2027/qiskit/optimization/algorithms/minimum_eigen_optimizer.py#L53

So qaoa_result.min_eigen_solver_result.eigenstate

[VIta197]

Thank you, woodsp-ibm!

I'm sorry, I also feel a little bad asking you all these stupid questions. But how can I then plot this result in a histogram in order to get a visual overview? Just like to see in the tutorial:

plot_histogram(qaoa_results.get_counts()) or plot_histogram(qaoa_result.min_eigen_solver_result.eigenstate.get_counts()) doesn't work.

[woodsp-ibm]

How about simply plot_histogram(qaoa_result.min_eigen_solver_result.eigenstate) The eigenstate should be a dictionary of counts already; you do not need to call get counts. Eigenstate is a vector or a counts dictionary depending on the backend type you run it on - with qasm_simulator it will be counts.

[VIta197]

Thank you so much for your help, I really appreciate it. Trying it also on my own, but the following doesn't work either. But it should actually, right?

Okay, if I do the following now, I'll get the result I want. But..

n = 3
num_qubits = n ** 2
ins = tsp.random_tsp(n)
print('distance\n', ins.w)

distance [[ 0. 79. 28.] [79. 0. 63.] [28. 63. 0.]]

brute_force_tsp(w, N): ...

order: (0, 1, 2) distance: 153.0 order: (0, 2, 1) distance: 153.0

Best order from brute force = (0, 1, 2) with total distance = 153.0

qp = QuadraticProgram()
qp.from_ising(Ising, offset, linear=True)

Ising, offset = tsp.get_operator(ins, penalty = 1e5)

backend = Aer.get_backend('qasm_simulator')
coby = COBYLA(maxiter=300, rhobeg=2, tol=1.5, disp=True)
qaoa_mes = QAOA(optimizer = coby, p = 1, quantum_instance = backend)
qaoa = MinimumEigenOptimizer(qaoa_mes)
qaoa_result = qaoa.solve(qp)

print("Result QAOA with QP: ",qaoa_result.x)
  if(tsp.tsp_feasible(qaoa_result.x)):
    quantum_route = tsp.get_tsp_solution(qaoa_result.x)
    print("means classicaly: ", quantum_route) 
    print('Route length: ', qaoa_result.fval)
    print()
    print('best order = ' + str(best_order) + ' with best distance = ' + str(best_distance))

draw_tsp_solution(G, quantum_route, colors, pos)

Result QAOA with QP: [1. 0. 0. 0. 1. 0. 0. 0. 1.] means classicaly: [0, 1, 2] Route length: 162.0

best order = (0, 1, 2) with best distance = 153.0

The rounten length is incorrect.

Stil, so far these are all results that can almost be expected. But if I now plot the eigenvector, the result is rather unsatisfactory.

from qiskit.tools.visualization import plot_histogram

plot_histogram(qaoa_result.min_eigen_solver_result.eigenstate, bar_labels = False, number_to_keep = 8, sort = 'desc')

Shouldn't the desired result crystallize out more clearly? I mean here the result that was correctly calculated above. Do you have any idea what is wrong there?

[woodsp-ibm]

I guess if it can be distinguished as the right solution you could argue its clear enough. And of course in problems there can be more than one solution. With these too its easy to validate the answer that was found to ensure its correct. Do you know whether the optimization process stopped when it found a minimum or did it stop ahead of that, maybe closeby because of maxiter of COBLYLA. You can check how many evals were done on the result.

[woodsp-ibm]

I believe this discussion is complete so I am closing this issue.