Het oplossen van het ‘Travelling Salesman Problem’ met quantum computing

Een klassiek algoritmisch probleem op het gebied van informatica, bekend als het Traveling Salesman Problem (TSP), is een uitstekend voorbeeld van een combinatorisch optimalisatieprobleem.

Wat is TSP precies? Deze wiskundige klassieker draait om het vinden van de kortst mogelijke route om N steden precies één keer te bezoeken voordat men terugkeert naar de vertrekstad. Naarmate het aantal steden toeneemt, nemen echter ook het aantal mogelijke routes en de rekentijd om de optimale oplossing te vinden toe. Terwijl dit probleem kan worden opgelost met benaderingsmethoden, zouden quantumcomputers veel betere oplossingen kunnen bieden en dat veel sneller.

Dit is precies wat theoretisch natuurkundige Prof. Dr. Jens Eisert’s team heeft aangetoond: dat dergelijke problemen beter en sneller kunnen worden opgelost met quantumcomputers.

Quantumcomputing maakt gebruik van hardware en algoritmen die de quantummechanica benutten om complexe problemen op te lossen die buiten het bereik van conventionele systemen, inclusief supercomputers, liggen. Ondanks hun kracht worden supercomputers – enorme klassieke computers met duizenden CPU- en GPU-kernen – beperkt door hun afhankelijkheid van transistorentechnologie uit de 20e eeuw bij het oplossen van problemen met een hoge complexiteit.

Hier komt de quantumfysica om de hoek kijken. In tegenstelling tot klassieke computers, die informatie coderen in binaire bits (0 en 1), gebruiken quantumcomputers quantumbits of qubits om multidimensionale quantumalgoritmen uit te voeren.

Bovendien, in tegenstelling tot conventionele computers die ventilatoren gebruiken voor koeling, moeten quantumcomputers hun quantumprocessoren op extreem lage temperaturen houden om hun quantumtoestanden te behouden. Dit wordt bereikt door supergekoelde supervloeistoffen.

Supergeleiders zijn materialen die een kritisch kwantummechanisch effect vertonen, waardoor elektronen er zonder weerstand doorheen kunnen bewegen. Terwijl elektronen passeren, vormen ze paren om een lading over barrières te dragen. Wanneer twee supergeleiders aan weerszijden van een isolator worden geplaatst, ontstaat een Josephson-junctie, die wordt gebruikt om supergeleidende qubits te geleiden.

Een qubit is nuttig bij de belangrijke taak om zijn quantuminformatie in een superpositie‑toestand te plaatsen, een combinatie van mogelijke configuraties van de qubit. Groepen qubits in superpositie kunnen complexe, multidimensionale rekenruimtes creëren waarin complexe problemen kunnen worden weergegeven.

Hier kan, door de verstrengeling van twee qubits, een wijziging in de ene direct de andere beïnvloeden, terwijl wanneer deze verstrengelde qubits in een superpositie‑toestand worden geplaatst, er talloze waarschijnlijkheden ontstaan. Rekenen op een quantumcomputer werkt door een superpositie van alle mogelijke rekenstaten voor te bereiden, en via interferentie worden oplossingen gevonden.

Natuurlijk is het bouwen van een quantumcomputer met veel qubits een zeer complex proces, hoewel verschillende methoden worden onderzocht om te bepalen wat zulke computers kunnen bereiken.

Volgens Eisert, die een gezamenlijk onderzoeksteam leidt bij Helmholtz‑Zentrum Berlin (HZB), een onderzoekscentrum voor energiematerialen, en de openbare universiteit Freie Universität Berlin:

“Er bestaan veel mythes erover, en soms een zekere hoeveelheid loze praat en hype. Echter, we hebben de kwestie grondig benaderd, met behulp van wiskundige methoden, en solide resultaten geleverd over het onderwerp. Bovenal hebben we verduidelijkt op welke manier er überhaupt voordelen kunnen zijn.”

The Critical Traveling Salesman Problem

Een optimalisatieprobleem, TSP is van groot economisch belang in de logistiek- en supply‑chain‑industrie. Het valt binnen de bredere categorie van combinatorische optimalisatieproblemen, die ook job‑planning, resource‑allocatie, portefeuille‑optimalisatie en zelfs eiwitvouwing omvatten, allemaal cruciaal voor diverse sectoren.

Gezien de sociale en economische betekenis van deze problemen, zijn ze het onderwerp van intensief onderzoek geweest. Het vinden van antwoorden op problemen zoals de meest efficiënte supply chain en de goedkoopste bezorgroute heeft een positieve impact op ons dagelijks leven.

