Quantum Algorithms to Solve the Traveling Salesman Problem

Overview

This project proposes and demonstrates two new quantum computing algorithms which solve the Traveling Salesman Problem (TSP). The TSP asks for the shortest continuous path in a graph of nodes known as cities. This problem is in the hardest class of problems in computer science and many optimization algorithms have been developed to more efficiently solve this problem. Versions of the TSP occur in a number of scientific and engineering fields such as circuit board design, logistics route planning, and astronomical observation planning. In this project, I formulate new quantum algorithms using both Quantum Annealing and Quantum Circuits, both of which leverage quantum superposition and have a significant computational advantage over classical computing. Quantum Annealing is a form of quantum computing that uses quantum fluctuations to find the global minimum of an objective function. I propose a novel mathematical objective function which uses penalty functions, each of which represent a rule to the TSP, leading to a new solution to solve the TSP with a substantially lower time complexity than conventional computing. The proposed quantum annealing algorithm was run on the D-Wave quantum computer, which produced the correct solution. I also propose a quantum circuit solution, using a modified version of the Quantum Search Algorithm. This project shows two novel quantum algorithms to solve the TSP, both of which have significant computational advantages over classical computers.

Competition history

• ISEF 2023 Physics and Astronomy · Entry PHYS041 · Dallas, Texas, United States Affiliated fair in IN, United States of America

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.