Development, Python, Quantum Computing, Quantum Programming, Technology

D-Wave Python Pack 1.4.0-alpha1 Trial 2

I decided to take a break from this long weekend’s coding bender to get back to the D-Wave developer tutorials. Taking a break from one coding project by working on another may seem counter-intuitive to non-programmers, but it’s actually a great way of getting a fresh perspective when one function starts blurring into another.

I decided to take a look at some of the new tutorials, namely Travelling Salesman and the Hadamard Matrix search. I’m pleased to report that they function exactly as advertised (despite some criticism from a certain user on the D-Wave forums).

Here is my copy of the complete source code of the Travelling Salesman tutorial (travelling-salesman.py), with corrections (and without comments). You will need the .tsp files from the original tutorial to run this code:


import math
from dwave_sapi import LocalConnection, BlackBoxSolver
from numpy import dot, array, prod

def file_to_coordinates(filename):
    f = open(filename, 'r')

    coordinates = [i.strip().split() for i in f.readlines()]

    coords = []
    for line in coordinates:
        try:
            temp = int(line[0])
            new_index = int(line[0])-1
            coords.append([new_index, float(line[1]), float(line[2])])
        except ValueError:
            pass

    f.close()

    return coords

def make_edge_list(coords):
    edges = []
    number_of_nodes = len(coords)

    for i in range(len(coords)):
        j = i+1
        while j < len(coords):
            x_distance = coords[i][1] - coords[j][1]
            y_distance = coords[i][2] - coords[j][2]
            distance = math.sqrt(x_distance**2 + y_distance**2)

            edge = [coords[i][0],coords[j][0],distance]
            edges.append(edge)

            j += 1

    return edges, number_of_nodes

def BuildIndexMatrix(edge_list, number_of_nodes):
    index_matrix = []
    for node_index in range(number_of_nodes):
        temp_list = []
        for line in edge_list:
            if line[0] == node_index or line[1] == node_index:
                temp_list.append(1)
            else:
                temp_list.append(0)
        index_matrix.append(temp_list)
    return index_matrix

def PathLengthFinder(edge_list, w):
    present_edges = []
    for i in range(len(w)):
        if w[i] == 1:
            present_edges.append(edge_list[i])

    previous_node = 0
    current_node = 0
    path_length = 0
    end = False
    element_to_delete = 0

    while end == False:
        previous_node = current_node
        for i in range(len(present_edges)):
            if present_edges[i][0] == current_node:
                element_to_delete = i
                current_node = present_edges[i][1]
                break
            elif present_edges[i][1] == current_node:
                element_to_delete = i
                current_node = present_edges[i][0]
                break

        if current_node == 0:
            path_length += 1
            end = True
        else:
            if previous_node == current_node:
                return 0
            else:
                del present_edges[element_to_delete]
                path_length += 1

    return path_length

class GeneratingFunction(object):
    def __init__(self, edge_list, number_of_nodes):
        self.edge_list = edge_list
        self.number_of_nodes = number_of_nodes

    def __call__(self, states, numStates):

        stateLen = len(states)/numStates
        states_bin = [(item+1)/2 for item in states]

        ret = []
        for state_number in range(numStates):
            w = array(states_bin[state_number*stateLen:(state_number+1)*stateLen])
            index_matrix = BuildIndexMatrix(self.edge_list, self.number_of_nodes)

            weights = []
            for line in self.edge_list:
                weights.append(line[2])

            prefactor = max(weights)*self.number_of_nodes

            current_path_length = PathLengthFinder(self.edge_list, w)
            if current_path_length == 0:
                G = prefactor**10
            else:
                G = dot(weights, w)
                for line in index_matrix:
                    G += (prefactor*(dot(line, w) - 2))**2
                G += (prefactor*(current_path_length - self.number_of_nodes))**2

            ret.append(G)

        return tuple(ret)

print 'List of nodes:'
coordinates = file_to_coordinates('simple.tsp')
for line in coordinates:
    print line

print 'List of edges:'
edges, num_node = make_edge_list(coordinates)
for edge in edges:
    print edge
print 'Number of nodes:', num_node
print 'Number of edges:', len(edges)

print 'Index matrix:'
index_matrix = BuildIndexMatrix(edges, num_node)
for line in index_matrix:
    print line

conn = LocalConnection()
solver = conn.get_solver('c4-sw_optimize')
blackbox_solver = BlackBoxSolver(solver)

genFunc = GeneratingFunction(edges, num_node)

blackbox_parameter = 10
blackbox_answer = blackbox_solver.solve(genFunc, len(edges), cluster_num = 10, min_iter_inner = blackbox_parameter, max_iter_outer = blackbox_parameter, unchanged_threshold = blackbox_parameter, max_unchanged_objective_outer = blackbox_parameter, max_unchanged_objective_inner = blackbox_parameter, unchanged_best_threshold = blackbox_parameter, verbose = 0)
blackbox_answer_bin = array([(item+1)/2 for item in blackbox_answer])

print 'The best bit string we found was:', blackbox_answer_bin

print 'This corresponds to the edges:'
total_journey = 0.0
for num in range(len(blackbox_answer_bin)):
    if blackbox_answer_bin[num] == 1:
        total_journey += edges[num][2]
        print edges[num]
print 'For a total journey distance of:', total_journey

I got the exact same results as posted on the tutorial page:


C:\Python27\python.exe "C:/.../travelling-salesman.py"
List of nodes:
[0, 0.0, 3.0]
[1, 0.0, 0.0]
[2, 3.0, 0.0]
[3, 4.0, 3.0]
List of edges:
[0, 1, 3.0]
[0, 2, 4.242640687119285]
[0, 3, 4.0]
[1, 2, 3.0]
[1, 3, 5.0]
[2, 3, 3.1622776601683795]
Number of nodes: 4
Number of edges: 6
Index matrix:
[1, 1, 1, 0, 0, 0]
[1, 0, 0, 1, 1, 0]
[0, 1, 0, 1, 0, 1]
[0, 0, 1, 0, 1, 1]
The best bit string we found was: [1 0 1 1 0 1]
This corresponds to the edges:
[0, 1, 3.0]
[0, 3, 4.0]
[1, 2, 3.0]
[2, 3, 3.1622776601683795]
For a total journey distance of: 13.1622776602

Process finished with exit code 0

The matrix search sourcecode is available in the Git repository or as a single code snippet on the tutorial page.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s