Het optimaliseren van bezorgroutes voor meerdere bestemmingen, rekening houdend met diverse beperkingen zoals verkeersopstoppingen, stijgende operationele kosten, plotselinge routewijzigingen, last‑minute zakelijke afspraken en klantverzoeken, maakt TSP nog uitdagender om op te lossen. Ondanks deze uitdagingen is het oplossen van de TSP cruciaal voor een efficiënte levering van goederen, wat een levensvatbaar bedrijfsmodel garandeert.

Er zijn veel voordelen aan het oplossen van dit probleem, waaronder het verkorten van de afgelegde afstand en uren en het besparen van brandstofverbruik. Het minimaliseren van de afgelegde afstand kan de CO2‑voetafdruk aanzienlijk verminderen, wat leidt tot betere luchtkwaliteit, vertraagde klimaatverandering en economische groei. Bovendien kan het oplossen van de TSP helpen bij tijdige levering van goederen en tijdige afspraken met klanten, wat de klantervaring en veldservicebedrijven verbetert.

Zoals we hebben gezien, helpt het oplossen van het probleem niet alleen bedrijven, maar deze voordelen stromen ook door naar de klanten, waardoor de ervaring voor iedereen die betrokken is wordt verrijkt.

Verschillende methoden kunnen worden gebruikt om het TSP-probleem op te lossen. Eén dergelijke methode is de ‘Brute‑Force’-aanpak, die alle mogelijke permutaties berekent om de kortste route te vinden. In de branch‑and‑bound‑methode wordt het probleem opgesplitst in verschillende reeksen subproblemen, waarbij de oplossing van elke fase de oplossing van de volgende fasen beïnvloedt.

Bij dynamisch programmeren ligt de focus op het vermijden van overbodige berekeningen. De Nearest Neighbor is een benaderingsalgoritme waarbij je begint bij de startlocatie en vervolgens stopt bij de dichtstbijzijnde. Zodra alle steden zijn bezocht, keer je terug naar het startpunt. Hoewel praktisch en relatief snel, levert deze methode niet altijd een efficiënte route op.

Naarmate de technologie vordert, kan routeplanning en optimalisatie veel effectiever worden uitgevoerd. Kunstmatige intelligentie (AI) kan met name helpen het probleem op te lossen door snel enorme hoeveelheden data te analyseren, waardoor veel moderne ondernemingen operationele en strategische beslissingen kunnen nemen.

Quantumcomputers worden ook onderzocht om het probleem op te lossen; ze bieden immers aanzienlijke rekenversnellingen ten opzichte van klassieke computers. Er wordt al lange tijd gesuggereerd dat deze computers de benaderingen van deze problemen daadwerkelijk kunnen verbeteren.

Using Quantum Computing Techniques to Solve TSP

Hoewel quantumcomputing enorme interesse wekt en veelbelovende resultaten levert voor bepaalde problemen, blijft de mate van dit quantum‑voordeel grotendeels onontgonnen.

Daarom leverde de studie een volledig constructief bewijs dat quantumcomputers conventionele computers daadwerkelijk kunnen overtreffen bij het vinden van benaderingen voor combinatorische optimalisatieproblemen.

De nieuwste studie, geleid door Eisert en zijn collega Jean‑Pierre Seifert, gebruikte uitsluitend analytische methoden om te evalueren hoe een quantumcomputer met qubits het TSP-probleem kan oplossen.

“We gaan er simpelweg van uit, ongeacht de fysieke realisatie, dat er voldoende qubits zijn en kijken naar de mogelijkheden om rekenbewerkingen met hen uit te voeren,” wat een gelijkenis vertoont met een veelvoorkomend probleem in cryptografie, namelijk de encryptie van data, legt Vincent Ulitzsch, promovendus aan de Technische Universiteit van Berlijn, uit.

Vervolgens gebruikte het team het Shor-algoritme, een quantumalgoritme, om de priemfactoren van een geheel getal te vinden en een subklasse van deze optimalisatieproblemen op te lossen. Daarmee zal de rekentijd niet langer exponentieel toenemen naarmate het aantal steden stijgt. Het zal alleen polynomiaal toenemen, d.w.z. met Nx, waarbij x een constante is. Op deze manier is de verkregen oplossing ook kwalitatief veel beter dan wat wordt afgeleid van de benaderende oplossing met het conventionele algoritme.

Door cryptografische concepten en computationele leerteorie te gebruiken, levert de studie “volledig constructief bewijs dat quantumcomputers een super‑polynomiaal voordeel hebben ten opzichte van klassieke computers bij het benaderen van combinatorische optimalisatieproblemen.”

De studie merkte bovendien op dat het onderzoeksteam aanzienlijke vooruitgang heeft geboekt op de belangrijke vraag welke potentiële quantumcomputers kunnen bieden voor het benaderen van oplossingen voor combinatorische optimalisatieproblemen, die aanzienlijke sociale en economische impact hebben.

De studie werd gefinancierd door de Einstein Research Unit, het Berlin Mathematics Research Center (MATH+ Cluster of Excellence), het BMBF (Hybrid), het BMWK (EniQmA), de Munich Quantum Valley en de DFG. Het Federale Ministerie van Onderwijs en Onderzoek van Duitsland leverde ook financiële steun.

Exploring Quantum Computing’s Potential 

Hoewel een grote prestatie, was dit niet de eerste keer dat quantumcomputing werd gebruikt om het traveling salesman‑probleem op te lossen. Er zijn talloze voorbeelden van enthousiastelingen en onderzoekers die het probleem probeerden op te lossen met behulp van quantumcomputing.

In december 2022 stelde een paper een quantumalgoritme voor de TSP voor, gebaseerd op de Grover Adaptive Search (GAS). Binnen het GAS‑kader zijn er ten minste twee fundamentele moeilijkheden — oplossingen kunnen onhaalbaar zijn, en het aantal qubits van huidige quantumcomputers is zeer beperkt en kan niet voldoen aan de minimale vereisten, waardoor de toepassing van quantumalgoritmen voor combinatorische optimalisatieproblemen wordt beperkt.

Daarom verfijnde het paper de Hamiltonian Cycle Detection (HCD) oracle, die onpraktische oplossingen automatisch kan verwijderen tijdens de uitvoering van het algoritme. Ze ontwierpen ook een “anchor register”‑strategie om het qubit‑gebruik te besparen, volledig rekening houdend met de omkeerbaarheidsvereiste van quantumcomputing en het overwinnen van het probleem dat gebruikte qubits niet eenvoudig kunnen worden overschreven of vrijgegeven. Hierdoor kon de studie slechts 31 qubits vereisen, en behaalde de oplossing een succesratio van 86,71%.

In 2019 schreef zelfverklaarde natuurkundeliefhebber Joseph Cammidge over het gebruik van een quantum‑annealing‑processor, waarmee hij het traveling salesman‑probleem voor zeven steden kon oplossen en theoretisch potentieel heeft om negen steden op te lossen zodra technologische beperkingen zijn weggenomen.

Een nieuwe rekenmethode, quantum annealing, heeft het potentieel getoond om optimalisatieproblemen sneller op te lossen dan klassieke technieken. De theorie impliceert dat de qubits een optimale lage‑energietoestand bereiken wanneer ze supergekoeld zijn.

Echter, in 2021 toonde een studie, gefinancierd door Supply Chain Digital & Data Science, Johnson & Johnson (JNJ ), aan dat de quantum‑annealer slechts een probleemgrootte van 8 of minder knooppunten aankan, en dat de prestaties zowel qua tijd als nauwkeurigheid inferieur zijn aan de klassieke oplosser.

Het gebruik van quantumcomputing om het TSP‑probleem op te lossen, bestaat al geruime tijd. Meer dan twee decennia geleden, in 2001, begon een studie te zoeken naar een quantumalgoritme om het probleem op te lossen.

In het paper keek Buckley Hopper van de University of Alabama naar de quantumalgoritmen van Grover en Shor. Hij merkte op dat het Grover‑algoritme slechts een vierkantswortelverbetering biedt, wat impliceert dat het een klassiek onoplosbaar probleem niet oplosbaar maakt op een quantumcomputer. Wat betreft het Shor‑algoritme, observeerde Hopper dat, hoewel het een vermoedelijk onoplosbaar priemfactorprobleem kan omzetten in een oplosbaar probleem op de quantummachine, het slechts geschikt is voor een zeer specifiek type probleem.

Over het geheel genomen “vond Hopper geen bevredigend resultaat voor een algoritme om benaderende oplossingen voor het traveling salesman‑probleem te berekenen.”

