Lösning av ‘The Travelling Salesman Problem’ genom kvantberäkning

Ett klassiskt algoritmiskt problem inom datavetenskap som kallas för Resande försäljare-problemet (TSP) är ett utmärkt exempel på ett kombinatoriskt optimeringsproblem.

Vad är 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å de möjliga rutternas antal och beräkningstiden för att hitta den optimala lösningen.Även om detta problem kan lösas med approximeringsmetoder, kan kvantdatorer ge mycket bättre lösningar och dessutom snabbare.

Detta är exakt vad den teoretiska fysikern 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 utanför räckhåll för konventionella datorer, inklusive superdatorer. Trots deras kraft är superdatorer – stora klassiska datorer med tusentals CPU- och GPU-kärnor – begränsade av sin tillit till 1900-talets transistor-teknik när det gäller att lösa problem med hög komplexitet.

Här kommer kvantfysiken in. Till skillnad från klassiska datorer, som kodar information i binära bitar (0 och 1), använder kvantdatorer kvantbitar eller qubit 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 behålla sina kvanttillstånd. Detta uppnås genom superkylda superfluida ämnen.

Supralegeringar är material som uppvisar en kritisk kvantmekanisk effekt, som tillåter elektroner att röra sig genom dem utan motstånd. När elektroner passerar genom, parar de ihop för att bära en laddning över barriärer. När två supralegeringar placeras på varsin sida om en isolator, skapas en Josephson-koppling, som används för att utföra superledande qubit.

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 qubit i superposition kan skapa komplexa, multidimensionella beräkningsutrymmen där komplexa problem kan representeras.

Här, genom sammanflätning av två qubit, kan förändringar i en påverka den andra direkt, medan när dessa sammanflätade qubit placeras i ett tillstånd av superposition, får vi många sannolikheter. Beräkning på en kvantdator fungerar genom att förbereda en superposition av alla möjliga beräkningslägen, och genom interferens hittas lösningar.

Naturligtvis är det att bygga en kvantdator med många qubit en mycket komplex procedur, ä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 forskningsuniversitetet Freie Universität Berlin:

“Det finns många myter om det, och ibland en viss mängd varm luft och hype. Men vi har angripit frågan rigoröst, med hjälp av matematiska metoder, och levererat solida resultat på ämnet. Framför allt har vi klargjort i vilken mening det kan finnas några fördelar alls.”

Det kritiska Resande försäljare-problemet

Ett optimeringsproblem, TSP är av stor ekonomisk betydelse inom logistik- och leverantörsindustrin. Det faller inom den bredare kategorin kombinatoriska optimeringsproblem, som också inkluderar jobbschemaläggning, resursallokering, portföljoptimering och till och med proteinveckning, alla kritiska för olika sektorer.

Med tanke på de sociala och ekonomiska konsekvenserna av dessa problem, har de varit föremål för intensiv forskning. Som sådan, att hitta svaret på problem som den mest effektiva leverantörskedjan och den billigaste leveransrouten har en positiv inverkan på våra dagliga liv.

Men att optimera leveransrutten för flera destinationer samtidigt som man tar hänsyn till olika begränsningar, såsom trafikstockningar, stigande driftskostnader, plötsliga ruteändringar, sista minuten-affärsmöten och kundförfrågningar, gör TSP ännu svårare att lösa. Trots dessa utmaningar är det att lösa 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 att minska avståndet och antalet timmar som färdas och spara bränsleförbrukning. Att minimera avståndet som färdas kan hjälpa till att minska koldioxidavtrycket betydligt, vilket översätts till bättre luwkvalitet, bromsande klimatförändringar och ekonomisk tillväxt. Dessutom kan lösning 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älttjänsterna.

Som vi har sett, att lösa problemet hjälper inte bara företag, utan dessa fördelar sipprar ner till kunderna också, 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änsmetoden bryts problemet ner i flera serier av underproblem, där varje skede lösning påverkar lösningen som hittas i efterföljande skeden.

