Source code for quantum_launcher.problems.problem_formulations.hamiltonians.tsp

  1from typing import Literal
  2
  3import numpy as np
  4import networkx as nx
  5
  6from quantum_launcher.problems.problem_initialization import TSP
  7
  8from quantum_launcher.hampy import Equation
  9import quantum_launcher.hampy as hampy
 10from quantum_launcher.hampy.utils import shift_affected_qubits
 11
 12

[docs]
 13def make_non_collision_hamiltonian(node_count: int, quadratic=False):
 14    """
 15    Creates a Hamiltonian representing constraints for the TSP problem. (Each node visited only once, one node per timestep)
 16    Qubit mapping: [step1:[node1, node2,... noden]],[step2],...[stepn]
 17
 18    Args:
 19        node_count: Number of nodes in the TSP problem
 20        quadratic: Whether to encode as a QUBO problem
 21
 22    Returns:
 23        np.ndarray: Hamiltonian representing the constraints
 24    """
 25
 26    n = node_count**2
 27    eq = Equation(n)
 28
 29    # hampy.one_in_n() takes a long time to execute with large qubit counts.
 30    # We can exploit the nature of tsp constraints and create the operator for the first timestep and then shift it for the rest of the timesteps
 31    # Same with nodes below.
 32    # I'm pretty sure this works as intended...
 33
 34    # Ensure that at each timestep only one node is visited
 35    t0_op = hampy.one_in_n(
 36        [i for i in range(node_count)],
 37        eq.size,
 38        quadratic=quadratic
 39    )
 40
 41    for timestep in range(node_count):
 42        shift = shift_affected_qubits(t0_op, timestep * node_count)
 43        eq += shift
 44
 45    # Ensure that each node is visited only once
 46    n0_op = hampy.one_in_n(
 47        [timestep * node_count for timestep in range(node_count)],
 48        eq.size,
 49        quadratic=quadratic
 50    )
 51
 52    for node in range(node_count):
 53        shift = shift_affected_qubits(n0_op, node)
 54        eq += shift
 55
 56    return -1 * eq.hamiltonian

 57
 58

[docs]
 59def make_connection_hamiltonian(edge_costs: np.ndarray, return_to_start: bool = True) -> np.ndarray:
 60    """
 61    Creates a Hamiltonian that represents the costs of picking each path.
 62
 63    Args:
 64        tsp_matrix: Edge cost matrix of the TSP problem
 65
 66    Returns:
 67        np.ndarray: Optimal chain of nodes to visit
 68    """
 69    node_count = edge_costs.shape[0]
 70    if len(edge_costs.shape) != 2 or edge_costs.shape[1] != node_count:
 71        raise ValueError("edge_costs must be a square matrix")
 72
 73    n = node_count**2
 74    eq = Equation(n)
 75
 76    for timestep in range(node_count - 1):
 77        for node in range(node_count):
 78            for next_node in range(node_count):
 79                if node == next_node:
 80                    continue
 81                and_hamiltonian = (
 82                    eq[node + timestep * node_count]
 83                    & eq[next_node + (timestep + 1) * node_count]
 84                )
 85                eq += edge_costs[node, next_node] * and_hamiltonian
 86
 87    if not return_to_start:
 88        return eq.hamiltonian
 89
 90    # Add cost of returning to the first node
 91    for node in range(node_count):
 92        for node2 in range(node_count):
 93            and_hamiltonian = (
 94                eq[node + (node_count - 1) * node_count] & eq[node2]
 95            )
 96            eq += edge_costs[node, node2] * and_hamiltonian
 97
 98    return eq.hamiltonian

 99
100

[docs]
101def problem_to_hamiltonian(problem: TSP, constraints_weight: int = 5, costs_weight: int = 1, return_to_start: bool = True, onehot: Literal['exact', 'quadratic'] = 'exact') -> np.ndarray:
102    """
103    Creates a Hamiltonian for the TSP problem.
104
105    Args:
106        problem: TSP problem instance
107        quadratic: Whether to encode as a quadratic Hamiltonian
108        constraints_weight: Weight of the constraints in the Hamiltonian
109        costs_weight: Weight of the costs in the Hamiltonian
110
111    Returns:
112        np.ndarray: Hamiltonian representing the TSP problem
113    """
114    instance_graph = problem.instance
115
116    edge_costs = nx.to_numpy_array(instance_graph)
117    # discourage breaking the constraints
118    edge_costs += np.eye(len(edge_costs)) * np.max(edge_costs)
119    scaled_edge_costs = edge_costs.astype(np.float32) / np.max(edge_costs)
120
121    node_count = len(instance_graph.nodes)
122
123    constraints = make_non_collision_hamiltonian(node_count, quadratic=(onehot == 'quadratic'))
124    costs = make_connection_hamiltonian(scaled_edge_costs, return_to_start=return_to_start)
125
126    return constraints * constraints_weight + costs * costs_weight