Problemet med resande säljare anses vara ett utmärkt exempel på ett kombinatoriskt optimeringsproblem. Nu har ett Berlin-team under ledning av teoretisk fysiker Prof. Dr. Jens Eisert vid Freie Universität Berlin och HZB visat att en viss klass av sådana problem faktiskt kan lösas bättre och mycket snabbare med kvantdatorer än med konventionella metoder.

Teamets arbete publiceras i tidskriften Science Advances .

Kvantdatorer använder så kallade qubits, som inte är vare sig noll eller ett som i konventionella logiska kretsar, utan kan anta vilket värde som helst däremellan. Dessa qubits realiseras av starkt kylda atomer, joner eller supraledande kretsar, och det är fortfarande fysiskt mycket komplicerat att bygga en kvantdator med många qubits. Men matematiska metoder kan redan användas för att utforska vad feltoleranta kvantdatorer kan åstadkomma i framtiden.

"Det finns många myter om det, och ibland en viss mängd hetluft och hype. Men vi har närmat oss frågan rigoröst, 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 överhuvudtaget, säger prof. Dr. Eisert, som leder en gemensam forskargrupp vid Freie Universität Berlin och Helmholtz-Zentrum Berlin.

Det välkända problemet med den resande säljaren fungerar som ett utmärkt exempel:En resenär måste besöka ett antal städer och sedan återvända till sin hemstad. Vilken är den kortaste vägen? Även om detta problem är lätt att förstå, blir det allt mer komplext när antalet städer ökar och beräkningstiden exploderar. Det resande säljarproblemet står för en grupp optimeringsproblem som är av enorm ekonomisk betydelse, oavsett om de handlar om järnvägsnät, logistik eller resursoptimering. Tillräckligt bra lösningar kan hittas med hjälp av approximationsmetoder.

Teamet som leds av Eisert och hans kollega Jean-Pierre Seifert har nu använt rent analytiska metoder för att utvärdera hur en kvantdator med qubits skulle kunna lösa denna klass av problem, ett klassiskt tankeexperiment med penna och papper och mycket expertis.

"Vi antar helt enkelt, oavsett den fysiska insikten, att det finns tillräckligt med qubits och tittar på möjligheterna att utföra datoroperationer med dem", förklarar Vincent Ulitzsch, en Ph.D. student vid tekniska universitetet i Berlin.

Därmed avslöjade teamet likheter med ett välkänt problem inom kryptografi, det vill säga kryptering av data.

"Vi insåg att vi kunde använda Shor-algoritmen för att lösa en underklass av dessa optimeringsproblem", säger Ulitzsch. Detta innebär att beräkningstiden inte längre "exploderar" med antalet städer (exponentiell, 2 ^N ), men ökar bara polynomiellt, dvs med N ^x , där x är en konstant. Lösningen som erhålls på detta sätt är också kvalitativt mycket bättre än den ungefärliga lösningen med den konventionella algoritmen.

"Vi har visat att för en specifik men mycket viktig och praktiskt relevant klass av kombinatoriska optimeringsproblem, har kvantdatorer en fundamental fördel jämfört med klassiska datorer för vissa fall av problemet", säger Eisert.

Mer information: Niklas Pirnay et al, En principiell superpolynomisk kvantfördel för att approximera kombinatoriska optimeringsproblem via beräkningslärandeteori, Science Advances (2024). DOI:10.1126/sciadv.adj5170

Tillhandahålls av Helmholtz Association of German Research Centers