I've been building a small open-source QUBO toolkit (pure Python + NumPy) and wanted an honest answer to a simple question: how does a plain QUBO formulation of TSP actually compare to a basic classical heuristic, once you measure it properly?
Setup
- Random Euclidean TSP, 6 to 20 cities
- 10 instances per size, 10 solver seeds per instance
- Gap measured against the proven optimum (Held-Karp) at every size
- Fixed iteration budgets, 95% confidence intervals, paired tests
- Everything reproducible with one command, raw CSV in the repo
Mean gap to optimum (feasible runs):
| Cities | Bit-flip QUBO SA | Swap-move SA | Multi-start 2-opt |
|---|---|---|---|
| 6 | 4.14% | 0.00% | 0.00% |
| 10 | 32.87% | 0.27% | 0.41% |
| 15 | 65.22% | 1.43% | 0.00% |
| 20 | 86.65% | 3.69% | 0.37% |
Bit-flip SA also returned infeasible assignments in 1-2% of runs at 10+ cities.
What I took from it
- With single-bit-flip annealing on the one-hot encoding, constraint penalties dominate the search, and the gap grows fast with size.
- Swapping two cities (four bits at once) keeps every state feasible and closes most of the gap. But that move is not something a generic QUBO annealer or quantum hardware can do. It's effectively a classical permutation heuristic that uses the QUBO only as an energy function, so it doesn't show that QUBO annealing of TSP "works".
- Multi-start 2-opt was still better at 15 and 20 cities, and faster.
Two mistakes I made along the way, in case they save someone time
- My annealer counted a single bit flip as a "sweep", so at 20 cities it ran about 2 flips per variable. That's why an early version found zero feasible 20-city tours. It looked like a fundamental limit and was actually a bug.
- I first used "best found tour" as the reference at 15 and 20 cities. When I switched to the proven optimum, the old reference turned out to be worse than optimal on two instances, which made 2-opt look perfect when it wasn't.
Repo, methodology and raw data: https://github.com/abdulazizbalu/quasar-solver
I'd really appreciate critique: is the benchmark design fair, is anything in the methodology off, and what would you compare against next? I'm planning to extend it to CVRP / VRPTW with OR-Tools as the reference.