Løse ‘The Travelling Salesman Problem’ med kvanteberegning

Et klassisk algoritmisk problem innen datavitenskap, kjent som Traveling Salesman Problem (TSP), er et fremragende eksempel på et kombinatorisk optimaliseringsproblem.

Hva er egentlig TSP? Dette matematiske klassikeren innebærer å finne den korteste mulige ruten for å besøke N antall byer nøyaktig én gang før man vender tilbake til startbyen. Men etter hvert som antallet byer øker, øker også antallet mulige ruter og beregningstiden for å finne den optimale løsningen. Selv om dette problemet kan løses ved hjelp av tilnærmingsmetoder, kan kvantedatamaskiner levere mye bedre løsninger og det mye raskere.

Dette er akkurat det teoretisk fysiker Prof. Dr. Jens Eiserts team demonstrerte at slike problemer kan løses bedre og raskere med kvantedatamaskiner.

Kvanteberegning bruker maskinvare og algoritmer som utnytter kvantemekanikk for å løse komplekse problemer som ligger utenfor rekkevidden til konvensjonelle, inkludert superdatamaskiner. Til tross for deres kraft, er superdatamaskiner—massive klassiske datamaskiner med tusenvis av CPU- og GPU-kjerner—begrenset av sin avhengighet av transistor‑teknologi fra 1900‑tallet når de løser problemer med høy kompleksitet.

Dette er hvor kvantefysikk kommer inn. I motsetning til klassiske datamaskiner, som koder informasjon i binære biter (0 og 1), bruker kvantedatamaskiner kvantebiter eller qubits for å kjøre multidimensjonale kvantealgoritmer.

Videre, i motsetning til konvensjonelle datamaskiner som bruker vifter for kjøling, krever kvantedatamaskiner at deres kvanteprosessorer holdes ved ekstremt lave temperaturer for å bevare sine kvantetilstander. Dette oppnås gjennom superkjølte supervæsker.

Superledere er materialer som viser en kritisk kvantemekanisk effekt, som gjør at elektroner kan bevege seg gjennom dem uten motstand. Når elektroner passerer, danner de par for å transportere en ladning over barrierer. Når to superledere plasseres på hver side av en isolator, dannes en Josephson‑kobling, som brukes til å lede superledende qubits.

En qubit er nyttig i den viktige oppgaven med å plassere sin kvanteinformasjon i en superposisjonstilstand, en kombinasjon av qubitens mulige konfigurasjoner. Grupper av qubits i superposisjon kan skape komplekse, multidimensjonale beregningsrom hvor komplekse problemer kan representeres.

Her, ved sammenfiltring av to qubits, kan endringer i den ene påvirke den andre direkte, mens når disse sammenfiltrede qubits plasseres i en superposisjonstilstand, får vi et stort antall sannsynligheter. Beregning på en kvantedatamaskin fungerer ved å forberede en superposisjon av alle mulige beregningstilstander, og gjennom interferens blir løsninger funnet.

Selvfølgelig er bygging av en kvantedatamaskin med mange qubits en svært kompleks prosedyre, selv om flere metoder blir utforsket for hva slike datamaskiner kan oppnå.

Ifølge Eisert, som leder en felles forskningsgruppe ved Helmholtz‑Zentrum Berlin (HZB), et forskningssenter for energimaterialer, og den offentlige forskningsuniversiteten Freie Universität Berlin:

“Det finnes mange myter om det, og noen ganger en viss mengde tomme ord og hype. Imidlertid har vi tilnærmet oss problemet grundig, ved å bruke matematiske metoder, og levert solide resultater på temaet. Fremfor alt har vi klargjort i hvilken forstand det kan finnes noen fordeler i det hele tatt.”

Det kritiske Traveling Salesman‑problemet

Et optimaliseringsproblem, TSP, har stor økonomisk betydning innen logistikk‑ og forsyningskjedeutvalget. Det faller inn under den bredere kategorien av kombinatoriske optimaliseringsproblemer, som også inkluderer jobbplanlegging, ressursallokering, porteføljeoptimalisering og til og med proteinfolding, alle kritiske for ulike sektorer.

