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.”
