traveling_salesperson_qubo(G, lagrange=None, weight='weight', missing_edge_weight=None)[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

  • 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.

  • missing_edge_weight (number, optional (default None)) – For bi-directional graphs, the weight given to missing edges. If None is given (the default), missing edges will be set to the sum of all weights.


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: