I 1994 fant en matematiker ut hvordan han kunne få en kvantedatamaskin til å gjøre noe som ingen vanlig klassisk datamaskin kunne. Arbeidet avslørte at i prinsippet kunne en maskin basert på kvantemekanikkens regler effektivt bryte et stort antall inn i sine hovedfaktorer - en oppgave så vanskelig for en klassisk datamaskin at den danner grunnlaget for mye av dagens internettsikkerhet.
En bølge av optimisme fulgte. Kanskje, tenkte forskere, vil vi være i stand til å finne opp kvantealgoritmer som kan løse et stort spekter av forskjellige problemer.
Men fremgangen stoppet opp. "Det har vært litt av en kjip bane," sa Ryan O'Donnell ved Carnegie Mellon University. «Folk sa: «Dette er fantastisk, jeg er sikker på at vi kommer til å få alle slags andre fantastiske algoritmer.» Nei.» Forskere oppdaget dramatiske hastighetsøkninger bare for en enkelt, smal klasse av problemer fra et standardsett kalt NP, noe som betyr at de hadde effektivt verifiserbare løsninger - for eksempel factoring.
Slik var det i nesten tre tiår. Så i april, forskere oppfunnet en fundamentalt ny type problem som en kvantedatamaskin skal kunne løse eksponentielt raskere enn en klassisk. Det innebærer å beregne inngangene til en komplisert matematisk prosess, utelukkende basert på dens rotete utdata. Hvorvidt problemet står alene eller er det første i en ny grense av mange andre, er ennå ikke bestemt.
"Det er en følelse av spenning," sa Vinod Vaikuntanathan, en informatiker ved Massachusetts Institute of Technology. "Mange mennesker tenker på hva annet som er der ute."
Dataforskere prøver å forstå hva kvantedatamaskiner gjør bedre ved å studere matematiske modeller som representerer dem. Ofte forestiller de seg en modell av en kvante- eller klassisk datamaskin paret med en idealisert regnemaskin kalt et orakel. Orakler er som enkle matematiske funksjoner eller dataprogrammer, som tar inn en inngang og spytter ut en forhåndsbestemt utgang. De kan ha en tilfeldig oppførsel, og sende ut "ja" hvis inngangen faller innenfor et visst tilfeldig område (si 12 til 67) og "nei" hvis det ikke gjør det. Eller de kan være periodiske, slik at en inngang mellom 1 til 10 returnerer "ja", 11 til 20 gir "nei", 21 til 30 gir "ja" igjen, og så videre.
La oss si at du har et av disse periodiske oraklene og at du ikke kjenner perioden. Alt du kan gjøre er å mate den med tall og se hva den gir. Med disse begrensningene, hvor raskt kunne en datamaskin finne perioden? I 1993 fant Daniel Simon, da ved University of Montreal, ut at en kvantealgoritme kunne beregne svaret på et nært beslektet problem eksponentielt raskere enn noen klassisk algoritme.
Resultatet gjorde det mulig for Simon å bestemme et av de første hint om hvor dramatisk overlegenhet for kvantedatamaskiner kunne forventes. Men da han leverte sitt papir til en ledende konferanse, ble det avvist. Avisen interesserte imidlertid et yngre medlem av konferansens programkomité - Peter Shor, som på den tiden var ved Bell Laboratories i New Jersey. Shor fortsatte med å finne ut at han kunne tilpasse Simons algoritme for å beregne perioden til et orakel, hvis det hadde et. Så skjønte han at han kunne tilpasse algoritmen igjen, for å løse en ligning som oppfører seg på samme måte som et periodisk orakel: ligningen som beskriver factoring, som er periodisk.
Shors resultat var historisk. Kvantealgoritmen han oppdaget kunne raskt redusere gigantiske tall til deres konstituerende primfaktorer, noe ingen kjent klassisk algoritme kan gjøre. I årene som fulgte oppdaget forskere andre effektive kvantealgoritmer. Noen av dem, som Shors algoritme, ga til og med eksponentielle fordeler, men ingen kunne bevise en dramatisk kvantefordel på noe NP-problem som ikke var periodisk.
Denne mangelen på fremskritt førte til at to informatikere, Scott Aaronson fra University of Texas, Austin, og Andris Ambainis fra University of Latvia, for å gjøre en observasjon. Bevis på kvantefordeler virket alltid avhengig av orakler som hadde en slags ikke-tilfeldig struktur, for eksempel periodisitet. I 2009, de formodet at det ikke kunne være dramatiske speedups på NP-problemer som var tilfeldige eller ustrukturerte. Ingen kunne finne et unntak.
Formodningen deres satte en grense for kreftene til kvantedatamaskiner. Men den sa bare at det ikke var noen dramatiske hastigheter for en spesifikk type ustrukturert NP-problem - de med ja eller nei svar. Hvis et problem innebar å finne ut mer spesifikke, kvantitative svar, som er kjent som et søkeproblem, gjaldt ikke formodningen.
Med det i tankene, forskere Takashi Yamakawa av NTT Sosialinformatikklaboratorier og Mark Zhandry fra NTT Research og Princeton University bestemte seg for å eksperimentere med et spesifikt søkeproblem, introdusert i 2005 av Oded Regev.
Se for deg et sett med værvinger som alle peker i samme retning. Gi hver av dem et avmålt dytt, og la deretter en vindkast påvirke retningen deres. Regev ønsket å bestemme, basert på deres endelige veibeskrivelse, hvor de alle pekte innledningsvis. Problemer som dette ble kalt "læring med feil", fordi skyvet og vinden fungerer som en kilde til tilfeldig feil i den opprinnelige retningen. Det er bevis på at det er vanskelig å løse for både klassiske og kvantealgoritmer.
Yamakawa og Zhandry finjusterte oppsettet. De endret styrken til de startskuddene, noe som gjorde dem mer forutsigbare. De førte også til at vinden ble bestemt av et tilfeldig orakel slik at den var enda mer tilfeldig i visse tilfeller, men helt i dvale i andre.
Med disse modifikasjonene oppdaget forskerne at en kvantealgoritme effektivt kunne finne den første retningen. De beviste også at enhver klassisk algoritme må være tregere med en eksponentiell faktor. I likhet med Shor tilpasset de deretter algoritmen sin for å løse en virkelig versjon av problemet, som erstatter oraklet med en faktisk matematisk ligning.
Dataforskere jobber fortsatt med å forstå og bygge videre på problemet. Vaikuntanathan sammenligner det med en annen som oppstår når du gjør datakomprimering: Når informasjon blir presset ned, kan to biter ved et uhell presses inn på samme sted og overskrive dem. Problemet med å forutsi disse kollisjonene på forhånd, slik at du kan unngå dem, har en viss likhet. "Det er en klasse med problemer som i utgangspunktet ser slik ut," sa han. "Kanskje disse problemene kan løses kvantum."
Det var håp om at et ustrukturert problem som det nye kunne løses selv på dagens nye versjoner av kvantedatamaskiner, og dermed gi et middel til å teste dem. Tanken var at ustrukturerte problemer kunne ta færre ressurser å programmere, eller være mindre følsomme for støy, siden de allerede er tilfeldige. Men så langt virker det nye problemet fortsatt for avansert til at eksisterende kvantedatamaskiner kan løses. "Det er et merkelig problem. Jeg hadde ikke tenkt på å definere det, sa Aaronson. "Men i ettertid har den noen veldig fine funksjoner."
Resultatet gir det første eksemplet på dramatiske kvantefordeler på et ustrukturert NP-problem. Kan det være mange andre problemer som kvanteverdenen endrer seg fra praktisk talt uløselig til løsbar? Det er nå mer grunn til å mene det.
"Det har snudd litt vår tro på hva slags problemer kvantedatamaskiner kan være gode på," sa O'Donnell.
