Lösa ‘The Travelling Salesman Problem’ med kvantberäkning

Ett klassiskt algoritmiskt problem inom datavetenskap, känt som Traveling Salesman Problem (TSP), är ett utmärkt exempel på ett kombinatoriskt optimeringsproblem.

Vad är egentligen TSP? Detta matematiska klassiker handlar om att hitta den kortaste möjliga rutten för att besöka N antal städer exakt en gång innan man återvänder till ursprungsstaden. Men när antalet städer ökar, ökar också antalet möjliga rutter och beräkningstiden för att hitta den optimala lösningen. Även om detta problem kan lösas med approximationsmetoder, kan kvantdatorer erbjuda mycket bättre lösningar och mycket snabbare.

Det är exakt vad teoretisk fysiker Prof. Dr. Jens Eiserts team demonstrerade: att sådana problem kan lösas bättre och snabbare med kvantdatorer.

Kvantberäkning använder hårdvara och algoritmer som utnyttjar kvantmekanik för att lösa komplexa problem som ligger bortom konventionella, inklusive superdatorer. Trots deras kraft är superdatorer—massiva klassiska datorer med tusentals CPU- och GPU-kärnor—begränsade av sitt beroende av transistor‑teknik från 1900‑talet när de löser problem med hög komplexitet. 

Det är här kvantfysiken kommer in. Till skillnad från klassiska datorer, som kodar information i binära bitar (0 och 1), använder kvantdatorer kvantbitar eller qubitar för att köra multidimensionella kvantalgoritmer. 

Dessutom, till skillnad från konventionella datorer som använder fläktar för kylning, kräver kvantdatorer att deras kvantprocessorer hålls vid extremt låga temperaturer för att bevara sina kvanttillstånd. Detta uppnås genom superkylda supervätskor. 

Supraledare är material som uppvisar en kritisk kvantmekanisk effekt, vilket tillåter elektroner att röra sig genom dem utan motstånd. När elektroner passerar, parar de sig för att bära en laddning över barriärer. När två supraledare placeras på vardera sidan av en isolator bildas en Josephson‑öron, som används för att leda supraledande qubitar.  

En qubit är användbar i den viktiga uppgiften att placera sin kvantinformation i ett tillstånd av superposition, en kombination av qubitens möjliga konfigurationer. Grupper av qubitar i superposition kan skapa komplexa, multidimensionella beräkningsrum där komplexa problem kan representeras.

Här, genom sammanflätning av två qubitar, kan förändringar i den ena direkt påverka den andra, medan när dessa sammanflätade qubitar placeras i ett superpositionstillstånd, får vi ett stort antal sannolikheter. Beräkning på en kvantdator fungerar genom att förbereda en superposition av alla möjliga beräkningstillstånd, och genom interferens hittas lösningarna.

Naturligtvis är konstruktionen av en kvantdator med många qubitar en mycket komplex process, även om flera metoder undersöks för vad sådana datorer kan åstadkomma. 

Enligt Eisert, som leder en gemensam forskargrupp vid Helmholtz‑Zentrum Berlin (HZB), ett forskningscenter för energimaterialforskning, och den offentliga forskningsuniversiteten Freie Universität Berlin:

“Det finns många myter om det, och ibland en viss mängd tomma ord och hype. Men vi har närmat oss frågan på ett rigoröst sätt, med matematiska metoder, och levererat solida resultat i ämnet. Framför allt har vi klargjort i vilken mening det kan finnas några fördelar alls.”

Det kritiska Traveling Salesman-problemet

Ett optimeringsproblem, TSP, har stor ekonomisk betydelse inom logistik‑ och leveranskedjeindustrin. Det faller inom den bredare kategorin av kombinatoriska optimeringsproblem, som också inkluderar jobbplanering, resursallokering, portföljoptimering och till och med proteinveckning, alla kritiska för olika sektorer.

Med tanke på den sociala och ekonomiska betydelsen av dessa problem har de varit föremål för intensiv forskning. Att hitta svaret på problem som den mest effektiva leveranskedjan och den billigaste leveransrutten har en positiv inverkan på våra dagliga liv.

Att optimera leveransrutterna för flera destinationer samtidigt som man beaktar olika begränsningar såsom trafikstockningar, ökande driftskostnader, plötsliga ruttändringar, sista‑minuten affärsmöten och kundförfrågningar gör TSP ännu mer utmanande att lösa. Trots dessa utmaningar är lösningen av TSP avgörande för en effektiv leverans av varor, vilket säkerställer en livskraftig affärsmodell. 

Det finns många fördelar med att lösa detta problem, inklusive minskning av avstånd och körda timmar samt besparing av bränsle. Att minimera det färdade avståndet kan avsevärt minska koldioxidavtrycket, vilket leder till bättre luftkvalitet, långsammare klimatförändringar och ekonomisk tillväxt. Dessutom kan lösningen av TSP hjälpa till med leverans av varor i tid och möten med kunder i tid, vilket förbättrar kundupplevelsen och fältserviceföretag.

Som vi har sett hjälper lösningen av problemet inte bara företag, utan dessa fördelar sprider sig även till kunderna, vilket berikar upplevelsen för alla inblandade.

Flera metoder kan användas för att lösa TSP-problemet. En sådan metod är ‘Brute‑Force’-metoden, som beräknar alla möjliga permutationer för att hitta den kortaste rutten. I gren‑och‑gräns‑metoden delas problemet upp i flera serier av delproblem, där varje stegslösning påverkar lösningen som hittas i efterföljande steg.

I dynamisk programmering ligger fokus på att undvika redundanta beräkningar. Närmaste granne‑algoritmen är en approximationsalgoritm där du börjar med startplatsen och sedan går till den närmaste. När alla städer har besökts återvänder du till startpunkten. Även om den är praktisk och relativt snabb, kan den ibland inte ge en effektiv rutt.

Allteftersom teknologin utvecklas kan ruttplanering och optimering göras mycket effektivare. Artificiell intelligens (AI) kan särskilt hjälpa till att lösa problemet genom att snabbt analysera enorma mängder data för att hjälpa moderna företag att fatta operativa och strategiska beslut.

Kvantdatorer undersöks också för att lösa problemet; de erbjuder nämligen betydande beräkningshastighetsökningar jämfört med klassiska datorer. Det har länge föreslagits att dessa datorer faktiskt kan förbättra approximationerna av dessa problem. 

Använda kvantberäkningstekniker för att lösa TSP

Medan kvantberäkning får enormt intresse och ger lovande resultat för vissa problem, är omfattningen av detta kvantfördel fortfarande i stor utsträckning outforskad. 

Som sådan gav studien ett fullständigt konstruktivt bevis på att kvantdatorer faktiskt kan överträffa konventionella datorer när det gäller att hitta approximationer till kombinatoriska optimeringsproblem.

Den senaste studien, ledd av Eisert och hans kollega Jean‑Pierre Seifert, använde endast analytiska metoder för att utvärdera hur en kvantdator med qubitar kan lösa TSP‑problemet. 

“Vi antar helt enkelt, oavsett den fysiska realiseringen, att det finns tillräckligt med qubitar och ser på möjligheterna att utföra beräkningsoperationer med dem,” vilket visar en likhet med ett vanligt problem inom kryptografi, dvs. kryptering av data, förklarar Vincent Ulitzsch, doktorand vid Tekniska universitetet i Berlin. 

Sedan använde teamet Shor‑algoritmen, en kvantalgoritm, för att hitta primfaktorerna för ett heltal och lösa en underklass av dessa optimeringsproblem. Med det kommer beräkningstiden inte längre explodera när antalet städer ökar. Den ökar bara polynomiskt, dvs. med Nx, där x är en konstant. På så sätt är den erhållna lösningen också kvalitativt mycket bättre än den som erhålls från den approximativa lösningen med den konventionella algoritmen.

