In 1994 ontdekte een wiskundige hoe hij een kwantumcomputer iets kon laten doen wat geen enkele gewone klassieke computer kon. Uit het werk bleek dat een machine gebaseerd op de regels van de kwantummechanica in principe een groot aantal op efficiënte wijze in zijn belangrijkste factoren kan opsplitsen – een taak die zo moeilijk is voor een klassieke computer dat deze de basis vormt voor een groot deel van de hedendaagse internetbeveiliging.
Een golf van optimisme volgde. Misschien, dachten onderzoekers, kunnen we kwantumalgoritmen uitvinden die een groot aantal verschillende problemen kunnen oplossen.
Maar de vooruitgang stokte. "Het is een beetje een bummer traject geweest," zei Ryan O'Donnell van de Carnegie Mellon-universiteit. "Mensen zeiden: 'Dit is geweldig, ik weet zeker dat we allerlei andere geweldige algoritmen gaan krijgen.' Nee." Wetenschappers ontdekten dramatische versnellingen voor slechts een enkele, beperkte klasse van problemen binnen een standaardset genaamd NP, wat betekent dat ze efficiënt verifieerbare oplossingen hadden, zoals factoring.
Dat was bijna drie decennia het geval. Toen, in april, onderzoekers uitgevonden een fundamenteel nieuw soort probleem dat een kwantumcomputer exponentieel sneller zou moeten kunnen oplossen dan een klassiek probleem. Het omvat het berekenen van de invoer voor een gecompliceerd wiskundig proces, uitsluitend gebaseerd op de door elkaar gegooide uitvoer. Of het probleem op zichzelf staat of het eerste is in een nieuwe grens van vele andere, moet nog worden vastgesteld.
"Er is een gevoel van opwinding", zei Vinod Vaikuntanathan, een computerwetenschapper aan het Massachusetts Institute of Technology. "Veel mensen denken na over wat er nog meer is."
Computerwetenschappers proberen te begrijpen wat kwantumcomputers beter doen door wiskundige modellen te bestuderen die ze vertegenwoordigen. Vaak stellen ze zich een model voor van een kwantumcomputer of een klassieke computer in combinatie met een geïdealiseerde rekenmachine die een orakel wordt genoemd. Orakels zijn als eenvoudige wiskundige functies of computerprogramma's, die een invoer opnemen en een vooraf bepaalde uitvoer uitspugen. Ze kunnen een willekeurig gedrag vertonen, waarbij ze "ja" uitvoeren als de invoer binnen een bepaald willekeurig bereik valt (bijvoorbeeld 12 tot 67) en "nee" als dat niet het geval is. Of ze kunnen periodiek zijn, zodat een invoer tussen 1 en 10 'ja' oplevert, 11 tot 20 'nee' oplevert, 21 tot 30 weer 'ja' oplevert, enzovoort.
Laten we zeggen dat je een van deze periodieke orakels hebt en dat je de periode niet kent. Het enige dat u kunt doen, is het nummers invoeren en zien wat het oplevert. Met die beperkingen, hoe snel zou een computer de periode kunnen vinden? In 1993 ontdekte Daniel Simon, toen aan de Universiteit van Montreal, dat een kwantumalgoritme het antwoord op een nauw verwant probleem exponentieel sneller kon berekenen dan welk klassiek algoritme dan ook.
Het resultaat stelde Simon in staat om een van de eerste aanwijzingen te vinden waar een dramatische superioriteit voor kwantumcomputers kon worden verwacht. Maar toen hij zijn paper voor een toonaangevende conferentie indiende, werd het afgewezen. De krant interesseerde echter wel een junior lid van de programmacommissie van de conferentie - Peter Shor, die destijds bij Bell Laboratories in New Jersey was. Shor ontdekte dat hij Simons algoritme kon aanpassen om de periode van een orakel te berekenen, als die er was. Toen realiseerde hij zich dat hij het algoritme opnieuw kon aanpassen om een vergelijking op te lossen die zich op dezelfde manier gedraagt als een periodiek orakel: de vergelijking die factoring beschrijft, die periodiek is.
Het resultaat van Shor was historisch. Het kwantumalgoritme dat hij ontdekte, kon gigantische getallen snel reduceren tot hun samenstellende priemfactoren, iets dat geen enkel bekend klassiek algoritme kan doen. In de jaren die volgden, ontdekten onderzoekers andere efficiënte kwantumalgoritmen. Sommigen van hen, zoals het algoritme van Shor, leverden zelfs een exponentieel voordeel op, maar niemand kon een dramatisch kwantumvoordeel bewijzen op een NP-probleem dat niet periodiek was.
Dit gebrek aan vooruitgang leidde twee computerwetenschappers, Scott Aaronson van de Universiteit van Texas, Austin, en Andris Ambaines van de Universiteit van Letland, om een opmerking te maken. Bewijzen van kwantumvoordeel leken altijd afhankelijk te zijn van orakels met een niet-willekeurige structuur, zoals periodiciteit. In 2009 hebben ze giste dat er geen dramatische versnellingen konden zijn op NP-problemen die willekeurig of ongestructureerd waren. Niemand kon een uitzondering vinden.
Hun vermoeden zette een grens aan de krachten van kwantumcomputers. Maar het zei alleen dat er geen dramatische versnellingen waren voor een specifiek type ongestructureerd NP-probleem - degenen met ja of nee antwoorden. Als het een probleem was om meer specifieke, kwantitatieve antwoorden te vinden, wat bekend staat als een zoekprobleem, was het vermoeden niet van toepassing.
Met dat in gedachten, onderzoekers Takashi Yamakawa van NTT Sociale Informatica Laboratoria en Mark Zhandry van NTT Research en Princeton University besloten te experimenteren met een specifiek zoekprobleem, geïntroduceerd in 2005 door Oded Regev.
Stel je een set windwijzers voor die allemaal in dezelfde richting wijzen. Geef elk van hen een afgemeten duw en laat een windvlaag hun richting beïnvloeden. Regev wilde op basis van hun definitieve richting bepalen waar ze in eerste instantie allemaal naar wezen. Dergelijke problemen werden 'leren met fouten' genoemd, omdat de duw en de wind fungeren als een bron van willekeurige fouten in de oorspronkelijke richting. Er zijn aanwijzingen dat het moeilijk op te lossen is voor zowel klassieke als kwantumalgoritmen.
Yamakawa en Zhandry hebben de setup aangepast. Ze wijzigden de kracht van die startende shoves, waardoor ze voorspelbaarder werden. Ze zorgden er ook voor dat de wind werd bepaald door een willekeurig orakel, zodat het in bepaalde gevallen nog meer willekeurig was, maar in andere volledig inactief.
Met deze aanpassingen ontdekten de onderzoekers dat een kwantumalgoritme de initiële richting efficiënt kon vinden. Ze bewezen ook dat elk klassiek algoritme een exponentiële factor langzamer moet zijn. Net als Shor pasten ze vervolgens hun algoritme aan om een echte versie van het probleem op te lossen, dat het orakel vervangt door een echte wiskundige vergelijking.
Computerwetenschappers werken nog steeds om het probleem te begrijpen en erop voort te bouwen. Vaikuntanathan vergelijkt het met een andere die ontstaat bij het comprimeren van gegevens: wanneer informatie wordt samengeperst, kunnen twee bits per ongeluk op dezelfde plaats worden geperst, waardoor ze worden overschreven. Het probleem om die botsingen van tevoren te voorspellen, zodat je ze kunt vermijden, vertoont enige gelijkenis. "Dat is een klasse van problemen die er in wezen zo uitzien," zei hij. "Misschien kunnen deze problemen kwantum worden opgelost."
Men hoopte dat een ongestructureerd probleem zoals het nieuwe zelfs op de huidige prille versies van kwantumcomputers oplosbaar zou zijn, waardoor het een middel zou zijn om ze te testen. De gedachte was dat ongestructureerde problemen minder middelen zouden vergen om te programmeren, of minder gevoelig zouden zijn voor ruis, omdat ze al willekeurig zijn. Maar tot nu toe lijkt het nieuwe probleem nog te geavanceerd voor bestaande kwantumcomputers om op te lossen. “Het is een raar probleem. Ik had er niet aan gedacht om het te definiëren, "zei Aaronson. "Maar achteraf gezien heeft het een aantal zeer mooie eigenschappen."
Het resultaat is het eerste voorbeeld van een dramatisch kwantumvoordeel op een ongestructureerd NP-probleem. Zouden er nog veel meer problemen kunnen zijn die de kwantumwereld verandert van praktisch onoplosbaar in oplosbaar? Er is nu meer reden om dat te denken.
"Het heeft onze overtuigingen over wat voor soort problemen kwantumcomputers goed zouden kunnen doen, enigszins omvergeworpen", zei O'Donnell.