Gitt den sosiale og økonomiske betydningen av disse problemene, har de vært gjenstand for intens forskning. Som sådan har det å finne svaret på problemer som den mest effektive forsyningskjeden og den billigste leveringsruten en positiv innvirkning på vårt daglige liv.

Imidlertid gjør optimalisering av leveringsruter for flere destinasjoner, samtidig som man tar hensyn til ulike begrensninger som trafikkbelastning, økende driftskostnader, plutselige ruteendringer, siste‑minutts forretningsavtaler og kundebehov, TSP enda mer utfordrende å løse. Til tross for disse utfordringene er løsning av TSP avgjørende for effektiv levering av varer, noe som sikrer en levedyktig forretningsmodell.

Det er mange fordeler ved å løse dette problemet, inkludert reduksjon av tilbakelagt avstand og timer samt sparing av drivstoff. Å minimere den tilbakelagte avstanden kan bidra til å redusere karbonavtrykket betydelig, noe som gir bedre luftkvalitet, bremser klimaendringene og fremmer økonomisk vekst. Videre kan løsning av TSP bidra til rettidig levering av varer og tidsriktige møter med kunder, noe som forbedrer kundeopplevelsen og feltservicevirksomheter.

Som vi har sett, hjelper løsning av problemet ikke bare bedrifter, men disse fordelene renner også ned til kundene, og beriker opplevelsen for alle involverte.

Flere metoder kan brukes for å løse TSP‑problemet. En slik metode er ‘Brute‑Force’-tilnærmingen, som beregner alle mulige permutasjoner for å finne den korteste ruten. I branch‑and‑bound‑metoden deles problemet opp i flere serier av delproblemer, hvor hver fases løsning påvirker løsningen som finnes i påfølgende faser.

I dynamisk programmering er fokuset på å unngå overflødige beregninger. Nearest Neighbor er derimot en tilnærmingsalgoritme hvor du starter fra startpunktet og deretter går til den nærmeste. Når alle byene er dekket, går du tilbake til startpunktet. Selv om den er praktisk og relativt rask, gir denne metoden kanskje ikke alltid en effektiv rute.

Etter hvert som teknologien utvikler seg, kan ruteplanlegging og optimalisering gjøres langt mer effektivt. Kunstig intelligens (AI) kan spesielt også bidra til å løse problemet ved å raskt analysere enorme mengder data for å hjelpe moderne virksomheter med operasjonelle og strategiske beslutninger.

Kvantedatamaskiner blir også undersøkt for å løse problemet; de gir tross alt betydelige beregningsforbedringer sammenlignet med klassiske datamaskiner. Det har lenge blitt antydet at disse maskinene kan bidra til å forbedre tilnærmingene til disse problemene.

Bruke kvanteberegningsteknikker for å løse TSP

Mens kvanteberegning får enorm interesse og gir lovende resultater for visse problemer, er omfanget av dette kvantefordelen fortsatt stort sett uutforsket.

Dermed ga studien full konstruktiv bevis på at kvantedatamaskiner faktisk kan overgå konvensjonelle datamaskiner når det gjelder å finne tilnærminger til kombinatoriske optimaliseringsproblemer.

Den nyeste studien, ledet av Eisert og hans kollega Jean‑Pierre Seifert, brukte kun analytiske metoder for å evaluere hvor godt en kvantedatamaskin med qubits kan løse TSP‑problemet.

“Vi antar simpelthen, uavhengig av den fysiske realiseringen, at det finnes nok qubits og ser på mulighetene for å utføre beregningsoperasjoner med dem,” noe som viser en likhet med et vanlig problem innen kryptografi, dvs. kryptering av data, forklarte Vincent Ulitzsch, Ph.D.-student ved Tekniske Universitetet i Berlin.

Deretter brukte teamet Shor‑algoritmen, en kvantealgoritme, for å finne primtallsfaktorene til et helt tall og løse en underklasse av disse optimaliseringsproblemene. Med dette vil beregningstiden ikke lenger eksplodere når antallet byer øker. Den vil kun øke polynomisk, dvs. med Nx, hvor x er en konstant. På denne måten er den oppnådde løsningen også kvalitativt mye bedre enn det som avledes fra den tilnærmede løsningen ved bruk av den konvensjonelle algoritmen.

