I 1994 fandt en matematiker ud af, hvordan man får en kvantecomputer til at gøre noget, som ingen almindelig klassisk computer kunne. Arbejdet afslørede, at i princippet kunne en maskine baseret på kvantemekanikkens regler effektivt opdele et stort antal i sine primære faktorer - en opgave så vanskelig for en klassisk computer, at den danner grundlaget for meget af nutidens internetsikkerhed.
En bølge af optimisme fulgte. Måske, tænkte forskere, vil vi være i stand til at opfinde kvantealgoritmer, der kan løse en lang række forskellige problemer.
Men fremskridtet gik i stå. "Det har været lidt af en elendig bane," sagde Ryan O'Donnell fra Carnegie Mellon University. "Folk tænkte:" Det er fantastisk, jeg er sikker på, at vi får alle mulige andre fantastiske algoritmer. Nix." Forskere opdagede dramatiske speedups kun for en enkelt, snæver klasse af problemer fra et standardsæt kaldet NP, hvilket betyder, at de havde effektivt verificerbare løsninger - såsom factoring.
Sådan var det i næsten tre årtier. Så i april, forskere opfundet en fundamentalt ny slags problem, som en kvantecomputer burde kunne løse eksponentielt hurtigere end en klassisk. Det indebærer beregning af input til en kompliceret matematisk proces, udelukkende baseret på dens blandede output. Om problemet står alene eller er det første i en ny grænse af mange andre, er endnu ikke afgjort.
"Der er en følelse af spænding," sagde Vinod Vaikuntanathan, en datalog ved Massachusetts Institute of Technology. "Mange mennesker tænker på, hvad der ellers er derude."
Dataloger forsøger at forstå, hvad kvantecomputere gør bedre ved at studere matematiske modeller, der repræsenterer dem. Ofte forestiller de sig en model af en kvante- eller klassisk computer parret med en idealiseret regnemaskine kaldet et orakel. Orakler er som simple matematiske funktioner eller computerprogrammer, der tager et input og spytter et forudbestemt output ud. De kan have en tilfældig adfærd, der udsender "ja", hvis input falder inden for et bestemt tilfældigt område (f.eks. 12 til 67) og "nej", hvis det ikke gør det. Eller de kan være periodiske, så et input mellem 1 til 10 returnerer "ja", 11 til 20 giver "nej", 21 til 30 giver "ja" igen, og så videre.
Lad os sige, at du har et af disse periodiske orakler, og at du ikke kender perioden. Alt du kan gøre er at give den tal og se, hvad den udsender. Med disse begrænsninger, hvor hurtigt kunne en computer finde perioden? I 1993 fandt Daniel Simon, dengang ved University of Montreal, ud af, at en kvantealgoritme kunne beregne svaret på et nært beslægtet problem eksponentielt hurtigere end nogen klassisk algoritme.
Resultatet gjorde det muligt for Simon at bestemme en af de første antydninger af, hvor dramatisk overlegenhed for kvantecomputere kunne forventes. Men da han sendte sit papir til en ledende konference, blev det afvist. Avisen interesserede dog et yngre medlem af konferencens programkomité - Peter Shor, som på det tidspunkt var på Bell Laboratories i New Jersey. Shor fortsatte med at finde ud af, at han kunne tilpasse Simons algoritme til at beregne perioden for et orakel, hvis det havde et. Så indså han, at han kunne tilpasse algoritmen igen for at løse en ligning, der opfører sig på samme måde som et periodisk orakel: ligningen, der beskriver factoring, som er periodisk.
Shors resultat var historisk. Den kvantealgoritme, han opdagede, kunne hurtigt reducere gigantiske tal til deres konstituerende primfaktorer, noget som ingen kendt klassisk algoritme kan gøre. I årene efter opdagede forskere andre effektive kvantealgoritmer. Nogle af dem, som Shor's algoritme, gav endda eksponentiel fordel, men ingen kunne bevise en dramatisk kvantefordel på noget NP-problem, der ikke var periodisk.
Denne mangel på fremskridt førte til, at to dataloger, Scott Aaronson fra University of Texas, Austin og Andris Ambainis fra universitetet i Letland, for at foretage en observation. Beviser for kvantefordele syntes altid at være afhængige af orakler, der havde en form for ikke-tilfældig struktur, såsom periodicitet. I 2009 har de formodede at der ikke kunne være dramatiske speedups på NP-problemer, der var tilfældige eller ustrukturerede. Ingen kunne finde en undtagelse.
Deres formodning satte en grænse for kvantecomputeres kræfter. Men den sagde kun, at der ikke var nogen dramatiske speedups for en specifik type ustruktureret NP-problem - dem med ja eller nej svar. Hvis et problem involverede at finde ud af mere specifikke, kvantitative svar, som er kendt som et søgeproblem, gjaldt formodningen ikke.
Med det i tankerne, forskere Takashi Yamakawa af NTT Social Informatics Laboratories og Mark Zhandry fra NTT Research og Princeton University besluttede at eksperimentere med et specifikt søgeproblem, introduceret i 2005 af Oded Regev.
Forestil dig et sæt vejrvinger, der alle peger i samme retning. Giv hver af dem et afmålt skub, og lad derefter en vindstød påvirke deres retning. Regev ønskede ud fra deres endelige anvisninger at bestemme, hvor de alle pegede indledningsvis. Problemer som dette kom til at blive kaldt "at lære med fejl", fordi skubningen og vinden fungerer som en kilde til tilfældig fejl i den oprindelige retning. Der er tegn på, at det er svært at løse for både klassiske og kvantealgoritmer.
Yamakawa og Zhandry justerede opsætningen. De ændrede styrken af disse startskud, hvilket gjorde dem mere forudsigelige. De fik også vinden til at blive bestemt af et tilfældigt orakel, så den var endnu mere tilfældig i visse tilfælde, men helt i dvale i andre.
Med disse modifikationer opdagede forskerne, at en kvantealgoritme effektivt kunne finde den indledende retning. De beviste også, at enhver klassisk algoritme skal være langsommere med en eksponentiel faktor. Ligesom Shor tilpassede de derefter deres algoritme for at løse en virkelighedsversion af problemet, som erstatter oraklet med en egentlig matematisk ligning.
Dataloger arbejder stadig på at forstå og bygge videre på problemet. Vaikuntanathan sammenligner det med en anden, der opstår, når man laver datakomprimering: Når information bliver presset ned, kan to bits ved et uheld blive presset ind på det samme sted og overskrive dem. Problemet med at forudsige disse kollisioner på forhånd, så du kan undgå dem, har en vis lighed. "Det er en klasse af problemer, som grundlæggende ser sådan ud," sagde han. "Måske kan disse problemer løses kvantum."
Der var håb om, at et ustruktureret problem som det nye kunne løses selv på nutidens spæde versioner af kvantecomputere, og derved give et middel til at teste dem. Tanken var, at ustrukturerede problemer kunne tage færre ressourcer at programmere eller være mindre følsomme over for støj, da de allerede er tilfældige. Men indtil videre virker det nye problem stadig for avanceret til, at eksisterende kvantecomputere kan løse det. "Det er et mærkeligt problem. Jeg havde ikke tænkt på at definere det,” sagde Aaronson. "Men set i bakspejlet har den nogle meget fine funktioner."
Resultatet giver det første eksempel på dramatisk kvantefordel på et ustruktureret NP-problem. Kan der være mange andre problemer, som kvanteverdenen ændrer sig fra praktisk talt uløselig til løselig? Det er der nu mere grund til at mene.
"Det har lidt omstødt vores overbevisning om, hvilke slags problemer kvantecomputere kunne være gode til," sagde O'Donnell.
