The TSP on the nodes of a graph asks for the shortest Hamiltonian cycle that can be taken through each of the nodes. A Hamilton cycle is a closed path that uses every vertex of a graph once. The general solution is unknown and an algorithm that finds it efficiently (e.g., in polynomial time) is not expected to exist.
https://qiskit-community.github.io/qiskit-optimization/tutorials/06_examples_max_cut_and_tsp.html
TSP benchmarking
4 cities:
- fixstar: 0:00:00.932049
- gurobi: 0:00:00.121999
- d-wave: 0:00:00.190519
- qiskit:
5 cities:
- fixstar: 0:00:00.929671
- gurobi: 0:00:00.021999
- d-wave: 0:00:00.221244
- qiskit: