Quantum Optimization Methods for the Generalized Traveling Salesman Problem

This paper evaluates quantum optimization methods, specifically a novel QUBO formulation for quantum annealing and a constrained QAOA variant with an XY-mixer, for the Generalized Traveling Salesman Problem, finding that while they offer competitive solution quality on small instances, they currently face significant challenges in feasibility, scalability, and runtime compared to classical solvers.

The Gist

Imagine you are a delivery robot with a very specific job. You have a list of tasks to do, but these tasks are grouped into "neighborhoods" (clusters). Your rule is simple: you must visit exactly one stop in each neighborhood, and you must do so in an order that saves the most fuel. You can't visit two stops in the same neighborhood, and you can't skip a neighborhood entirely. This is the Generalized Traveling Salesman Problem (GTSP).

Now, imagine trying to solve this puzzle not with a regular computer, but with a Quantum Computer. These are futuristic machines that use the weird rules of physics (like being in two places at once) to find answers.

This paper is a report card on how well current quantum computers can solve this specific "neighborhood delivery" puzzle. Here is the breakdown of what the researchers did and what they found, using simple analogies.

The Two Quantum Tools They Tried

The team tested two different "quantum engines" to solve the puzzle:

1. The Quantum Annealer (The "Magnet Maze"):
   Think of this as a marble rolling down a bumpy, complex hill. The bottom of the hill represents the perfect solution (the cheapest route). The machine tries to roll the marble down to find the lowest point.

   • The Problem: The hill is full of "traps" (invalid routes). The marble often gets stuck in a shallow dip that looks like the bottom but isn't the real answer. The researchers had to build a very specific map (a QUBO formulation) to make sure the marble only rolls on valid paths.

2. The Gate-Based QAOA (The "Tightrope Walker"):
   This is like a tightrope walker trying to find the best path across a canyon. They take steps (layers of a circuit), adjusting their balance (parameters) to get closer to the goal.

   • The Innovation: The researchers built a special "safety harness" (an XY-mixer) for this walker. This harness forces the walker to stay on the tightrope (visiting exactly one stop per neighborhood) at every step. However, they still had to rely on "penalty signs" to stop the walker from stepping off the map entirely (visiting the wrong neighborhoods or non-existent roads).

The "Size Limit" Problem

Current quantum computers are like tiny calculators compared to the supercomputers we use today. They don't have enough "buttons" (qubits) to handle big problems.

To make the puzzle fit on these tiny machines, the researchers invented a Preprocessing Trick:

• Imagine you have a city with 100 neighborhoods, but your robot can only handle 5.
• Instead of trying to solve the whole city, they looked at each neighborhood and said, "Okay, which one stop in this neighborhood is closest to the next neighborhood?"
• They threw away all the other stops and kept only the "best entry" and "best exit" for each neighborhood.
• This shrank the massive city down to a tiny village that the quantum computer could actually handle.

What They Found (The Results)

The researchers compared their quantum robots against a very smart, classical computer (a standard algorithm called GLNS).

1. The Good News (Small Puzzles):
When the puzzle was small (3 to 5 neighborhoods), the quantum computers were impressive. They often found the perfect route or a route very close to it. In these tiny scenarios, they performed just as well as the best classical computers.

2. The Bad News (Growing Pains):
As soon as the puzzle got slightly bigger (more than 5 or 7 neighborhoods), the quantum computers started to struggle badly.

• The "Feasibility" Crash: The biggest issue wasn't that they found a bad route; it's that they often found no valid route at all. Imagine the tightrope walker falling off the rope, or the marble rolling into a wall.
• The "Noise" Factor: As the problem grew, the quantum computers got "confused" by noise and limitations. For the largest tests, they failed to find a single valid solution more than 99% of the time.
• The Bottleneck: The researchers found that the main problem is sampling. The quantum computer needs to try many, many times to get a good answer. But as the puzzle gets bigger, the chance of getting any valid answer in the time allowed drops to near zero.

The Verdict

The paper concludes that while quantum computers are currently great at small, specific puzzles, they are not yet ready to solve big, real-world routing problems on their own.

• For small jobs: They work well and can compete with classical computers.
• For big jobs: They currently fail because they can't keep the solution "valid" (feasible) as the problem gets complex.

The researchers suggest that for quantum computers to be useful for this kind of problem in the future, we need better ways to force the computer to stay on the "valid path" without crashing, and we need bigger, less noisy machines. Until then, the "preprocessing trick" is the only way to make these problems fit on today's quantum hardware, but even that has limits.

Technical Summary

1. Problem Definition

The paper addresses the Generalized Traveling Salesman Problem (GTSP), an NP-hard extension of the classical TSP.

• Definition: The problem involves a graph where nodes are partitioned into disjoint clusters. The objective is to find a minimum-cost tour that visits exactly one node from each cluster and returns to the origin.
• Applications: GTSP models real-world industrial scenarios such as flexible manufacturing scheduling, automated storage/retrieval, warehouse order picking, and robotic motion planning (where a robot must select one execution variant from multiple options for a sequence of subtasks).
• Challenge: While quantum solutions for the standard TSP exist, GTSP formulations are scarce. The problem introduces complex constraints (cluster selection and sequencing) that are difficult to map to current Noisy Intermediate-Scale Quantum (NISQ) hardware due to qubit limitations and the difficulty of maintaining solution feasibility.

2. Methodology

The authors propose and evaluate two distinct quantum optimization paradigms, alongside a classical preprocessing strategy to mitigate hardware limitations.

