Solving TSP as Binary Quadratic Model
Even if it is not the most suitable problem for it, it is possible to define the Travel Salesman Problem using qlasskit, and solve it using a quantum annealer (or a simulator).
The first thing we are going to do is to define our oracle function, that given a distance matrix and a list of point to visit, returns the sum of distances between points visited. The distance matrix is passed as Parameter, so we can use the same function for any matrix.
from qlasskit import qlassf, Parameter, Qlist, Qmatrix, Qint
@qlassf
def tsp(
dst_matrix: Parameter[Qmatrix[Qint[3], 3, 3]], order: Qlist[Qint[2], 3]
) -> Qint[4]:
dst_sum = Qint4(0)
assertion = False
if sum(order) != 3:
assertion = True
for i in range(len(order) - 1):
oim = order[i]
oi = order[i + 1]
dst_sum += dst_matrix[oim][oi] if not assertion else 0xF
return dst_sum
After that, we bind the dst_matrix parameter with a real distance matrix; we put 0xF in the diagonal in order to avoid point repetition.
dst_matrix = [
[0xF, 2, 4],
[2, 0xF, 1],
[4, 1, 0xF],
]
tsp_f = tsp.bind(dst_matrix=dst_matrix)
This is the representation of the distance matrix using networkx and matplotlib.
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
G = nx.Graph()
for i in range(len(dst_matrix)):
for j in range(i + 1, len(dst_matrix)):
if dst_matrix[i][j] != 0:
G.add_edge(i, j, weight=dst_matrix[i][j])
plt.figure(figsize=(6, 6))
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_color="#3333ee", node_size=900)
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_labels(G, pos)
edge_labels = nx.get_edge_attributes(G, "weight")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.axis("off")
plt.show()
Calling to_bqm, we translate the qlassf function into a bqm model.
bqm = tsp_f.to_bqm()
print("Vars:", bqm.num_variables, "\nInteractions:", bqm.num_interactions)
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/qlasskit/bqm.py:68, in to_bqm(args, returns, exprs, fmt)
67 try:
---> 68 from pyqubo import AndConst, Binary, NotConst, OrConst, XorConst
69 except:
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/pyqubo/__init__.py:6
5 from pyqubo.utils.asserts import *
----> 6 from pyqubo.utils.solver import *
7 from .array import *
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/pyqubo/utils/solver.py:15
1 # Copyright 2018 Recruit Communications Co., Ltd.
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
(...) 12 # See the License for the specific language governing permissions and
13 # limitations under the License.
---> 15 import neal
16 import numpy as np
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/neal/__init__.py:15
1 # Copyright 2018 D-Wave Systems Inc.
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
(...) 12 # See the License for the specific language governing permissions and
13 # limitations under the License.
---> 15 from neal.sampler import *
16 import neal.sampler
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/neal/sampler.py:15
1 # Copyright 2018 D-Wave Systems Inc.
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
(...) 12 # See the License for the specific language governing permissions and
13 # limitations under the License.
---> 15 from dwave.samplers.sa.sampler import Neal, SimulatedAnnealingSampler, default_beta_range
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/dwave/samplers/__init__.py:19
17 from dwave.samplers.greedy import *
---> 19 from dwave.samplers.random import *
21 from dwave.samplers.sa import *
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/dwave/samplers/random/__init__.py:15
1 # Copyright 2022 D-Wave Systems Inc.
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
(...) 12 # See the License for the specific language governing permissions and
13 # limitations under the License.
---> 15 from dwave.samplers.random.sampler import *
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/dwave/samplers/random/sampler.py:22
20 import numpy as np
---> 22 from dwave.samplers.random.cyrandom import sample
25 __all__ = ['RandomSampler']
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/dwave/samplers/random/cyrandom.pyx:1, in init dwave.samplers.random.cyrandom()
AttributeError: module 'numpy.random.bit_generator' has no attribute 'SeedlessSequence'
During handling of the above exception, another exception occurred:
Exception Traceback (most recent call last)
Cell In[4], line 1
----> 1 bqm = tsp_f.to_bqm()
2 print("Vars:", bqm.num_variables, "\nInteractions:", bqm.num_interactions)
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/qlasskit/qlassfun.py:273, in QlassF.to_bqm(self, fmt)
272 def to_bqm(self, fmt: BQMFormat = "bqm"):
--> 273 return to_bqm(
274 args=self.args, returns=self.returns, exprs=self.expressions, fmt=fmt
275 )
File /opt/hostedtoolcache/Python/3.11.14/x64/lib/python3.11/site-packages/qlasskit/bqm.py:70, in to_bqm(args, returns, exprs, fmt)
68 from pyqubo import AndConst, Binary, NotConst, OrConst, XorConst
69 except:
---> 70 raise Exception("Library pyqubo not found: run `pip install pyqubo`")
72 a_vars = {}
73 for arg in args:
Exception: Library pyqubo not found: run `pip install pyqubo`
And now we can run it in a simulated annealing using the neal library. As we expected, the minimum energy sample is (0,1,2).
import neal
from qlasskit.bqm import decode_samples
sa = neal.SimulatedAnnealingSampler()
sampleset = sa.sample(bqm, num_reads=10)
decoded_samples = decode_samples(tsp_f, sampleset)
best_sample = min(decoded_samples, key=lambda x: x.energy)
print(best_sample.sample, ":", best_sample.energy)
{'order': (0, 1, 2)} : 2.0