Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
QI: Fachverband Quanteninformation
QI 12: Quantum Computing Theory II
QI 12.5: Vortrag
Dienstag, 11. März 2025, 12:15–12:30, HS IV
Solving the travelling salesman problem on a quantum system — •Kapil Goswami1, Rick Mukherjee1,2, and Peter Schmelcher1,3 — 1The Center for Optical Quantum Technologies, University of Hamburg, Luruper Chaussee 149, 22761 Hamburg, Germany — 2Quantum Center, The University of Tennessee, 701 East Martin Luther King Boulevard, Chattanooga, USA — 3The Hamburg Centre for Ultrafast Imaging, University of Hamburg, Germany
The Traveling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization problem that seeks the optimal route for visiting a set of cities once and returning to the starting point. Current quantum methods for solving TSPs typically use gate-based or binary variable-based encoding, which is resource-intensive and less effective than classical algorithms, even for small problems. We present a framework that solves TSP using a single qubit, utilizing quantum parallelism. In this approach, cities are represented as quantum states on the Bloch sphere, allowing simultaneous exploration of multiple paths through superposition states. By employing optimal control techniques, a selective superposition of quantum states is created to find the shortest route. Numerical simulations for four to nine cities yield exact solutions. Our algorithm can be implemented on any quantum platform capable of rotating a qubit and facilitating state tomography. It demonstrates greater resource efficiency and accuracy compared to existing quantum methods, with potential for scalability and a polynomial speed-up over classical algorithms.
Keywords: Single qubit; Quantum parallelism; Non-QUBO; Travelling salesman problem; Optimal control