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:
- \(|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.
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.