30. Ruter: a travelling-salesperson route on a quantum annealer

A small route-planning experiment: six random locations, the shortest round trip through all of them written as a QUBO with dwave_networkx, and the QUBO sent to a D-Wave quantum annealer through EmbeddingComposite. The steps are explained in Annealing in practice.

The stored run below stopped with API token not defined: it needs a D-Wave Leap account. To run it yourself, set your token (for example dwave config create) or swap DWaveSampler() for a classical sampler such as dimod’s simulated annealing.

import random
import numpy as np
from dwave.system import DWaveSampler, EmbeddingComposite
import dwave_networkx as dnx
import networkx as nx
import dimod


# Number of geolocations (nodes)
num_nodes = 6

# Function to generate random geolocations
def generate_geolocations(num_nodes):
    geolocations = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(num_nodes)]
    return geolocations

# Function to calculate the Euclidean distance between two points
def euclidean_distance(p1, p2):
    return np.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

# Generate geolocations
geolocations = generate_geolocations(num_nodes)

# Create a complete graph with nodes representing geolocations
G = nx.complete_graph(num_nodes)

# Add edges with weights as the Euclidean distance between geolocations
for i, p1 in enumerate(geolocations):
    for j, p2 in enumerate(geolocations):
        if i != j:
            G.add_edge(i, j, weight=euclidean_distance(p1, p2))

# Set up the QUBO problem
lagrange = 1.0
qubo = dnx.traveling_salesperson_qubo(G, lagrange)

# Convert the QUBO to a BQM (Binary Quadratic Model)
bqm = dimod.BinaryQuadraticModel.from_qubo(qubo)

# Set up the sampler
sampler = EmbeddingComposite(DWaveSampler())

# Solve the TSP problem using D-Wave's quantum annealer
sampleset = sampler.sample(bqm)

# Find the shortest path from the sampleset
path = dnx.traveling_salesperson(G, sampleset)

print("Shortest path:", path)
print("Total distance:", sampleset.first.energy)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[7], line 40
     37 bqm = dimod.BinaryQuadraticModel.from_qubo(qubo)
     39 # Set up the sampler
---> 40 sampler = EmbeddingComposite(DWaveSampler())
     42 # Solve the TSP problem using D-Wave's quantum annealer
     43 sampleset = sampler.sample(bqm)

File ~/micromamba/envs/moenv/lib/python3.9/site-packages/dwave/system/samplers/dwave_sampler.py:184, in DWaveSampler.__init__(self, failover, retry_interval, **config)
    181 self.retry_interval = retry_interval
    182 self._solver_penalty = defaultdict(int)
--> 184 self.client = Client.from_config(**config)
    185 self.solver = self._get_solver(penalty=self._solver_penalty)

File ~/micromamba/envs/moenv/lib/python3.9/site-packages/dwave/cloud/client/base.py:374, in Client.from_config(cls, config_file, profile, client, **kwargs)
    371 _client = config.pop('client', None) or 'base'
    373 logger.debug("Creating %s.Client() with: %r", _client, config)
--> 374 return _clients[_client](**config)

File ~/micromamba/envs/moenv/lib/python3.9/site-packages/dwave/cloud/events.py:105, in dispatches_events.__call__.<locals>.wrapped(*pargs, **kwargs)
    103 dispatch_event(self.before_eventname, obj=obj, args=args)
    104 try:
--> 105     rval = fn(*pargs, **kwargs)
    106 except Exception as exc:
    107     dispatch_event(self.after_eventname, obj=obj, args=args, exception=exc)

File ~/micromamba/envs/moenv/lib/python3.9/site-packages/dwave/cloud/client/base.py:477, in Client.__init__(self, *args, **kwargs)
    475 token = options['token']
    476 if not token:
--> 477     raise ValueError("API token not defined")
    479 # parse optional client certificate
    480 client_cert = options['client_cert']

ValueError: API token not defined