traveling_salesperson_qubo(G, lagrange=None, weight='weight')¶
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:
\(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.
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