1994 kom en matematiker på hur man får en kvantdator att göra något som ingen vanlig klassisk dator kunde. Arbetet avslöjade att, i princip, en maskin baserad på kvantmekanikens regler effektivt kunde bryta in ett stort antal i sina primära faktorer - en uppgift så svår för en klassisk dator att den utgör grunden för mycket av dagens internetsäkerhet.
En våg av optimism följde. Kanske, tänkte forskare, kommer vi att kunna uppfinna kvantalgoritmer som kan lösa ett stort antal olika problem.
Men framstegen avstannade. "Det har varit lite av en bummer bana," sa Ryan O'Donnell från Carnegie Mellon University. "Folk var som," Det här är fantastiskt, jag är säker på att vi kommer att få alla möjliga andra fantastiska algoritmer. Nej." Forskare upptäckte dramatiska hastigheter endast för en enda, smal klass av problem från en standarduppsättning kallas NP, vilket innebär att de hade effektivt verifierbara lösningar - som factoring.
Så var fallet i nästan tre decennier. Sedan i april, forskare uppfunnit en fundamentalt ny typ av problem som en kvantdator borde kunna lösa exponentiellt snabbare än en klassisk. Det innebär att beräkna indata till en komplicerad matematisk process, baserad enbart på dess virriga utdata. Om problemet står ensamt eller är det första i en ny gräns av många andra har ännu inte bestämts.
"Det finns en känsla av spänning," sa Vinod Vaikuntanathan, en datavetare vid Massachusetts Institute of Technology. "Många människor funderar på vad som finns där ute."
Datavetare försöker förstå vad kvantdatorer gör bättre genom att studera matematiska modeller som representerar dem. Ofta föreställer de sig en modell av en kvantdator eller klassisk dator parad med en idealiserad räknemaskin som kallas ett orakel. Orakel är som enkla matematiska funktioner eller datorprogram, som tar in en ingång och spottar ut en förutbestämd utdata. De kan ha ett slumpmässigt beteende, avger "ja" om inmatningen faller inom ett visst slumpmässigt intervall (säg 12 till 67) och "nej" om det inte gör det. Eller de kan vara periodiska, så att en inmatning mellan 1 och 10 returnerar "ja", 11 till 20 ger "nej", 21 till 30 ger "ja" igen, och så vidare.
Låt oss säga att du har ett av dessa periodiska orakel och att du inte känner till perioden. Allt du kan göra är att mata den med siffror och se vad den ger. Med dessa begränsningar, hur snabbt kunde en dator hitta perioden? 1993 fann Daniel Simon, då vid University of Montreal, att en kvantalgoritm kunde beräkna svaret på ett närbesläktat problem exponentiellt snabbare än någon klassisk algoritm.
Resultatet gjorde det möjligt för Simon att avgöra en av de första antydningarna om var dramatisk överlägsenhet för kvantdatorer kunde förväntas. Men när han lämnade in sitt papper till en ledande konferens avslogs det. Tidningen intresserade dock en yngre medlem av konferensens programkommitté — Peter Shor, som vid den tiden var på Bell Laboratories i New Jersey. Shor fortsatte med att hitta att han kunde anpassa Simons algoritm för att beräkna perioden för ett orakel, om det hade ett. Sedan insåg han att han kunde anpassa algoritmen igen, för att lösa en ekvation som beter sig på samma sätt som ett periodiskt orakel: ekvationen som beskriver factoring, som är periodisk.
Shors resultat var historiskt. Kvantalgoritmen han upptäckte kunde snabbt reducera gigantiska siffror till deras ingående primfaktorer, något som ingen känd klassisk algoritm kan göra. Under åren som följde upptäckte forskare andra effektiva kvantalgoritmer. Vissa av dem, som Shors algoritm, gav till och med exponentiell fördel, men ingen kunde bevisa en dramatisk kvantfördel på något NP-problem som inte var periodiskt.
Denna brist på framsteg ledde till att två datavetare, Scott aaronson vid University of Texas, Austin och Andris Ambainis från Lettlands universitet, för att göra en observation. Bevis på kvantfördelar verkade alltid vara beroende av orakel som hade någon form av icke-slumpmässig struktur, såsom periodicitet. 2009 gjorde de conjectured att det inte kunde ske dramatiska snabba uppgångar på NP-problem som var slumpmässiga eller ostrukturerade. Ingen kunde hitta ett undantag.
Deras gissningar satte en gräns för krafterna hos kvantdatorer. Men det stod bara att det inte fanns några dramatiska snabbare för en specifik typ av ostrukturerade NP-problem - de med ja eller nej svar. Om ett problem gällde att ta reda på mer specifika, kvantitativa svar, vilket är känt som ett sökproblem, gällde inte gissningen.
Med det i åtanke, forskare Takashi Yamakawa av NTT Social Informatics Laboratories och Mark Zhandry från NTT Research och Princeton University beslutade att experimentera med ett specifikt sökproblem, som introducerades 2005 av Oded Regev.
Föreställ dig en uppsättning väderflöjlar som alla pekar åt samma håll. Ge var och en av dem ett uppmätt knuff och låt sedan en byig vind påverka deras riktning. Regev ville utifrån sina slutliga anvisningar bestämma var de alla pekade inledningsvis. Problem som detta kom att kallas "lära med fel", eftersom stöten och vinden fungerar som en källa till slumpmässiga fel i den ursprungliga riktningen. Det finns bevis för att det är svårt att lösa för både klassiska och kvantalgoritmer.
Yamakawa och Zhandry justerade inställningen. De ändrade styrkan på de startskotten, vilket gjorde dem mer förutsägbara. De gjorde också att vinden bestämdes av ett slumpmässigt orakel så att den var ännu mer slumpmässig i vissa fall men helt vilande i andra.
Med dessa modifieringar upptäckte forskarna att en kvantalgoritm effektivt kunde hitta den initiala riktningen. De visade också att alla klassiska algoritmer måste vara långsammare med en exponentiell faktor. Liksom Shor anpassade de sedan sin algoritm för att lösa en verklig version av problemet, som ersätter oraklet med en faktisk matematisk ekvation.
Datavetare arbetar fortfarande med att förstå och bygga vidare på problemet. Vaikuntanathan jämför det med en annan som uppstår när man gör datakomprimering: När information pressas ner kan två bitar av misstag klämmas in på samma plats och skriva över dem. Problemet med att förutsäga dessa kollisioner i förväg, så att du kan undvika dem, har en viss likhet. "Det är en klass av problem som i princip ser ut så här," sa han. "Kanske kan dessa problem lösas kvantum."
Det fanns förhoppningar om att ett ostrukturerat problem som det nya skulle kunna lösas även på dagens nystartade versioner av kvantdatorer, och därigenom ge ett sätt att testa dem. Tanken var att ostrukturerade problem kunde ta färre resurser att programmera, eller vara mindre känsliga för brus, eftersom de redan är slumpmässiga. Men än så länge verkar det nya problemet fortfarande vara för avancerat för befintliga kvantdatorer att lösa. "Det är ett konstigt problem. Jag hade inte tänkt på att definiera det, säger Aaronson. "Men i efterhand har den några mycket trevliga funktioner."
Resultatet ger det första exemplet på dramatiska kvantfördelar på ett ostrukturerat NP-problem. Kan det finnas många andra problem som kvantvärlden förändras från praktiskt taget olöslig till lösbar? Det finns nu mer anledning att tro det.
"Det är något omkullkastat vår övertygelse om vilka typer av problem kvantdatorer kan vara bra på," sa O'Donnell.
