Solving the traveling salesman problem with D-Wave's hybrid quantum-classical solver
(2024) FYSK04 20241Department of Physics
- Abstract
- The traveling salesman problem (TSP) is a well-known computationally hard problem often used to benchmark new optimization algorithms. With recent advances in the field of quantum computing, quantum optimization algorithms are emerging as promising new ways to potentially solve such problems that remain difficult for classical computers. However, most modern quantum processing units (QPUs) still lack the capacity to solve more complex problems requiring a large number of variables. Hybrid quantum-classical methods such as the hybrid solvers offered by D-Wave, have therefore been developed to compensate for the weaknesses of modern QPUs while also leveraging the suggested benefits. D-Wave's hybrid solver combines classical computation with... (More)
- The traveling salesman problem (TSP) is a well-known computationally hard problem often used to benchmark new optimization algorithms. With recent advances in the field of quantum computing, quantum optimization algorithms are emerging as promising new ways to potentially solve such problems that remain difficult for classical computers. However, most modern quantum processing units (QPUs) still lack the capacity to solve more complex problems requiring a large number of variables. Hybrid quantum-classical methods such as the hybrid solvers offered by D-Wave, have therefore been developed to compensate for the weaknesses of modern QPUs while also leveraging the suggested benefits. D-Wave's hybrid solver combines classical computation with the quantum optimization method of spin glass quantum annealing running on their Advantage QPUs. In this study we compared the performance of D-Wave's hybrid solver to two types of classical simulated annealing algorithms, in solving four TSP instances from the TSP benchmarking library TSPLIB. We found that the hybrid solver was unable to solve any of our selected TSPLIB instances, and that it does not yet appear to be competitive with efficient classical TSP heuristics. To find an explanation for this lacking performance, we created a custom graph where the ratio between the maximum and minimum edge weight was much smaller than that of most standard TSP graphs. The hybrid solver successfully solved this TSP, suggesting that the subpar performance stems from having to minimize the weighted sum in the spin glass energy function, which often contains weights varying significantly in scale. (Less)
- Popular Abstract (Swedish)
- Handelsresandeproblemet (the Traveling Salesman Problem, TSP) är ett välkänt optimeringsproblem som kan vara utmanade att lösa även för dagens mest kraftfulla datorer. Problemet är enkelt att formulera: en handelsresande ska hitta den kortaste vägen för att besöka N städer och sedan återvända till staden hen startade i. Svårigheten härstammar från att när antalet städer ökar i problemet, ökar också antalet möjliga resvägar så fort att det blir nästintill omöjligt att hitta den optimala vägen genom en fullständig sökning av alla alternativ. Trots denna utmaning har många algoritmer utvecklats för TSP-problemet och en stor andel lyckas hitta den optimala vägen, men med nackdelen att man inte alltid kan bekräfta att man hittat den bästa... (More)
- Handelsresandeproblemet (the Traveling Salesman Problem, TSP) är ett välkänt optimeringsproblem som kan vara utmanade att lösa även för dagens mest kraftfulla datorer. Problemet är enkelt att formulera: en handelsresande ska hitta den kortaste vägen för att besöka N städer och sedan återvända till staden hen startade i. Svårigheten härstammar från att när antalet städer ökar i problemet, ökar också antalet möjliga resvägar så fort att det blir nästintill omöjligt att hitta den optimala vägen genom en fullständig sökning av alla alternativ. Trots denna utmaning har många algoritmer utvecklats för TSP-problemet och en stor andel lyckas hitta den optimala vägen, men med nackdelen att man inte alltid kan bekräfta att man hittat den bästa lösningen förrän man senare utesluter alla andra vägar.
Utvecklingen av kvantdatorer de senaste åren har däremot möjliggjort helt nya lösningsmetoder. Genom att använda kvantbitar istället för klassiska bitar kan kvantdatorer utnyttja kvantmekaniska fenomen såsom superposition och tunneleffekten för att potentiellt skapa ännu snabbare optimeringsalgoritmer för dessa typer av svåra problem. Kvantdatorföretaget D-Wave Systems lanserade 2020 en sorts kvant-klassisk hybriddator som löser optimeringsproblem med hjälp av klassiska datorer som samarbetar med deras Advantage kvantdatorer. Detta ska göra det möjligt för större och mer komplexa problem att lösas med hjälp av kvantdatorer, då beräkningar på kvandatorer tidigare varit begränsade av bland annat totala mängden kvantbitar och antalet kvantbitar som kan sammanflätas.
I denna studie har vi använt D-Waves hybriddator för att försöka lösa fyra olika TSP-problem. Vi har också jämfört dess prestanda med klassiska lösningsmetoder. Våra resultat visade att hybriddatorn endast lyckades hitta approximativa lösningar till de fyra TSP-problemen. Vi kunde därav också konstatera att klassiska TSP-algoritmer fortfarande presterar bättre än hybridmetoden på typiska TSP-problem.
En liknande studie från 2022 som testade hybriddatorn för proteinveckning, vilket också är att svårt optimeringsproblem, visade dock att hybridmetoden presterade bättre än klassiska metoder. Därav undersökte vi även varför hybridmetoden presterade sämre på TSP-problem och fann att anledningen förmodligen är att de flesta TSP-problemen inkluderar städer som ligger både väldigt nära samt väldigt långt bort. Dessa skillnader i skalor blir problematiska för kvantdatorn att hantera då den inte har noggrannheten för att jobba på både väldigt stora och små energiskalor samtidigt. När vi konstruerade ett eget TSP-problem där avstånden inte hade stora skillnader i skala för att undersöka denna hypotes, lyckades hybridmetoden alltid hitta den optimala vägen. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9159019
- author
- Lindén Åsell, Tim LU
- supervisor
-
- Anders Irbäck LU
- Lucas Knuthson LU
- organization
- course
- FYSK04 20241
- year
- 2024
- type
- M2 - Bachelor Degree
- subject
- keywords
- traveling salesman problem, TSP, quantum computing, D-Wave, hybrid, combinatorial optimization, simulated annealing, quantum annealing, 2-opt, edge weights, QUBO, spin glass, computational physics, quantum optimization, TSPLIB, QPU
- language
- English
- id
- 9159019
- date added to LUP
- 2024-06-11 13:29:04
- date last changed
- 2024-06-11 13:29:04
@misc{9159019,
abstract = {{The traveling salesman problem (TSP) is a well-known computationally hard problem often used to benchmark new optimization algorithms. With recent advances in the field of quantum computing, quantum optimization algorithms are emerging as promising new ways to potentially solve such problems that remain difficult for classical computers. However, most modern quantum processing units (QPUs) still lack the capacity to solve more complex problems requiring a large number of variables. Hybrid quantum-classical methods such as the hybrid solvers offered by D-Wave, have therefore been developed to compensate for the weaknesses of modern QPUs while also leveraging the suggested benefits. D-Wave's hybrid solver combines classical computation with the quantum optimization method of spin glass quantum annealing running on their Advantage QPUs. In this study we compared the performance of D-Wave's hybrid solver to two types of classical simulated annealing algorithms, in solving four TSP instances from the TSP benchmarking library TSPLIB. We found that the hybrid solver was unable to solve any of our selected TSPLIB instances, and that it does not yet appear to be competitive with efficient classical TSP heuristics. To find an explanation for this lacking performance, we created a custom graph where the ratio between the maximum and minimum edge weight was much smaller than that of most standard TSP graphs. The hybrid solver successfully solved this TSP, suggesting that the subpar performance stems from having to minimize the weighted sum in the spin glass energy function, which often contains weights varying significantly in scale.}},
author = {{Lindén Åsell, Tim}},
language = {{eng}},
note = {{Student Paper}},
title = {{Solving the traveling salesman problem with D-Wave's hybrid quantum-classical solver}},
year = {{2024}},
}