I dynamisk programmering fokuserar man på att undvika onödiga beräkningar. Närmaste granne är en approximationsalgoritm där du börjar med startplatsen och sedan stannar vid den närmaste. När alla städer är täckta, återvänder du till startplatsen. Medan det är praktiskt och relativt snabbt, kan denna metod inte alltid ge en effektiv rutt.

Allteftersom tekniken utvecklas kan ruteplanering och optimering göras mycket mer effektivt. Artificiell intelligens (AI) kan också hjälpa till att lösa problemet genom att analysera en stor mängd data snabbt för att hjälpa många moderna företag att fatta operativa och strategiska beslut.

Kvantdatorer undersöks också för att lösa problemet; efter allt, de erbjuder betydande beräkningshastigheter jämfört med klassiska datorer.

Användning av kvantberäkningsmetoder för att lösa TSP

Medan kvantberäkning väcker enormt intresse och ger lovande resultat för vissa problem, förblir omfattningen av denna kvantfördel i stort sett outforskad.

Som sådan, gav studien fullständig konstruktiv bevis för att kvantdatorer faktiskt kan överträffa konventionella datorer för att hitta approximeringar 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 qubit kan lösa TSP-problemet.

“Vi antar helt enkelt, oavsett den fysiska realiseringen, att det finns tillräckligt med qubit och tittar 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örklarade Vincent Ulitzsch, en doktorand vid Tekniska universitetet i Berlin.

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

Genom att använda kryptografiska begrepp och beräkningsinlärningsteori ger studien “fullständig konstruktiv bevis för att kvantdatorer har en superpolynomisk fördel över klassiska datorer vid approximering av kombinatoriska optimeringsproblem”.

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

Studien finansierades av Einstein Research Unit, Berlin Mathematics Research Center (MATH+ Cluster of Excellence), BMBF (Hybrid), BMWK (EniQmA), Munich Quantum Valley och DFG. Tysklands federala utbildnings- och forskningsministerium gav också ekonomiskt stöd.

Utforskning av kvantberäkningspotential

Medan detta var en stor prestation, var det inte första gången som kvantberäkning har använts för att lösa Resande försäljare-problemet. Det har funnits många tillfällen då entusiaster och forskare har undersökt att lösa problemet med hjälp av kvantberäkning.

I december 2022, föreslog en artikel en kvantalgoritm för TSP baserad på Grover Adaptive Search (GAS). Under GAS-ramverket finns det minst två grundläggande svårigheter – lösningar kan inte vara genomförbara, och antalet qubit i nuvarande kvantdatorer är mycket begränsat och kan inte uppfylla de minimikrav som krävs, vilket begränsar tillämpningen av kvantalgoritmer för kombinatoriska optimeringsproblem.

Som sådan, polerade artikeln Hamiltonian Cycle Detection (HCD)-oraklet, som kan ta bort icke-godtagbara lösningar automatiskt under algoritmens körning. De utformade också en “ankare-registreringsstrategi” för att spara qubit-användning, med full hänsyn till kravet på omvändbarhet i kvantberäkning och övervann svårigheten att de använda qubiterna inte kunde skrivas över eller släppas.

I november 2019 skrev Joseph Cammidge, en fysikentusiast, om att använda en annealing-kvantprocessor, som tillät honom att lösa Resande försäljare-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 potentialen att lösa optimeringsproblem snabbare än klassiska tekniker. Dess teori implicerar att qubitarna kommer att uppnå ett optimalt lågenergitillstånd när de är superkylda.

Men i januari 2021, fann en studie som finansierades av Supply Chain Digital & Data Science, Johnson & Johnson, att kvantannealern bara kan hantera ett problemstorlek på 8 eller färre noder, och dess prestanda är undermålig både i termer av tid och noggrannhet jämfört med den klassiska solvers.

Användningen av kvantberäkning för att lösa TSP-problemet har pågått under en längre tid. För över två decennier sedan, 2001, började en studie att söka efter en kvantalgoritm för att lösa problemet.

