Welcome to the resource topic for 2024/626
Title:
Exponential Quantum Speedup for the Traveling Salesman Problem
Authors: Anant Sharma, Nupur Deshpande, Sanchita Ghosh, Sreetama Das, Shibdas Roy
Abstract:The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be NP-hard with a brute-force complexity of O(N^N) or O(N^{2N}) for N number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem typically provide with a quadratic speedup only, using Grover’s search, thereby having a complexity of O(N^{N/2}) or O(N^N). We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential speedup. The overall complexity of our algorithm is O(N^3\log(N)\kappa/\epsilon + 1/\epsilon^3), where the errors \epsilon are O(1/{\rm poly}(N)), and \kappa is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.
ePrint: https://eprint.iacr.org/2024/626
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .