Løsning af ‘Traveling Salesman Problem’ gennem kvantecomputing

Et klassisk algoritmisk problem inden for datalogi, kendt som Traveling Salesman Problem (TSP), er et fremragende eksempel på et kombinatorisk optimeringsproblem.

Hvad er TSP egentlig? Denne matematiske klassiker involverer at finde den korteste mulige rute for at besøge N antal byer præcis én gang, før man vender tilbage til udgangspunktet. Men efterhånden som antallet af byer stiger, gør også antallet af mulige ruter og beregningstiden for at finde den optimale løsning. Mens dette problem kan løses ved hjælp af tilnærmningsmetoder, kan kvantecomputere levere meget bedre løsninger og langt hurtigere.

Dette er præcis, hvad den teoretiske fysiker Prof. Dr. Jens Eiserts team demonstrerede: at sådanne problemer kan løses bedre og hurtigere med kvantecomputere.

Kvantecomputing bruger hardware og algoritmer, der udnytter kvantemekanik til at løse komplekse problemer, som ligger uden for rækkevidden af konventionelle, inklusive supercomputere. På trods af deres kraft er supercomputere – massive klassiske computere med tusindvis af CPU- og GPU-kerner – begrænset af deres afhængighed af transistor-teknologi fra det 20. århundrede, når de løser problemer med høj kompleksitet.

Det er her kvantefysik kommer ind i billedet. I modsætning til klassiske computere, som koder information i binære bits (0 og 1), bruger kvantecomputere kvantebits eller qubits til at køre multidimensionale kvantealgoritmer.

Desuden, i modsætning til konventionelle computere, som bruger blæsere til køling, kræver kvantecomputere, at deres kvanteprocessorer holdes ved ekstremt lave temperaturer for at bevare deres kvantetilstande. Dette opnås gennem superkølede superflydende.

Superledere er materialer, der udviser en kritisk kvantemekanisk effekt, som tillader elektroner at bevæge sig gennem dem uden modstand. Når elektroner passerer, danner de par for at transportere en ladning over barrierer. Når to superledere placeres på hver side af en isolator, dannes en Josephson‑kobling, som bruges til at drive superledende qubits.

En qubit er nyttig i den vigtige opgave at placere sin kvanteinformation i en superpositions‑tilstand, en kombination af qubitens mulige konfigurationer. Grupper af qubits i superposition kan skabe komplekse, multidimensionale beregningsrum, hvor komplekse problemer kan repræsenteres.

Her kan sammenfiltringen af to qubits få ændringer i den ene til at påvirke den anden direkte, mens når disse sammenfiltrede qubits placeres i en superpositions‑tilstand, får vi utallige sandsynligheder. Beregning på en kvantecomputer fungerer ved at forberede en superposition af alle mulige beregningstilstande, og gennem interferens findes løsninger.

Selvfølgelig er opbygning af en kvantecomputer med mange qubits en meget kompleks proces, selvom flere metoder undersøges for, hvad sådanne computere kan opnå.

Ifølge Eisert, som leder en fælles forskningsgruppe ved Helmholtz‑Zentrum Berlin (HZB), et forskningscenter for energimaterialer, og den offentlige forskningsuniversitet Freie Universität Berlin:

“Der er mange myter om det, og nogle gange en vis mængde blæst og hype. Men vi har behandlet problemet grundigt, ved brug af matematiske metoder, og leveret solide resultater på området. Frem for alt har vi afklaret i hvilken forstand der overhovedet kan være nogen fordele.”

Det kritiske Traveling Salesman Problem

Et optimeringsproblem, TSP har stor økonomisk betydning inden for logistik‑ og forsyningskædeindustrien. Det falder inden for den bredere kategori af kombinatoriske optimeringsproblemer, som også inkluderer jobplanlægning, ressourceallokering, porteføljeoptimering og endda proteinfoldning, alle kritiske for forskellige sektorer.

Givet den sociale og økonomiske betydning af disse problemer, har de været genstand for intens forskning. Som sådan har det at finde svar på problemer som den mest effektive forsyningskæde og den billigste leveringsrute en positiv indvirkning på vores daglige liv.

Dog gør optimering af leveringsruter for flere destinationer, mens man tager højde for forskellige begrænsninger såsom trafikpropper, stigende driftsomkostninger, pludselige ruteændringer, sidste‑øjebliks forretningsaftaler og kundebehov, TSP endnu mere udfordrende at løse. På trods af disse udfordringer er løsning af TSP afgørende for effektiv levering af varer, hvilket sikrer en levedygtig forretningsmodel.

Der er mange fordele ved at løse dette problem, herunder at reducere den tilbagelagte distance og timer samt spare brændstofforbrug. At minimere den tilbagelagte distance kan hjælpe med at reducere CO₂‑aftrykket betydeligt, hvilket fører til bedre luftkvalitet, langsommere klimaændringer og økonomisk vækst. Desuden kan løsning af TSP hjælpe med rettidig levering af varer og møder med kunder, hvilket forbedrer kundeoplevelsen og feltservicevirksomheder.

Som vi har set, hjælper løsning af problemet ikke kun virksomheder, men disse fordele strømmer også ned til kunderne, hvilket beriger oplevelsen for alle involverede.

Flere metoder kan anvendes til at løse TSP‑problemet. En sådan metode er ‘Brute‑Force’-tilgangen, som beregner alle mulige permutationer for at finde den korteste rute. I branch‑and‑bound‑metoden deles problemet op i flere serier af delproblemer, hvor hver løsningsfase påvirker den løsning, der findes i efterfølgende faser.

I dynamisk programmering er fokus på at undgå overflødige beregninger. Nearest Neighbor er derimod en tilnærmningsalgoritme, hvor du starter ved udgangspunktet og derefter stopper ved den nærmeste. Når alle byerne er besøgt, vender du tilbage til startpunktet. Selvom den er praktisk og relativt hurtig, giver denne metode ikke altid en optimal rute.

Efterhånden som teknologien udvikler sig, kan ruteplanlægning og optimering udføres langt mere effektivt. Kunstig intelligens (AI) kan især hjælpe med at løse problemet ved hurtigt at analysere enorme datamængder, så mange moderne virksomheder kan træffe operationelle og strategiske beslutninger.

Kvantecomputere undersøges også for at løse problemet; de tilbyder nemlig betydelige beregningshastighedsforøgelser i forhold til klassiske computere. Det har længe været antydet, at disse computere faktisk kan forbedre tilnærmelserne til sådanne problemer.

Brug af kvantecomputing‑teknikker til at løse TSP

Mens kvantecomputing får enorm interesse og leverer lovende resultater for visse problemer, er omfanget af denne kvantefordel stadig stort set uudforsket.

Som sådan leverede undersøgelsen fuld konstruktiv bevis for, at kvantecomputere faktisk kan overgå konventionelle computere i at finde tilnærmelser til kombinatoriske optimeringsproblemer.

Den seneste undersøgelse, ledet af Eisert og hans kollega Jean‑Pierre Seifert, brugte kun analytiske metoder til at evaluere, hvor meget en kvantecomputer med qubits kan løse TSP‑problemet.

“Vi antager simpelthen, uanset den fysiske realisering, at der er nok qubits og ser på mulighederne for at udføre beregningsoperationer med dem,” hvilket afslører en lighed med et almindeligt problem inden for kryptografi, dvs. datakryptering, forklarede Vincent Ulitzsch, Ph.D.-studerende ved Technische Universität Berlin.

Derefter brugte teamet Shor‑algoritmen, en kvantealgoritme, til at finde de primære faktorer af et heltal og løse en underklasse af disse optimeringsproblemer. Med det vil beregningstiden ikke længere eksplodere, når antallet af byer stiger. Den vil kun vokse polynomisk, dvs. med Nx, hvor x er en konstant. På denne måde er den opnåede løsning også kvalitativt meget bedre end den, der udledes fra den tilnærmede løsning ved brug af den konventionelle algoritme.

Ved at bruge kryptografiske koncepter og beregningslæringsteori giver undersøgelsen “fuldt konstruktivt bevis på, at kvantecomputere har en super‑polynomisk fordel over klassiske computere i tilnærmelse af kombinatoriske optimeringsproblemer.”

Undersøgelsen bemærkede yderligere, at forskerteamet har gjort betydelige fremskridt med det vigtige spørgsmål om, hvad potentielle kvantecomputere kan tilbyde for at tilnærme løsningen af kombinatoriske optimeringsproblemer, som har betydelige sociale og økonomiske virkninger.

Undersøgelsen blev finansieret af Einstein Research Unit, Berlin Mathematics Research Center (MATH+ Cluster of Excellence), BMBF (Hybrid), BMWK (EniQmA), Munich Quantum Valley og DFG. Det tyske Forbundsministerium for Uddannelse og Forskning ydede også økonomisk støtte.

Udforskning af kvantecomputings potentiale

Selvom det er en stor præstation, var det ikke første gang, at kvantecomputing er blevet brugt til at løse traveling salesman‑problemet. Der har været mange tilfælde af entusiaster og forskere, der har undersøgt at løse problemet ved hjælp af kvantecomputing.

I december 2022 foreslog en artikel en kvantealgoritme for TSP baseret på Grover Adaptive Search (GAS). Under GAS‑rammen er der mindst to grundlæggende vanskeligheder – løsninger kan være urealistiske, og antallet af qubits i nuværende kvantecomputere er meget begrænset og kan ikke opfylde minimumskravene, hvilket begrænser anvendelsen af kvantealgoritmer til kombinatoriske optimeringsproblemer.

Som sådan forbedrede artiklen Hamiltonian Cycle Detection (HCD) oraklet, som automatisk kan fjerne upraktiske løsninger under algoritmeudførelsen. De designede også en “anchor register”-strategi for at spare qubit‑forbrug, fuldt ud under hensyntagen til kvantecomputings reversibilitetskrav og overkomme vanskeligheden ved, at de anvendte qubits ikke blot kan overskrives eller frigives. Dette gjorde det muligt for studiet at kræve kun 31 qubits, og løsningen havde en succesrate på 86,71%.

I 2019 skrev den selvdefinerede fysikentusiast Joseph Cammidge om brug af en annealing kvanteprocessor, som gjorde det muligt for ham at løse traveling salesman‑problemet for syv byer og har det teoretiske potentiale til at løse for ni byer, når teknologiske begrænsninger elimineres.

En ny beregningsmetode, kvante‑annealing, har vist potentiale til at løse optimeringsproblemer hurtigere end klassiske teknikker. Dens teori antyder, at qubits vil opnå en optimal lavenergi‑tilstand, når de er superkølede.

Dog i 2021 fandt en undersøgelse finansieret af Supply Chain Digital & Data Science, Johnson & Johnson, at kvante‑annealeren kun kan håndtere en problemstørrelse på 8 eller færre noder, og dens ydeevne er underlegen både i tid og nøjagtighed sammenlignet med den klassiske løser.

Brugen af kvantecomputing til at løse TSP‑problemet har stået på i et stykke tid nu. Over to årtier siden, i 2001, begyndte en undersøgelse at søge efter en kvantealgoritme til at løse problemet.

I artiklen undersøgte Buckley Hopper fra University of Alabama Grovers og Shors kvantecomputer‑algoritmer. Han bemærkede, at Grovers algoritme kun giver en kvadratrodsforbedring, hvilket indebærer, at den ikke kan gøre et klassisk uoverkommeligt problem håndterbart på en kvantecomputer. Hvad angår Shors algoritme, observerede Hopper, at selvom den kan omdanne et formodet uoverkommeligt primfaktorproblem til et håndterbart problem på den kvantemaskine, er den kun egnet til en meget specifik type problem.

Samlet set fandt Hopper “ikke et tilfredsstillende resultat for en algoritme til beregning af tilnærmede løsninger på traveling salesman‑problemet.”

Et par år senere præsenterede Institute of Electrical and Electronics Engineers (IEEE) en ny algoritme til at løse problemet, inspireret af både genetiske algoritmer og kvantecomputing. IEEE fandt, at resultaterne fra anvendelsen af den foreslåede algoritme på nogle forekomster af Traveling Salesman Problem er betydeligt bedre end dem, der leveres af standard genetiske algoritmer.

Klik her for at lære om den aktuelle tilstand af kvantecomputing.

Virksomheder, der arbejder med kvantecomputing

Lad os nu se på et par navne, der arbejder med forskning og udvikling af kvantecomputing:

#1. IBM

International Business Machines Corporation er engageret i en bred vifte af sektorer, herunder AI, cloud‑tjenester, IT, klientfinansiering og kommerciel finansiering. Teknologigiganten er også involveret i kvantecomputing via sin IBM Quantum Platform, som giver offentlig og premium adgang til sine cloud‑baserede kvantecomputing‑tjenester. Disse inkluderer et sæt af IBMs prototype kvanteprocessorer, tutorials om kvanteberegning og en interaktiv lærebog.

For nylig har IBM‑forskere udsagn at de er et skridt tættere på at overvinde en forhindring, der låser det spilskiftende potentiale i kvantecomputere. Til dette introducerede de en ny kvantefejlkorrektionskode, som de siger er omkring ti gange mere effektiv end tidligere metoder.

Sent sent år lancerede virksomheden også kvantecomputeren kaldet Condor, med 1.121 superledende qubits arrangeret i et bikubemønster. IBM præsenterede også IBM Quantum System Two, deres første modulære kvantecomputer og kvantecentrerede supercomputing‑arkitektur, som er skalerbar og derfor kan opgraderes med chips, der vil blive lanceret i de næste fem år.

Med en markedsværdi på 175 milliarder dollars handles IBMs aktier til $190,86, op 16,66% år‑til‑dato (YTD). IBM har rapporteret en omsætning (TTM) på 61,86 mia. $, mens EPS (TTM) er 8,03, P/E (TTM) 23,76, og ROE (TTM) 33,36%. Virksomheden betaler et udbytte på 3,48%.

#2. D‑Wave Systems

Dette kvantecomputing‑firma udvikler og leverer relaterede systemer, software og tjenester. Dets produkter inkluderer The Leap og The Advantage, og det leverer kvanteapplikationer til planlægning, logistik, lægemiddelforskning, fremstillingsprocesser og mere.

Tidligere denne måned sagde D‑Wave, at kvantemaskiner nu kan løse problemer med virkelige anvendelser hurtigere end enhver almindelig computer. Tidligere i år annoncerede virksomheden en kvantecomputer med 1.200 qubits, 10.000 couplers og en 20x hurtigere tid‑til‑løsning på hårde optimeringsproblemer.

Virksomhedens aktier handles i øjeblikket til $1,86, op 138,6% år‑til‑dato (YTD), med en markedsværdi på 267 millioner dollars. Den rapporterede $8,247 millioner i salg (TTM), -0,66 EPS (TTM), og -3,19 P/E (TTM), og annoncerede over 20% vækst i salget for både Q4 og årslut 2023, mens bookingerne steg med henholdsvis 34% og 89%.

Interessant nok erklærede virksomhedens administrerende direktør, Dr. Alan Baratz, firmaets momentum, og nævnte virksomhedens flerårige strategiske partnerskab med Zapata AI, introduktionen af 1.200+ qubit Advantage2‑prototypen, joint ventures med NEC Australia og Deloitte Canada, samt udnævnelsen af den tidligere Homeland Security Secretary Kirstjen Nielsen til bestyrelsen.

Konklusion

Markedet for kvantecomputing forventes at nå 6,5 milliarder dollars i 2028, og dets potentiale til at løse Traveling Salesman Problem (TSP) har konsekvenser for flere industrier, såsom fremstilling, logistik, forsyningskædestyring, e‑handel, transport og forskning. Endelig kan det resultere i betydelige fordele, især ved at øge produktiviteten, reducere omkostninger og fremme innovation på tværs af forskellige sektorer.

Klik her for listen over de fem bedste kvantecomputing‑virksomheder.