dwave_networkx.algorithms.tsp.traveling_salesperson_qubo

traveling_salesperson_qubo(G, lagrange=None, weight='weight')[source]

Return the QUBO with ground states corresponding to a minimum TSP route.

If \(|G|\) is the number of nodes in the graph, the resulting qubo will have:

  • \(|G|^2\) variables/nodes
  • \(2 |G|^2 (|G| - 1)\) interactions/edges
Parameters:
  • G (NetworkX graph) – A complete graph in which each edge has a attribute giving its weight.
  • lagrange (number, optional (default None)) – Lagrange parameter to weight constraints (no edges within set) versus objective (largest set possible).
  • weight (optional (default 'weight')) – The name of the edge attribute containing the weight.
Returns:

QUBO – The QUBO with ground states corresponding to a minimum travelling salesperson route. The QUBO variables are labelled (c, t) where c is a node in G and t is the time index. For instance, if (‘a’, 0) is 1 in the ground state, that means the node ‘a’ is visted first.
Return type:

dict