Solving the Steiner Traveling Salesman Problem with Quantum Computing

What is it about?

This research looks at a problem called the Steiner Traveling Salesman Problem (STSP). Imagine a delivery driver who must visit several required locations, but can also pass through optional “shortcut” stops if they make the trip cheaper or faster. Finding the best route is very difficult because the number of possible paths grows extremely fast as the network gets bigger. We explore whether quantum annealing, a type of quantum computing available on D-Wave machines, can help solve this problem. To make it practical, we created a method to simplify the network before giving it to the quantum computer. This reduces unnecessary paths and makes the problem easier to handle. We then tested both D-Wave’s direct quantum processor and its hybrid solver (which mixes quantum and classical computing). Our results show that the simplification method always makes the problem easier and improves the solutions. The hybrid solver found better and faster solutions than the quantum hardware alone, making it more suitable for larger and real-world cases.

Featured Image

Why is it important?

This is the first time quantum computing has been applied to the Steiner Traveling Salesman Problem, which is relevant in logistics, transportation, and communication network design. The work shows that while pure quantum hardware still struggles with larger cases, hybrid quantum-classical methods can already provide good results. Our simplification method (PMRA) is a key contribution, as it makes quantum optimization approaches more practical and scalable. This study helps bridge the gap between theoretical quantum computing and real-world applications in routing and logistics.

Perspectives