I artikeln undersökte Buckley Hopper från University of Alabama Grovers och Shors kvantberäkningsalgoritmer. Han noterade att Grovers algoritm endast ger en kvadratisk förbättring, vilket innebär att den inte kan göra ett klassiskt olösligt problem lösbart på en kvantdator. Vad gäller Shors algoritm observerade Hopper att den, medan den kan omvandla ett förmodat olösligt primfaktorproblem till ett lösbart problem på en kvantdator, endast är lämplig för ett mycket specifikt problem.

Sammanfattningsvis fann Hopper “inte ett tillfredsställande resultat för en algoritm för att beräkna approximativa lösningar till Resande försäljare-problemet”.

Ett par å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 Resande försäljare-problemet är betydligt bättre än de som tillhandahålls av standardgenetiska algoritmer.

Klicka här för att lära dig om den aktuella tillståndet för kvantberäkning.

Företag som arbetar med kvantberäkning

Nu, låt oss ta en titt på några namn som arbetar med forskning och utveckling av kvantberäkning:

#1. IBM

International Business Machines Corporation är engagerad i en mängd olika sektorer, inklusive AI, molntjänster, IT, kundfinansiering och kommersiell finansiering. Teknikjätten är också involverad i kvantberäkning via sin IBM Quantum Platform, som ger allmän och premiumåtkomst till sina molnbaserade kvantberäkningstjänster. Dessa inkluderar en uppsättning av IBMs prototyp-kvantprocessorer, handledningar om kvantberäkning och en interaktiv lärobok.

Alldeles nyligen meddelade IBM-forskare att de är ett steg närmare att övervinna ett hinder som låser upp den spektakulära potentialen för kvantdatorer. För detta introducerade de en ny kvantfelkorrekturkod, som de påstår är cirka tio gånger mer effektiv än tidigare metoder.

Sent förra året lanserade företaget också kvantdatorn Condor, med 1 121 superledande qubit som är arrangerade i ett hexagonmönster. IBM lanserade också IBM Quantum System Two, sin första modulära kvantdator och kvantcentrerad superdatorarkitektur, som är skalbar och kan uppgraderas med chip som kommer att lanseras under de närmaste fem åren.

Med en marknadsvärdering på 175 miljarder dollar, handlas IBMs aktier för 190,86 dollar, upp 16,66% sedan årsskiftet. IBM har rapporterat intäkter (TTM) på 61,86 miljarder dollar, medan EPS (TTM) är 8,03, P/E (TTM) är 23,76 och ROE (TTM) är 33,36%. Företaget betalar en utdelning på 3,48%.

#2. D-Wave Systems

Detta kvantberäkningsföretag utvecklar och levererar relaterad utrustning, programvara och tjänster. Deras produkter inkluderar The Leap och The Advantage, och de erbjuder kvantprogram för schemaläggning, logistik, läkemedelsupptäckt, tillverkningsprocesser och mer.

I början av denna månad sa D-Wave att kvantmaskiner nu kan lösa problem med verkliga tillämpningar snabbare än någon vanlig dator. Tidigare i år tillkännagav företaget en kvantdator med 1 200 qubit, 10 000 kopplingar och en 20 gånger snabbare lösningstid för svåra optimeringsproblem.

Företagets aktier handlas för närvarande för 1,86 dollar, upp 138,6% sedan årsskiftet, med en marknadsvärdering på 267 miljoner dollar. De rapporterade 8,247 miljoner dollar i försäljning (TTM), -0,66 EPS (TTM) och -3,19 P/E (TTM), och tillkännagav en tillväxt på över 20% i försäljning för både det fjärde kvartalet och helåret 2023, medan beställningar ökade med 34% respektive 89%.

Intressant nog förklarade företagets VD, Dr. Alan Baratz, företagets momentum, med hänvisning till företagets fleråriga strategiska partnerskap med Zapata AI, introduktionen av 1 200+ qubit Advantage2-prototypen, samarbeten med NEC Australia och Deloitte Canada, och utnämningen av den tidigare hemlands säkerhetsministern 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 Resande försäljare-problemet har konsekvenser för flera branscher, såsom tillverkning, logistik, leverantörskedjeledning, e-handel, transport och forskning. Efter allt, det kan resultera i betydande fördelar, särskilt ökad produktivitet, minskade utgifter och stimulerad innovation över olika sektorer.

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