211service.com
Quantum Computing har nu ett kraftfullt sökverktyg
Grovers algoritm
Redan 1996 avslöjade en datavetare vid namn Lov Grover vid Bell Labs i New Jersey en ovanlig algoritm för att söka igenom en databas. Sökalgoritmer är bland de viktigaste inom datavetenskap. De möjliggör vardagliga uppgifter som att leta igenom telefonböcker men också mer exotiska uppgifter som att bryta kryptografiska koder. Den här typen av algoritmer finns överallt inom datavetenskap.
Så varje sätt att påskynda uppgiften är enormt betydelsefullt. En standardsökning tar en tidsperiod som är ungefär proportionell mot antalet element i sökningen. Det beror på att algoritmen i värsta fall måste söka igenom alla element för att bara hitta en.
Men Grovers algoritm är annorlunda. Tiden det tar är proportionell mot kvadratroten av antalet element. Datavetare kallar detta en kvadratisk hastighetshöjning. Och i en värld där hastighetsökningar på några bråkdelar av en procent är enormt värdefulla, är en kvadratisk hastighetshöjning en imponerande prestation.
Grovers trick var att använda de märkliga men kraftfulla idéerna bakom kvantmekaniken. I den klassiska världen är bitar bara 0:or och 1:or. Men i kvantvärlden kan en enda kvantbit, eller qubit, vara 0 och 1 samtidigt. Fysiker säger att qubiten är i en superposition av tillstånd.
Superpositionen är nyckeln. I detta tillstånd kan en algoritm söka både 0:an och 1:an i samma ögonblick. Eftersom den kan söka i mer än ett element samtidigt, kan en kvantalgoritm söka igenom en lista mycket snabbare än en algoritm som begränsas av den klassiska fysikens plågsamma takt.
Kvantalgoritmer måste implementeras av en kvantdator, och 1996, när Grover gjorde sitt arbete, var dessa lite mer än en avlägsen dröm. Men genombrottet kom snabbt. Fysiker demonstrerade den första primitiva kvantdatorn 1998 och visade hur den kunde köra Grovers algoritm samma år.
Men just denna form av kvantberäkning var extremt begränsad. Det fungerade på några qubits men inte mer och kunde inte ens i princip skalas upp till större beräkningar. Detta problem med att bygga och demonstrera skalbara kvantdatorer har plågat disciplinen sedan dess.
Nu, cirka 20 år senare, börjar fysiker bygga kvantdatorer som har potential att skala och som därför kan göra mer kraftfulla beräkningar. Och idag säger Caroline Figgatt och kompisar från University of Maryland att de har kört Grovers algoritm på en skalbar kvantdator för första gången.
Arbetet demonstrerar kvantberäkningarnas snabba hastighet och banar väg för mer ambitiöst arbete med algoritmen som kan börja knäcka verkliga utmaningar som kodbrott.
Kvantdatorn som Figgatt och co arbetar med består av en sträng av fem ytterbiumjoner suspenderade i ett elektromagnetiskt fält. Varje jon är som en liten magnet som kan orienteras uppåt eller nedåt och vändas från ett tillstånd till ett annat med en laser. På så sätt kan varje jon lagra information: en 1 för att snurra upp och en 0 för att snurra ner till exempel. Och eftersom de är kvantobjekt kan jonerna existera i en superposition av dessa tillstånd.
Jonerna interagerar också med varandra via de frånstötande krafterna som är förknippade med deras positiva laddning. Denna interaktion tillåter en qubit att interagera med en annan qubit för att bearbeta information. Detta är kärnan i kvantberäkning. Ordningen på stegen i denna beräkning är kvantalgoritmen, i detta fall Grovers algoritm.
Figgatt och co använder sitt system för att skapa en tre-qubit kvantdator som kan lagra upp till åtta objekt i en databas. De utför sedan Grovers algoritm för att visa att det är möjligt att hitta ett föremål betydligt snabbare, i genomsnitt, än en klassisk dator som skulle kräva minst åtta bitar. Vi rapporterar resultat för en komplett tre-qubit Grover-sökalgoritm som använder den skalbara kvantberäkningstekniken för fångade atomjoner, med bättre prestanda än klassisk, säger Figgatt och co.
Det är ett intressant arbete med stor potential. Detta banar väg för mer omfattande användning av Grovers sökalgoritm för att lösa större problem på kvantdatorer, inklusive att använda kretsen som en subrutin för andra kvantalgoritmer, säger teamet.
Men arbetet ger också en intressant inblick i kapplöpningen om att bygga kraftfulla kvantdatorer. Vinnaren av detta lopp kommer sannolikt att skörda enorma ekonomiska belöningar, men ingen är helt säker på vilken teknik som är bäst.
Denna värld har kastats i förvirring av en kanadensisk startup som heter D-Wave Systems som har sålt till synes kraftfulla kvantdatorer till företag som Google och Lockheed Martin. Dessa datorer fungerar med 1 000 qubits, mycket mer än någon annan teknik.
Men många teoretiker säger att D-Waves påståenden är överdrivna och att dess maskiner inte kan producera i närheten av den typ av beräkningskraft som andra kvantdatorer borde kunna.
Det är därför många grupper försöker kommersialisera andra kvantteknologier som skiljer sig dramatiskt i hur de lagrar och bearbetar kvantinformation. Dessa förlitar sig på olika sätt på fotoner, elektroner, atomer, joner och molekyler för att göra sina kvantbud.
Av dessa tekniker är en av de äldsta och bäst utvecklade kvantberäkningarna med jonfällor, och University of Maryland-gruppen är världsledande på detta område. Faktum är att gruppens ledare, Chris Monroe, har en startup som heter IonQ som syftar till att kommersialisera denna teknik.
Så demonstrationen av en skalbar kvantdator som kan implementera Grovers algoritm, om än med bara tre qubits, kan ses som en avsiktsförklaring.
1998, efter den första implementeringen av Grovers algoritm, fanns det en rad åsikter om hur lång tid det skulle ta fysiker att göra nästa steg skalbara datorer. Ett antal startups bildades och kollapsade baserat på optimistiska prognoser. Men på den tiden var 20 år vid det pessimistiska slutet av spektrumet av förutsägelser. Att det har tagit så lång tid sätter i perspektiv uppgiftens svårighetsgrad.
Det är svårt att kontrollera universum på kvantskalan. En intressant fråga nu för teknologer och riskkapitalister är om takten för tekniska framsteg kan påskyndas avsevärt.
Ref: arxiv.org/abs/1703.10535 : Slutför 3-Qubit Grover-sökning på en programmerbar kvantdator