Een paar jaar later presenteerde het Institute of Electrical and Electronics Engineers (IEEE) een nieuw algoritme voor het oplossen van het probleem, geïnspireerd door zowel genetische algoritmen als quantumcomputing. De IEEE vond dat de resultaten van de toepassing van het voorgestelde algoritme op enkele instanties van het Traveling Salesman Problem aanzienlijk beter waren dan die van standaard genetische algoritmen.

Klik hier om meer te leren over de huidige staat van quantumcomputing.

Companies Working with Quantum Computing 

Laten we nu een paar namen bekijken die werken aan onderzoek en ontwikkeling van quantumcomputing:

#1. IBM

International Business Machines Corporation (IBM ) is actief in een breed scala aan sectoren, waaronder AI, cloudservices, IT, klantfinanciering en commerciële financiering. De techgigant is ook betrokken bij quantumcomputing via zijn IBM Quantum Platform, dat publieke en premium toegang biedt tot zijn cloud‑gebaseerde quantumcomputing‑diensten. Deze omvatten een reeks prototype‑quantumprocessoren van IBM, tutorials over quantumcomputatie en een interactief leerboek.

Onlangs verklaarden IBM‑wetenschappers dat ze een stap dichterbij zijn bij het overwinnen van een obstakel dat het baanbrekende potentieel van quantumcomputers ontsluit. Hiervoor introduceerden ze een nieuwe quantum‑foutcorrigerende code, die volgens hen ongeveer tien keer efficiënter is dan eerdere methoden.

Eind vorig jaar lanceerde het bedrijf ook de quantumcomputer genaamd Condor, met 1.121 supergeleidende qubits die in een honingraatpatroon zijn gerangschikt. IBM onthulde ook IBM Quantum System Two, hun eerste modulaire quantumcomputer en quantum‑centrische supercomputing‑architectuur, die schaalbaar is en daarom kan worden geüpgraded met chips die de komende vijf jaar zullen worden gelanceerd.

Met een marktkapitalisatie van $175 miljard worden IBM‑aandelen verhandeld tegen $190,86, een stijging van 16,66 % jaar‑tot‑datum (YTD). IBM rapporteerde een omzet (TTM) van $61,86 miljard met een EPS (TTM) van 8,03, een P/E (TTM) van 23,76 en een ROE (TTM) van 33,36 %. Het bedrijf betaalt een dividendrendement van 3,48 %.

#2. D-Wave Systems

Dit quantumcomputing‑bedrijf ontwikkelt en levert gerelateerde systemen, software en diensten. Zijn producten omvatten The Leap en The Advantage, en het biedt quantumtoepassingen voor planning, logistiek, geneesmiddelenontdekking, productieprocessen en meer.

Eerder deze maand verklaarde D‑Wave dat quantummachines nu problemen met echte toepassingen sneller kunnen oplossen dan welke gewone computer dan ook. Begin dit jaar kondigde het bedrijf een quantumcomputer aan met 1.200 qubits, 10.000 couplers en een 20‑maal snellere time‑to‑solution bij harde optimalisatieproblemen.

De aandelen van het bedrijf worden momenteel verhandeld tegen $1,86, een stijging van 138,6 % jaar‑tot‑datum (YTD), met een marktkapitalisatie van $267 miljoen. Het rapporteerde $8,247 miljoen aan omzet (TTM), een EPS (TTM) van -0,66 en een P/E (TTM) van -3,19, en kondigde een groei van meer dan 20 % in de omzet voor zowel Q4 als het einde van 2023 aan, terwijl de boekingen respectievelijk met 34 % en 89 % toenamen.

Interessant genoeg verklaarde de CEO van het bedrijf, Dr. Alan Baratz, dat het momentum van het bedrijf voortkomt uit de meerjarige strategische samenwerking met Zapata AI, de introductie van de 1.200+‑qubit Advantage2‑prototype, joint ventures met NEC Australia en Deloitte Canada, en de benoeming van voormalig minister van Binnenlandse Veiligheid Kirstjen Nielsen in de raad van bestuur.

Conclusion

De markt voor quantumcomputing wordt verwacht een waarde van $6,5 miljard te bereiken in 2028, en het potentieel om het Traveling Salesman Problem (TSP) op te lossen heeft gevolgen voor verschillende industrieën, zoals productie, logistiek, supply‑chain‑management, e‑commerce, transport en onderzoek. Uiteindelijk kan het leiden tot aanzienlijke voordelen, met name een verhoging van de productiviteit, kostenreductie en het stimuleren van innovatie in diverse sectoren.

Klik hier voor de lijst van de beste vijf quantumcomputing‑bedrijven.