Genom att använda kryptografiska koncept och beräkningslärningsteori ger studien ett “fullständigt konstruktivt bevis” på att kvantdatorer har ett superpolynomiskt försprång framför klassiska datorer när det gäller att approximera kombinatoriska optimeringsproblem. 

Studien noterade vidare att forskarteamet har gjort betydande framsteg i den viktiga frågan om vad potentiella kvantdatorer kan erbjuda för att approximera lösningen av kombinatoriska optimeringsproblem, vilka har betydande sociala och ekonomiska effekter.

Studien finansierades av Einstein Research Unit, Berlin Mathematics Research Center (MATH+ Cluster of Excellence), BMBF (Hybrid), BMWK (EniQmA), Munich Quantum Valley och DFG. Det tyska federala utbildnings‑ och forskningsministeriet bidrog också med finansiellt stöd.

Utforska kvantberäkningens potential 

Trots att det är en stor prestation var detta inte första gången kvantberäkning har använts för att lösa traveling salesman‑problemet. Det har funnits många fall där entusiaster och forskare har undersökt att lösa problemet med hjälp av kvantberäkning. 

I december 2022 föreslog en artikel ett kvantalgoritm för TSP baserad på Grover Adaptive Search (GAS). Inom GAS‑ramverket finns minst två grundläggande svårigheter—lösningarna kan vara otillgängliga, och antalet qubitar i nuvarande kvantdatorer är mycket begränsat och kan inte uppfylla minimikraven, vilket begränsar tillämpningen av kvantalgoritmer för kombinatoriska optimeringsproblem. 

Som sådan polerade artikeln Hamiltonian Cycle Detection (HCD)‑oraklet, som kan automatiskt ta bort opraktiska lösningar under algoritmens körning. De designade också en “anchor register”-strategi för att spara qubit‑användning, med full hänsyn till kvantberäkningens reversibilitetskrav och övervann svårigheten att använda qubitar som inte enkelt kan skrivas över eller släppas. Detta gjorde att studien krävde endast 31 qubitar, och lösningen hade en framgångsfrekvens på 86,71 %.

År 2019 skrev den självutnämnda fysikentusiasten Joseph Cammidge om att använda en kvant‑annealingsprocessor, vilket gjorde det möjligt för honom att lösa traveling salesman‑problemet för sju städer och har den teoretiska potentialen att lösa för nio städer när tekniska begränsningar elimineras. 

En ny beräkningsmetod, kvantannealing, har visat potential att lösa optimeringsproblem snabbare än klassiska tekniker. Dess teori innebär att qubitarna kommer att uppnå ett optimalt lågenergitillstånd när de är superkylda. 

Dock fann en studie finansierad av Supply Chain Digital & Data Science, Johnson & Johnson att kvantannealern endast kan hantera ett problem med högst 8 noder, och dess prestanda är underlägsen både i tid och noggrannhet jämfört med den klassiska lösaren.

Användningen av kvantberäkning för att lösa TSP‑problemet har pågått ett tag nu. Redan för mer än två decennier sedan, år 2001, påbörjades en sökning efter en kvantalgoritm för att lösa problemet.

I artikeln granskade Buckley Hopper från University of Alabama Grovers och Shors kvantdatoralgoritmer. Han noterade att Grovers algoritm endast ger en kvadratrotsförbättring, vilket innebär att den inte kan göra ett klassiskt olösligt problem lösbart på en kvantdator. När det gäller Shors algoritm observerade Hopper att, även om den kan omvandla ett förmodat olösligt primtalsfaktorproblem till ett lösbart på den kvanta maskinen, är den bara lämplig för en mycket specifik typ av problem. 

Sammanfattningsvis “hittade Hopper inget tillfredsställande resultat för en algoritm som beräknar approximativa lösningar på traveling salesman‑problemet.”

Några år senare presenterade Institute of Electrical and Electronics Engineers (IEEE) en ny algoritm för att lösa problemet, inspirerad av både genetiska algoritmer och kvantberäkning. IEEE fann att resultaten från tillämpningen av den föreslagna algoritmen på vissa instanser av Traveling Salesman Problem var avsevärt bättre än de som levererades av standardgenetiska algoritmer.

