Wetenschap
Kwantumcomputers kunnen combinatorische optimalisatieproblemen gemakkelijker oplossen dan conventionele methoden, blijkt uit onderzoek
Het handelsreizigersprobleem wordt beschouwd als een goed voorbeeld van een combinatorisch optimalisatieprobleem. Nu heeft een Berlijns team onder leiding van theoretisch natuurkundige prof. dr. Jens Eisert van de Freie Universität Berlin en HZB aangetoond dat een bepaalde klasse van dergelijke problemen daadwerkelijk beter en veel sneller kan worden opgelost met kwantumcomputers dan met conventionele methoden.
Het werk van het team is gepubliceerd in het tijdschrift Science Advances .
Kwantumcomputers gebruiken zogenaamde qubits, die niet nul of één zijn zoals in conventionele logische circuits, maar elke waarde daartussenin kunnen aannemen. Deze qubits worden gerealiseerd door sterk gekoelde atomen, ionen of supergeleidende circuits, en het is fysiek nog steeds erg complex om een quantumcomputer met veel qubits te bouwen. Wiskundige methoden kunnen echter nu al worden gebruikt om te onderzoeken wat fouttolerante kwantumcomputers in de toekomst kunnen bereiken.
‘Er bestaan veel mythes over, en soms is er sprake van een zekere mate van gebakken lucht en hype. Maar we hebben de kwestie rigoureus benaderd, met behulp van wiskundige methoden, en hebben solide resultaten over dit onderwerp opgeleverd. Bovenal hebben we duidelijk gemaakt in welke zin er kunnen überhaupt voordelen zijn”, zegt prof. dr. Eisert, hoofd van een gezamenlijke onderzoeksgroep aan de Freie Universität Berlin en Helmholtz-Zentrum Berlin.
Het bekende probleem van de handelsreiziger dient als goed voorbeeld:een reiziger moet een aantal steden bezoeken en vervolgens terugkeren naar zijn geboortestad. Wat is de kortste route? Hoewel dit probleem gemakkelijk te begrijpen is, wordt het steeds complexer naarmate het aantal steden toeneemt en de rekentijd explosief toeneemt. Het handelsreizigersprobleem staat voor een groep optimalisatieproblemen die van enorm economisch belang zijn, of het nu gaat om spoorwegnetwerken, logistiek of optimalisatie van hulpbronnen. Oplossingen die goed genoeg zijn, kunnen worden gevonden met behulp van benaderingsmethoden.
Het team onder leiding van Eisert en zijn collega Jean-Pierre Seifert heeft nu puur analytische methoden gebruikt om te evalueren hoe een kwantumcomputer met qubits deze klasse van problemen zou kunnen oplossen, een klassiek gedachte-experiment met pen en papier en veel expertise.
"We gaan er eenvoudigweg van uit, ongeacht de fysieke realisatie, dat er voldoende qubits zijn en kijken naar de mogelijkheden om er computerbewerkingen mee uit te voeren", legt Vincent Ulitzsch, een Ph.D. student aan de Technische Universiteit van Berlijn.
Daarbij onthulde het team overeenkomsten met een bekend probleem in de cryptografie, namelijk de versleuteling van gegevens.
"We realiseerden ons dat we het Shor-algoritme konden gebruiken om een subklasse van deze optimalisatieproblemen op te lossen", zegt Ulitzsch. Dit betekent dat de rekentijd niet langer "explodeert" met het aantal steden (exponentieel, 2 N ), maar neemt alleen polynomiaal toe, d.w.z. met N x , waarbij x een constante is. De op deze manier verkregen oplossing is ook kwalitatief veel beter dan de geschatte oplossing met behulp van het conventionele algoritme.
"We hebben aangetoond dat kwantumcomputers voor een specifieke maar zeer belangrijke en praktisch relevante klasse van combinatorische optimalisatieproblemen een fundamenteel voordeel hebben ten opzichte van klassieke computers voor bepaalde gevallen van het probleem", zegt Eisert.