Ved å bruke kryptografiske konsepter og beregningslæringsteori gir studien “fullt konstruktivt bevis på at kvantedatamaskiner har en superpolynomisk fordel over klassiske datamaskiner når de tilnærmer seg kombinatoriske optimaliseringsproblemer.”

Studien bemerket videre at forskerteamet har gjort betydelige fremskritt i det viktige spørsmålet om hva potensielle kvantedatamaskiner kan tilby for å tilnærme løsningen av kombinatoriske optimaliseringsproblemer, som har betydelige sosiale og økonomiske virkninger.

Studien ble finansiert av Einstein Research Unit, Berlin Mathematics Research Center (MATH+ Cluster of Excellence), BMBF (Hybrid), BMWK (EniQmA), Munich Quantum Valley og DFG. Det føderale tyske utdannings‑ og forskningsdepartementet bidro også med økonomisk støtte.

Utforske kvanteberegningens potensial 

Selv om det er en stor prestasjon, var dette ikke første gang kvanteberegning har blitt brukt til å løse traveling salesman‑problemet. Det har vært mange tilfeller av entusiaster og forskere som har undersøkt å løse problemet ved å bruke kvanteberegning.

I desember 2022 foreslo en artikkel en kvantealgoritme for TSP basert på Grover Adaptive Search (GAS). Under GAS‑rammeverket finnes det minst to grunnleggende vanskeligheter—løsninger kan være urealistiske, og antallet qubits i dagens kvantedatamaskiner er svært begrenset og kan ikke oppfylle minimumskravene, noe som begrenser bruken av kvantealgoritmer for kombinatoriske optimaliseringsproblemer.

Dermed forbedret artikkelen Hamiltonian Cycle Detection (HCD)-orakelet, som automatisk kan fjerne upraktiske løsninger under algoritmekjøringen. De designet også en “anchor register”-strategi for å spare qubit‑bruk, med full hensyn til reversibilitetskravet i kvanteberegning og overvinne vanskeligheten med at brukte qubits ikke bare kan overskrives eller frigjøres. Dette gjorde at studien kun krevde 31 qubits, og løsningen hadde en suksessrate på 86,71 %.

I 2019 skrev fysikkentusiasten Joseph Cammidge om bruk av en kvante‑annealer, som gjorde ham i stand til å løse traveling salesman‑problemet for syv byer og har teoretisk potensial til å løse for ni byer når teknologiske begrensninger er fjernet.

En ny beregningsmetode, kvante‑annealing, har vist potensial til å løse optimaliseringsproblemer raskere enn klassiske teknikker. Teorien innebærer at qubits vil oppnå en optimal lavenergitilstand når de er superkjølt.

Imidlertid fant en studie i 2021, finansiert av Supply Chain Digital & Data Science, Johnson & Johnson (JNJ ), at kvante‑annealeren kun kan håndtere et problem med 8 eller færre noder, og ytelsen er underlegen både i tid og nøyaktighet sammenlignet med den klassiske løseren.

Bruken av kvanteberegning for å løse TSP‑problemet har pågått en stund nå. Over to tiår siden, i 2001, begynte en studie å lete etter en kvantealgoritme for å løse problemet.

I artikkelen undersøkte Buckley Hopper fra University of Alabama Grovers og Shors kvantealgoritmer. Han bemerket at Grovers algoritme kun gir en kvadratrotforbedring, noe som innebærer at den ikke kan gjøre et klassisk uløselig problem løselig på en kvantedatamaskin. Når det gjelder Shors algoritme, observerte Hopper at, selv om den kan konvertere et antatt uløselig primtallsfaktorproblem til et løselig på den kvantebaserte maskinen, er den kun egnet for en svært spesifikk type problem.

Alt i alt fant Hopper at “han ikke oppnådde et tilfredsstillende resultat for en algoritme som beregner tilnærmede løsninger på traveling salesman‑problemet.”

