Browsing by Subject "quantum algorithms"

The Traveling Salesman Problem (TSP) is a well-known optimization problem. The time needed to solve TSP classically grows exponentially with the size of the input, placing it into the NP-hard computational complexity class–the class of problems that are at least as hard as any other problem solvable in nondeterministic polynomial time. Quantum computing gives us a new approach to searching through such a huge search space, using methods such as quantum annealing and phase estimation. Although the current state of quantum computers does not give us enough resources to solve TSP with a large input, we can use quantum computing methods to improve on existing classical algorithms. The thesis reviews existing methods to efficiently tackle TSP utilizing potential quantum resources, and discusses the augmentation of classical algorithms with quantum techniques to reduce the time complexity of solving this computationally challenging problem.