Quantum Search and Classical Computing Combine to Tackle Tough Travel Problems

Scientists at the Chinese Academy of Sciences, led by Xujun Bai, have presented a new methodology addressing the travelling salesman problem (TSP), a significant classical NP-hard challenge within the domain of combinatorial optimisation. The research demonstrates the potential for a quantum advantage by integrating classical dynamic programming techniques with quantum search algorithms. A carefully constructed, parameterised spectrum for this hybrid approach reveals an achievable query complexity of O(1.865666…^n) when employing a 4-subset scheme. Crucially, quantum advantages in solving the TSP are not solely attributable to accelerated quantum search, but also to the efficient preparation of structured quantum states, potentially paving the way for a practically implementable TSP solver.

Quantum algorithm surpasses classical limits for travelling salesman problem

A query complexity of O∗(1.865666…^n) now effectively solves the travelling salesman problem, representing a substantial improvement over the previously reported O∗(2.225880…^n) achieved by a comparable algorithm. This quantum algorithm, leveraging a 4-subset scheme, now operates below the threshold necessary to surpass the classical Held-Karp bound, a longstanding limitation in the field of TSP research. The Held-Karp algorithm, a dynamic programming approach, provides an optimal solution to the TSP in O(n^2 * 2^n) time, serving as a benchmark for evaluating the efficiency of alternative algorithms. Detailed analysis revealed that the earlier calculation of query complexity was inaccurate, as it failed to account for half of the recursive branches inherent within the algorithm’s structure; correcting this oversight confirms that the 8-subset scheme could never outperform classical methods. The 4-subset scheme, in contrast, demonstrates a clear advantage by more efficiently exploring the solution space.

A carefully designed quantum divide-and-conquer strategy underpins this improvement, allowing for a parameterised spectrum of approaches ranging from purely classical to purely quantum. This spectrum allows researchers to systematically explore the trade-offs between classical and quantum resources, optimising the algorithm for specific hardware capabilities and problem sizes. The team emphasises that the quantum benefit arises not only from the well-known speedups offered by quantum search algorithms, such as Grover’s algorithm, but also from the efficient preparation of structured quantum states. This efficient state preparation enables parallel data loading, significantly reducing the classical overhead typically associated with data handling in quantum algorithms. The ability to load data in parallel is critical for mitigating the communication bottleneck between classical and quantum processors in hybrid algorithms. Simulations conducted on IBM’s Qiskit platform, utilising graphs comprising six and seven nodes, yielded accuracies of 98.9% and 100% respectively. However, it is important to note that these results are currently limited to small problem instances due to the constraints imposed by the available quantum computing resources, specifically the number of qubits and their coherence times.

This work represents a refinement of a hybrid method initially proposed by Ambainis and colleagues in 2019, precisely identifying limitations within the previous approach and pinpointing areas where genuine improvements are achievable. The travelling salesman problem has long presented a formidable challenge to mathematicians and computer scientists, requiring the determination of the shortest possible route that visits each of a given set of locations exactly once and returns to the origin. Applications of solving the TSP extend beyond logistical route planning to include areas such as DNA sequencing, microchip design, and the analysis of wireless sensor networks. While this quantum algorithm now demonstrably outperforms classical approaches, the research focused specifically on refining an existing method rather than developing a completely novel algorithmic solution. The emphasis on refinement is crucial, as it builds upon established theoretical foundations and focuses on practical improvements that can be implemented with current and near-term quantum hardware.

Earlier estimations of quantum speedup were inaccurate, overlooking key aspects of the computational process and incorrectly assessing the performance of existing methods, as the current analysis demonstrates. The researchers meticulously re-evaluated the computational complexity, identifying the previously unrecognised impact of incomplete branch consideration. More than simply accelerating the search for solutions is required to achieve a quantum advantage for the travelling salesman problem. The team’s work highlights that a quantum advantage isn’t solely derived from speedups in search algorithms, but also from the efficiency of state preparation and data handling, which reduces classical overhead and enables parallel processing. The efficient preparation of quantum states allows for a more compact representation of the problem, reducing the number of qubits required and simplifying the quantum circuit. Further investigation will focus on scaling the algorithm to larger problem instances, exploring the potential for integration with other quantum algorithms, such as variational quantum eigensolvers (VQEs), and investigating the robustness of the algorithm to noise and imperfections in quantum hardware. The ultimate goal is to develop a practical and scalable quantum solution to the travelling salesman problem that can address real-world optimisation challenges.

The researchers demonstrated a quantum advantage for solving the travelling salesman problem by combining classical dynamic programming with quantum search. This achievement matters because it clarifies how quantum algorithms can outperform classical ones for complex optimisation tasks, with a query complexity of O^*(1.865666ldotsⁿ) achieved using a 4-subset scheme. Their analysis revealed previous estimations of quantum speedup were inaccurate, and the quantum advantage arises from both faster searching and more efficient data handling. The team intends to scale this algorithm to larger problems and explore integration with other quantum techniques like variational quantum eigensolvers.