A. Preprocessing: Extended Nearest Nodes to Clusters (NN2C)

To address the limited qubit count of current hardware, the authors extend the NN2C algorithm to reduce instance size before solving:

• Mechanism: For each cluster, the algorithm selects the "best entry node" (minimizing incoming distance from other clusters) and the "best exit node" (minimizing outgoing distance).
• Outcome: This reduces the number of nodes per cluster to at most two, effectively shrinking the problem size while preserving the cluster structure. This allows larger original GTSPLIB instances to be mapped to solvable quantum instances.

B. Quantum Annealing Approach (Q-GTSP)

• Formulation: The authors propose a novel QUBO (Quadratic Unconstrained Binary Optimization) encoding using a one-hot representation ($x_{c,i} = 1$ if node $i$ is visited at step $c$).
• Constraints: The cost function is augmented with quadratic penalty terms to enforce:
  1. Exactly one node visited per step ($p_0$).
  2. Exactly one node visited per cluster ($p_1$).
  3. Valid edge transitions ($p_2$).
• Penalty Weighting: A specific penalty factor $\lambda$ is calculated to ensure that any invalid solution is strictly more expensive than the most expensive valid solution, theoretically guaranteeing that the ground state corresponds to a feasible tour.
• Hardware: Executed on D-Wave's Advantage2 QPU (Zephyr topology).

C. Gate-Based Approach (C-QAOA)

• Algorithm: A constrained Quantum Approximate Optimization Algorithm (QAOA) variant.
• Mixer Design: Instead of a standard transverse-field mixer, the authors employ an XY-mixer. This mixer preserves the "one-hot" constraint (step-wise Hamming weight) by restricting quantum evolution to the feasible subspace of the step constraint.
• Constraint Handling: While the XY-mixer handles the step constraint intrinsically, the cluster and edge constraints are still enforced via penalty terms in the cost Hamiltonian.
• Initialization: The circuit starts in a single feasible random one-hot state rather than a uniform superposition to reduce circuit depth and hardware demands.
• Simulation: Simulated using Qiskit Aer (due to limited access to IBM QPUs for full parameter optimization), targeting Heron processor architectures.

3. Key Contributions

1. Novel GTSP QUBO Encoding: A specific formulation focused on generating feasible solutions through carefully tuned penalty terms.
2. Constrained QAOA Pipeline: Implementation of a hardware-oriented C-QAOA using an XY-mixer to intrinsically preserve step-wise feasibility, a significant step toward constraint-preserving quantum algorithms.
3. Extended Preprocessing: A modified NN2C algorithm tailored for asymmetric GTSP instances to reduce problem dimensions for NISQ devices.
4. Comprehensive Benchmarking: A direct comparison of quantum annealing and gate-based approaches against classical state-of-the-art solvers (GLNS/Gurobi) on the GTSPLIB dataset.

4. Experimental Results

The study evaluated performance on Subsample (randomly selected clusters) and Preprocessed (reduced via NN2C) instances from GTSPLIB.

• Small Instances (3–5 nodes):

  • Both quantum approaches frequently found optimal or near-optimal solutions.
  • Feasibility: Quantum Annealing (Q-GTSP) showed high feasibility rates (up to 98% on preprocessed instances). C-QAOA showed lower feasibility (often <50%) but could still find optimal solutions in the "best-shot" analysis.
  • Comparison: On very small graphs, quantum solvers were competitive with classical solvers.

• Scaling and Larger Instances (6–20+ nodes):

  • Feasibility Collapse: As instance size grew, the percentage of feasible solutions dropped sharply. For C-QAOA, feasibility fell below 1% for instances with 13–15 nodes. For Q-GTSP, feasibility dropped significantly beyond 15 nodes.
  • Solution Quality: The mean approximation ratio often fell below the random guessing baseline, indicating that the majority of sampled shots were invalid or poor quality.
  • Hardware Limits:
    • Q-GTSP: Encountered "embedding failures" on preprocessed medium instances where logical qubit requirements (up to 400) exceeded physical qubit capacity.
    • C-QAOA: Suffered from low sampling rates; 1500 shots were insufficient to cover the exponentially growing search space.

• Preprocessing Impact:

  • Preprocessing significantly improved the feasibility of the Quantum Annealing approach, allowing it to handle larger underlying problem structures.
  • Preprocessing had a negative or neutral impact on C-QAOA, likely due to the increased structural complexity (more clusters) which the shallow circuit depth ($p=1$) could not handle.

5. Significance and Conclusion

• Current State: Quantum optimizers show promise for small-scale GTSP instances, capable of finding optimal solutions. However, they currently suffer from poor scalability and low feasibility rates as problem size increases.
• Primary Bottleneck: The main failure mode is not just solution quality, but the inability to generate feasible solutions within a fixed shot budget. Penalty-based constraint handling (in QUBO) and shallow mixers (in QAOA) struggle to navigate the constrained search space effectively.
• Future Directions: The authors conclude that for quantum optimization to be viable for GTSP, future work must focus on:
  1. Constraint Handling: Moving beyond penalty terms to intrinsic constraint enforcement (e.g., more sophisticated mixers in QAOA).
  2. Scalability: Improving encoding efficiency and circuit depth management.
  3. Hardware: Utilizing larger, more connected qubit topologies to reduce embedding overhead.

In summary, while the paper establishes a foundational framework for quantum GTSP, it highlights that current NISQ hardware and algorithms are not yet ready to replace classical solvers for practical, medium-to-large scale routing problems without significant algorithmic breakthroughs in constraint handling.