Sterke en zwakke punten van quantumalgoritmen

Hoewel het bouwen van een grote praktische quantumcomputer nog steeds een langetermijnproject is, hebben onderzoekers de afgelopen twee decennia grote vooruitgang geboekt bij het bouwen van rudimentaire quantumhardware en bij het ontwikkelen van quantumalgoritmen, de rekenrecepten die op quantumhardware kunnen draaien. Deze vooruitgang heeft bij verschillende industrieën veel belangstelling gewekt om te onderzoeken of quantumcomputers hun rekenproblemen veel sneller kunnen oplossen. De grote vraag is welke problemen sneller opgelost kunnen worden en wanneer dit werkelijkheid gaat worden.

Onderzoeken welke problemen op een quantumcomputer kunnen worden opgelost en bepalen wanneer een quantumcomputer beter zal presteren dan een klassieke computer, is een onderzoeksgebied waarin het CWI uitblinkt. De afgelopen jaren hebben CWI-onderzoekers de grenzen bepaald van wat quantumcomputers wel en niet kunnen oplossen. Ronald de Wolf, senior onderzoeker bij het CWI: “De complexiteit van het oplossen van een probleem op een quantumcomputer heeft een boven- en een ondergrens. Het vinden van een quantumalgoritme geeft je een bovengrens: je kunt laten zien dat je een bepaald probleem met een bepaalde efficiëntie op een quantumcomputer kunt oplossen. Bij het CWI hebben we een aantal nieuwe quantumalgoritmen ontwikkeld voor sommige optimalisatieproblemen en andere taken, met behulp van tools als quantumamplitudeversterking en quantum random walks.”

Grote rekenproblemen

Harry Buhrman, voormalig groepsleider van de Algorithms & Complexity groep bij het CWI en oud-directeur van QuSoft, heeft een fundamentele ondergrens van quantumalgoritmen ontdekt: zelfs een quantumcomputer kan een bepaald probleem niet sneller oplossen dan deze ondergrens. Buhrman: “Uitgaande van een quantumversie van de zogenaamde exponentiële-tijdhypothese, die zegt dat zoeken met brute kracht het beste is wat je kunt doen voor bepaalde constraint-satisfaction-problemen, hebben we aangetoond dat quantumcomputers voor veel problemen op zijn best een kwadratische oplossing bieden, en vaak zelfs minder, snelheidsverbetering geven in de tijd die nodig is om ze op te lossen. Voor veel rekenproblemen verklaart deze quantum fine-grained complexity (quantum fijnkorrelige complexiteit) waarom een quantumcomputer je niet meer dan kwadratische versnelling oplevert.”

De Wolf: “Een praktische quantumcomputer heeft veel foutcorrectie nodig, wat de rekensnelheid in feite flink vertraagt: één basis quantumoperatie is een stuk langzamer en duurder dan één basisoperatie op een klassieke computer. Omdat een quantumcomputer voor veel problemen hooguit een kwadratische versnelling geeft, kun je berekenen dat je pas voor heel grote rekenproblemen op het crossoverpunt komt waarboven de quantumcomputer de best mogelijke klassieke computer verslaat.”

In zekere zin is dit nieuwe resultaat slecht nieuws voor bedrijven en academische onderzoekers die hoopten deze problemen snel op een quantumcomputer te kunnen oplossen, want een voldoende grote quantumcomputer zal er de komende twintig tot dertig jaar waarschijnlijk niet komen. "Maar het is onze missie om de waarheid te vinden, hoe hard die ook aankomt", zegt De Wolf.

Leidende rol

Het onderzoeken van de sterke en zwakke punten van quantumalgoritmen past perfect in CWI’s lange geschiedenis op het gebied van quantum computing. Al sinds het ontstaan van het vakgebied halverwege de jaren negentig hebben CWI-onderzoekers een leidende rol gespeeld. In 2015 richtten het CWI en de Universiteit van Amsterdam (UvA) gezamenlijk ’s werelds eerste onderzoekscentrum voor quantumsoftware op, genaamd QuSoft. “Hier combineren we onderzoek op het gebied van de wiskunde, informatica en natuurkunde om de basis te leggen voor de quantuminformatica”, zegt Buhrman. “QuSoft telt momenteel zo’n zeventig junior en senior onderzoekers, waarvan er zo’n twintig in dienst zijn bij het CWI, maar veel van de anderen hebben ook een kantoor op het CWI.”

Voor de nabije toekomst hebben De Wolf en Buhrman een paar ideeën om de grenzen van quantum computing verder te verkennen. Eén idee is om te zoeken naar bruikbare toepassingen van quantumcomputers met een paar honderd qubits, die voor bepaalde scheikundige problemen misschien al beter kunnen presteren dan klassieke computers. “We denken dat we daar misschien een grote quantumversnelling kunnen bereiken, maar dat weten we nog niet zeker”, zegt Buhrman. “Als dat zo is, zou dat binnen tien tot vijftien jaar tot zeer nuttige toepassingen kunnen leiden."

Een ander idee is om quantumalgoritmen te ontwikkelen die voor bepaalde optimalisatieproblemen een meer dan kwadratische versnelling geven. De Wolf: “Ik zou ook graag willen proberen cryptografische systemen te breken die gebaseerd zijn op recent gekozen nieuwe post-quantumcryptografiestandaarden, vergelijkbaar met hoe het quantumalgoritme van Shor gevestigde cryptografie zoals RSA breekt.”

Buhrman wil graag verder kijken dan de worst-case-analyse die hem ertoe bracht een ondergrens voor de prestaties van quantumalgoritmen te ontdekken: “Het zou kunnen zijn dat er specifieke problemen zijn waarvoor quantumalgoritmen het beter kunnen doen dan in de algemene worst-case-analyse dat wij hebben gedaan. Een voorbeeld hiervan kunnen diepe neurale netwerken zijn (zogenaamde 'deep learning'). Het is bekend dat deze netwerken niet altijd efficiënt getraind kunnen worden: de 'worst case' gevallen van dit leer-probleem zijn moeilijk. Maar de typische gevallen die we in de praktijk tegenkomen zijn meestal wel goed te trainen: de 'average case' instanties zijn relatief makkelijk. Ik zou graag willen onderzoeken of we meer problemen kunnen vinden waarvoor een quantumheuristiek tot meer leidt dan een kwadratische versnelling.”

Auteur: Bennie Mols. Vertaling: CWI.