Kvantecomputere kan lettere løse kombinatoriske optimeringsproblemer end konventionelle metoder, viser forskning

Problemet med den rejsende sælger betragtes som et glimrende eksempel på et kombinatorisk optimeringsproblem. Nu har et Berlin-hold ledet af teoretisk fysiker prof. Dr. Jens Eisert fra Freie Universität Berlin og HZB vist, at en bestemt klasse af sådanne problemer faktisk kan løses bedre og meget hurtigere med kvantecomputere end med konventionelle metoder.

Holdets arbejde er publiceret i tidsskriftet Science Advances .

Kvantecomputere bruger såkaldte qubits, som ikke er enten nul eller én som i konventionelle logiske kredsløb, men kan antage en hvilken som helst værdi imellem. Disse qubits realiseres af højt afkølede atomer, ioner eller superledende kredsløb, og det er stadig fysisk meget komplekst at bygge en kvantecomputer med mange qubits. Matematiske metoder kan dog allerede bruges til at udforske, hvad fejltolerante kvantecomputere kan opnå i fremtiden.

"Der er mange myter om det, og nogle gange en vis mængde varm luft og hype. Men vi har grebet sagen stringent an ved hjælp af matematiske metoder og leveret solide resultater om emnet. Frem for alt har vi afklaret i hvilken forstand der kan være nogen fordele overhovedet," siger prof. Dr. Eisert, der leder en fælles forskningsgruppe ved Freie Universität Berlin og Helmholtz-Zentrum Berlin.

Det velkendte problem med den rejsende sælger fungerer som et godt eksempel:En rejsende skal besøge en række byer og derefter vende tilbage til sin hjemby. Hvilken er den korteste vej? Selvom dette problem er let at forstå, bliver det stadig mere komplekst, efterhånden som antallet af byer stiger, og beregningstiden eksploderer. Det rejsende sælgerproblem står for en gruppe af optimeringsproblemer, der er af enorm økonomisk betydning, hvad enten de involverer jernbanenet, logistik eller ressourceoptimering. Gode ​​nok løsninger kan findes ved hjælp af tilnærmelsesmetoder.

Holdet ledet af Eisert og hans kollega Jean-Pierre Seifert har nu brugt rent analytiske metoder til at evaluere, hvordan en kvantecomputer med qubits kunne løse denne klasse af problemer, et klassisk tankeeksperiment med pen og papir og en masse ekspertise.

"Vi antager simpelthen, uanset den fysiske erkendelse, at der er nok qubits og ser på mulighederne for at udføre computeroperationer med dem," forklarer Vincent Ulitzsch, der er ph.d. studerende ved det tekniske universitet i Berlin.

Derved afslørede holdet ligheder med et velkendt problem inden for kryptografi, dvs. kryptering af data.

"Vi indså, at vi kunne bruge Shor-algoritmen til at løse en underklasse af disse optimeringsproblemer," siger Ulitzsch. Det betyder, at regnetiden ikke længere "eksploderer" med antallet af byer (eksponentiel, 2 ^N ), men kun øges polynomielt, dvs. med N ^x , hvor x er en konstant. Løsningen opnået på denne måde er også kvalitativt meget bedre end den omtrentlige løsning ved brug af den konventionelle algoritme.

"Vi har vist, at for en specifik, men meget vigtig og praktisk relevant klasse af kombinatoriske optimeringsproblemer, har kvantecomputere en fundamental fordel i forhold til klassiske computere for visse tilfælde af problemet," siger Eisert.

Flere oplysninger: Niklas Pirnay et al., En principiel superpolynomisk kvantefordel til tilnærmelse af kombinatoriske optimeringsproblemer via computational learning theory, Science Advances (2024). DOI:10.1126/sciadv.adj5170

Leveret af Helmholtz Association of German Research Centres