Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Imagine a delivery driver who must visit a list of cities exactly once and return home, aiming to travel the shortest possible distance. This is the traveling salesman problem, a classic puzzle that sits at the heart of logistics, scheduling, and circuit design. While finding the perfect route for a few cities is easy, the difficulty explodes as the list grows; for every new city added, the number of possible routes multiplies so rapidly that even the fastest supercomputers can get stuck trying to find the best one. For decades, scientists have looked to quantum computers, machines that use the strange rules of subatomic particles to process information, to solve these puzzles faster. However, a major hurdle has remained: how to translate the problem into a language the quantum computer understands without drowning the calculation in errors and unnecessary complexity.

A researcher at QuantScape Inc. has now demonstrated a new way to guide a quantum computer through this maze, successfully finding the shortest route for maps with up to ten cities. The work, which relies on simulations of quantum hardware rather than physical machines, introduces a method that uses far fewer quantum bits—the basic units of information in a quantum computer—than previous approaches. More importantly, it shows that a single set of instructions can adapt to changing road conditions, such as traffic that varies throughout the day, without needing to be retrained for every new scenario. The results suggest that with the right encoding and training techniques, quantum computers could soon tackle optimization problems that are currently out of reach, provided the hardware continues to improve.

The core of the challenge lies in how the problem is written down for the machine. Traditional methods assign a separate quantum bit to every possible combination of a city and a position in the route. For a map with ten cities, this approach requires eighty-one bits, and it forces the computer to constantly check and discard invalid routes, wasting time and energy on penalties. The new study uses a different strategy, inspired by a mathematical system called the Lehmer code, which essentially ranks every possible route by its order in a list. This method requires only nineteen bits for ten cities, a significant reduction. By using this compact code, every possible state of the quantum computer represents a valid route, eliminating the need for penalty checks. To make the search efficient, the researchers arranged these states so that flipping a single bit in the code corresponds to a small, logical change in the route, allowing the computer to explore the solution space smoothly.

To guide the quantum computer, the researchers employed a hybrid system called a variational quantum Kolmogorov–Arnold network. Think of this as a smart controller that watches the map and the time of day, then sets the dials on the quantum circuit to the correct positions. Instead of hard-coding the settings for each specific map, this controller learns a general rule: how to adjust the circuit based on the distances between cities and the current time. This allows the system to handle time-dependent graphs, where travel times change, such as a power grid or a road network with rush hour traffic. The controller was trained using a specific goal: to minimize the risk of picking a long route. Rather than just looking for the absolute average length, the training focused on the worst-case scenarios within the top few percent of likely outcomes, ensuring the final result is robust and reliable.

The training process itself was rigorous, designed to avoid the common trap of getting stuck in a local minimum, where the computer settles for a "good enough" answer instead of the best one. The researchers used a multi-step strategy that started with broad searches and gradually narrowed the focus, combined with a technique that deliberately jostled the settings to escape dead ends. They also used a method called basin hopping, which acts like a gentle shake to help the system jump out of shallow valleys in the search landscape. When tested on maps with four to ten cities, including both symmetric shapes and random, uneven networks, this approach found the perfect route in every single case for the smaller maps. For the ten-city maps, which are significantly harder, the method found the optimal route in 112 out of 120 trials, with the remaining failures being only one percent off the perfect distance.

Crucially, the study ruled out several alternative ideas that might have seemed promising. The researchers tested a simpler approach that uses only ten bits, one for each city, to track the driver's position step-by-step. This method failed completely for maps with six or more cities because it could not represent the complex relationships between successive stops. They also compared their results against a standard classical algorithm known as 2-opt, which improves a route by swapping two segments. While 2-opt is effective, the quantum circuit provided a much better starting point, and the combination of the two outperformed either method alone. The study confirmed that the success came from the specific way the problem was encoded and the sophisticated training of the controller, not just from the power of the quantum circuit itself.

The findings also highlight the efficiency of the method regarding measurement. In a real quantum computer, reading the answer requires repeating the process many times to get a clear signal. The simulations showed that even with as few as one hundred readings, the system could reliably identify the best route. This suggests that when physical quantum computers with enough bits become available, this method could deliver results quickly without needing millions of repetitions. The researchers noted that while the current work was performed on a classical computer simulating quantum behavior, the techniques are designed to work on actual hardware. The next steps involve testing the system under the noisy conditions of real machines and scaling it up to larger maps where the number of possible routes is too vast to check by hand.

This work represents a significant step forward in making quantum optimization practical. By solving the encoding problem and creating a controller that generalizes across different maps and times, the researchers have shown a path toward machines that can solve complex routing problems efficiently. The ability to handle time-dependent changes with a single set of parameters is particularly promising for real-world applications where conditions are never static. While the journey to a fully functional quantum optimizer is ongoing, this study provides a clear blueprint for how to train these machines to find the shortest path through a complex world.