Klicka här för att lära dig om den nuvarande statusen för kvantberäkning.

Företag som arbetar med kvantberäkning 

Låt oss nu titta på ett par namn som arbetar med forskning och utveckling av kvantberäkning:

#1. IBM

International Business Machines Corporation (IBM ) är verksam inom ett brett spektrum av sektorer, inklusive AI, molntjänster, IT, klientfinansiering och kommersiell finansiering. Teknikjätten är också involverad i kvantberäkning via sin IBM Quantum Platform, som ger offentlig och premiumåtkomst till dess molnbaserade kvantberäkningstjänster. Dessa inkluderar ett set av IBMs prototypkvantprocessorer, handledningar om kvantberäkning och en interaktiv lärobok.

Senast har IBM-forskare uppgett att de är ett steg närmare att övervinna ett hinder som låser upp den spelväxlande potentialen hos kvantdatorer. För detta introducerade de en ny kvantfelkorrigeringskod, som de säger är ungefär tio gånger mer effektiv än tidigare metoder. 

Sent sent år lanserade företaget också kvantdatorn kallad Condor, med 1 121 supraledande qubitar arrangerade i ett honungskakemönster. IBM presenterade också IBM Quantum System Two, deras första modulära kvantdator och kvantcentrerade superdatorarkitektur, som är skalbar och därför kan uppgraderas med chip som kommer att lanseras de kommande fem åren.

Med ett börsvärde på 175 miljarder dollar handlas IBMs aktier till 190,86 dollar, upp 16,66 % år‑till‑datum (YTD). IBM har rapporterat intäkter (TTM) på 61,86 miljarder dollar samt ett EPS (TTM) på 8,03, P/E (TTM) på 23,76 och ROE (TTM) på 33,36 %. Företaget betalar en utdelningsavkastning på 3,48 %.

#2. D-Wave Systems

Detta kvantberäkningsföretag utvecklar och levererar relaterade system, mjukvara och tjänster. Dess produkter inkluderar The Leap och The Advantage, och det tillhandahåller kvantapplikationer för schemaläggning, logistik, läkemedelsupptäckt, tillverkningsprocesser och mer.

Tidigare i månaden sade D-Wave att kvantmaskiner nu kan lösa problem med verkliga tillämpningar snabbare än någon vanlig dator. Tidigare i år annonserade företaget en kvantdator med 1 200 qubitar, 10 000 kopplare och en 20‑ gånger snabbare tid‑till‑lösning på svåra optimeringsproblem.

Företagets aktier handlas för närvarande till 1,86 dollar, upp 138,6 % år‑till‑datum (YTD), med ett börsvärde på 267 miljoner dollar. Det rapporterade 8,247 miljoner dollar i försäljning (TTM), -0,66 EPS (TTM) och -3,19 P/E (TTM), och meddelade över 20 % tillväxt i försäljning för både Q4 och årsslutet 2023, medan bokningarna ökade med 34 % respektive 89 %.

Intressant nog har företagets VD, Dr. Alan Baratz, deklarerat företagets momentum, med hänvisning till företagets fleråriga strategiska partnerskap med Zapata AI, introduktionen av 1 200+ qubit Advantage2‑prototypen, joint ventures med NEC Australia och Deloitte Canada, samt utnämningen av den tidigare Homeland Security‑secretary Kirstjen Nielsen till styrelsen.

Slutsats

Marknaden för kvantberäkning förväntas nå 6,5 miljarder dollar år 2028, och dess potential att lösa Traveling Salesman Problem (TSP) har konsekvenser för flera industrier, såsom tillverkning, logistik, leveranskedjehantering, e‑handel, transport och forskning. Efter allt kan det leda till betydande fördelar, särskilt ökad produktivitet, minskade kostnader och främjande av innovation över olika sektorer. 

Klicka här för listan över de fem bästa kvantberäkningsföretagen.