Combinatorial classes¶

Two Quadratic Unconstrained Binary Optimisation (QUBO) example problems are listed here: the Travelling Salesman Problem and the Maximum Independent Set.

Travelling Salesman Problem¶

The Travelling Salesman Problem (sometimes referred to as the Travelling Salesperson Problem), commonly abbreviated as TSP, is a NP-hard problem in combinatorial optimisation.

Briefly, the problem revolves around finding the shortest possible route for a salesman to visit some cities before returning to the origin. TSP is usually formulated as a graph problem with nodes specifying the cities and edges denoting the distances between each city.

The idea behind TSP can be mapped to similar-type problems. For instance, what is the optimal route for the salesman to take in order to minimise something.

In this module, the TSP class follows Hadfield’s 2017 paper.

class qiboopt.combinatorial_classes.combinatorial_classes.TSP(distance_matrix, backend=None)[source]¶

Class representing the Travelling Salesman Problem (TSP). The implementation is based on the work by Hadfield.

Parameters:

distance_matrix – a numpy matrix encoding the distance matrix.
backend – Backend to use for calculations. If not given the global backend will be used.

Example

from qibo.models.tsp import TSP
import numpy as np
from collections import defaultdict
from qibo import gates
from qibo.models import QAOA
from qibo.result import CircuitResult


def convert_to_standard_Cauchy(config):
    m = int(np.sqrt(len(config)))
    cauchy = [-1] * m  # Cauchy's notation for permutation, e.g. (1,2,0) or (2,0,1)
    for i in range(m):
        for j in range(m):
            if config[m * i + j] == '1':
                cauchy[j] = i  # citi i is in slot j
    for i in range(m):
        if cauchy[i] == 0:
            cauchy = cauchy[i:] + cauchy[:i]
            return tuple(cauchy)
            # now, the cauchy notation for permutation begins with 0


def evaluate_dist(cauchy):
    '''
    Given a permutation of 0 to n-1, we compute the distance of the tour

    '''
    m = len(cauchy)
    return sum(distance_matrix[cauchy[i]][cauchy[(i+1)%m]] for i in range(m))


def qaoa_function_of_layer(layer, distance_matrix):
    '''
    This is a function to study the impact of the number of layers on QAOA,
    it takes in the number of layers and compute the distance of the mode
    of the histogram obtained from QAOA

    '''
    small_tsp = TSP(distance_matrix)
    obj_hamil, mixer = small_tsp.hamiltonians()
    qaoa = QAOA(obj_hamil, mixer=mixer)
    best_energy, final_parameters, extra = qaoa.minimize(initial_p=[0.1] * layer,
                                         initial_state=initial_state, method='BFGS')
    qaoa.set_parameters(final_parameters)
    quantum_state = qaoa.execute(initial_state)
    circuit = Circuit(9)
    circuit.add(gates.M(*range(9)))
    result = CircuitResult(quantum_state, circuit.measurements,
            small_tsp.backend, nshots=1000)
    freq_counter = result.frequencies()
    # let's combine freq_counter here, first convert each key and sum up the frequency
    cauchy_dict = defaultdict(int)
    for freq_key in freq_counter:
        standard_cauchy_key = convert_to_standard_Cauchy(freq_key)
        cauchy_dict[standard_cauchy_key] += freq_counter[freq_key]
    max_key = max(cauchy_dict, key=cauchy_dict.get)
    return evaluate_dist(max_key)

np.random.seed(42)
num_cities = 3
distance_matrix = np.array([[0, 0.9, 0.8], [0.4, 0, 0.1],[0, 0.7, 0]])
distance_matrix = distance_matrix.round(1)
small_tsp = TSP(distance_matrix)
initial_parameters = np.random.uniform(0, 1, 2)
initial_state = small_tsp.prepare_initial_state([i for i in range(num_cities)])
qaoa_function_of_layer(2, distance_matrix)

Reference:: 1. S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, R. Biswas, From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz. (arxiv:1709.03489)

hamiltonians()[source]¶

Constructs the phaser and mixer Hamiltonians for the TSP.

Returns:: A tuple containing the phaser and mixer Hamiltonians.
Return type:: tuple

prepare_initial_state(ordering)[source]¶

Prepares a valid initial state for TSP QAOA based on the given city ordering.

Parameters:: ordering (list) – A list representing the permutation of cities.
Returns:: The quantum state representing the initial solution.
Return type:: array

penalty_method(penalty)[source]¶

Constructs the TSP QUBO object using a penalty method for feasibility.

Parameters:: penalty (float) – The penalty parameter for constraint violations.
Returns:: A QUBO object for the TSP with penalties applied.
Return type:: QUBO

Maximum Independent Set¶

The MIS problem involves selecting the largest subset of non-adjacent vertices in a graph.

class qiboopt.combinatorial_classes.combinatorial_classes.Mis(g)[source]¶

Class for representing the Maximal Independent Set (MIS) problem.

The MIS problem involves selecting the largest subset of non-adjacent vertices in a graph.

Parameters:: g (networkx.Graph) – A graph object representing the problem.

Example

import networkx as nx
from qiboopt.combinatorial_classes.combinatorial_classes import Mis

g = nx.Graph()
g.add_edges_from([(0, 1), (1, 2), (2, 0)])
mis = Mis(g)
penalty = 10
qp = mis.penalty_method(penalty)

penalty_method(penalty)[source]¶

Constructs the QUBO Hamiltonian for the MIS problem using a penalty method.

Parameters:: penalty (float) – The penalty parameter for constraint violations.
Returns:: A QUBO object for the Maximal Independent Set (MIS) problem.
Return type:: QUBO (qiboopt.opt_class.opt_class.QUBO)