Noen år senere presenterte Institute of Electrical and Electronics Engineers (IEEE) en ny algoritme for å løse problemet, inspirert av både genetiske algoritmer og kvanteberegning. IEEE fant at resultatene fra anvendelsen av den foreslåtte algoritmen på noen forekomster av Traveling Salesman Problem er betydelig bedre enn de som leveres av standard genetiske algoritmer.

Klikk her for å lære om den nåværende tilstanden til kvanteberegning.

Selskaper som jobber med kvanteberegning 

La oss nå se på noen navn som arbeider med forskning og utvikling av kvanteberegning:

#1. IBM

International Business Machines Corporation (IBM ) er engasjert i et bredt spekter av sektorer, inkludert AI, skytjenester, IT, klientfinansiering og kommersiell finansiering. Teknologigiganten er også involvert i kvanteberegning via sin IBM Quantum Platform, som gir offentlig og premium tilgang til sine skybaserte kvanteberegningstjenester. Disse inkluderer et sett med IBMs prototype kvanteprosessorer, opplæringsprogrammer i kvanteberegning og en interaktiv lærebok.

Nylig uttalte IBM-forskere at de er ett skritt nærmere å overvinne et hinder som låser opp det spillendrende potensialet til kvantedatamaskiner. For dette introduserte de en ny kvantefeilkorrigeringskode, som de sier er omtrent ti ganger mer effektiv enn tidligere metoder.

Sent på slutten av året lanserte selskapet også kvantedatamaskinen kalt Condor, med 1 121 superledende qubits arrangert i et bikake‑mønster. IBM avduket også IBM Quantum System Two, sin første modulære kvantedatamaskin og kvante‑sentrerte superdatamaskinarkitektur, som er skalerbar og dermed kan oppgraderes med chips som vil bli lansert i løpet av de neste fem årene.

Med en markedsverdi på 175 milliarder dollar, handles IBMs aksjer til $190,86, opp 16,66 % år‑til‑dato (YTD). IBM har rapportert inntekter (TTM) på 61,86 milliarder dollar, med en EPS (TTM) på 8,03, P/E (TTM) på 23,76, og ROE (TTM) på 33,36 %. Selskapet betaler en utbytteavkastning på 3,48 %.

#2. D‑Wave Systems

Dette kvanteberegningsselskapet utvikler og leverer relaterte systemer, programvare og tjenester. Produktene deres inkluderer The Leap og The Advantage, og de tilbyr kvanteapplikasjoner for planlegging, logistikk, legemiddelforskning, produksjonsprosesser og mer.

Tidligere denne måneden uttalte D‑Wave at kvantemaskiner nå kan løse problemer med virkelige anvendelser raskere enn noen vanlig datamaskin. Tidligere i år kunngjorde selskapet en kvantedatamaskin med 1 200 qubits, 10 000 koblere og en 20‑ganger raskere tid‑til‑løsning på vanskelige optimaliseringsproblemer.

Selskapets aksjer handles for tiden til $1,86, opp 138,6 % år‑til‑dato (YTD), med en markedsverdi på 267 millioner dollar. Det rapporterte $8,247 millioner i salg (TTM), -0,66 EPS (TTM), og -3,19 P/E (TTM), og kunngjorde over 20 % vekst i salg for både Q4 og årsslutt 2023, mens bestillinger økte med henholdsvis 34 % og 89 %.

Interessant nok erklærte selskapets administrerende direktør, Dr. Alan Baratz, firmaets fremdrift, og nevnte selskapets flerårige strategiske partnerskap med Zapata AI, introduksjonen av 1 200+ qubit Advantage2‑prototypen, joint ventures med NEC Australia og Deloitte Canada, samt utnevnelsen av tidligere Homeland Security‑secretær Kirstjen Nielsen til styret.

Konklusjon

Markedet for kvanteberegning forventes å reach $6.5 billion i 2028, og potensialet til å løse Traveling Salesman Problem (TSP) har konsekvenser for flere industrier, som produksjon, logistikk, forsyningskjedeledelse, netthandel, transport og forskning. Til syvende og sist kan det føre til betydelige fordeler, spesielt økt produktivitet, reduserte kostnader og stimulert innovasjon på tvers av ulike sektorer.

Klikk her for listen over de fem beste kvanteberegningsselskapene.