En viktig kvantalgoritm kan faktiskt vara en egenskap hos naturen

Konceptuell illustration av DNA dubbel helix Ms. Tech; Originalbild: Wikimedia commons

Redan 1996 publicerade en kvantfysiker vid Bell Labs i New Jersey ett nytt recept för att söka igenom en databas med N poster. Datavetare har länge vetat att denna process tar runt N steg för i värsta fall kan den sista punkten på listan vara den av intresse.

Denna fysiker, Lov Grover, visade dock hur kvantmekanikens konstiga regler gjorde det möjligt för sökningen att göras i ett antal steg lika med kvadratroten av N .

Det var en stor grej. Att söka i databaser är en grundläggande uppgift inom datavetenskap, som används för allt från att hitta telefonnummer till att bryta kryptografiska koder. Så varje snabbhet är ett betydande framsteg.

Relaterad berättelse

Vad är kvantberäkning?

Kvantmekaniken gav en extra twist. Vid den tiden var Grovers recept bara den andra kvantalgoritmen som hade bevisats snabbare än dess klassiska motsvarighet. (Den första var Peter Shors algoritm för faktorisering av tal, som han upptäckte 1994.) Grovers arbete var en viktig faktor för att bereda vägen för kvantberäkningsrevolutionen som fortfarande pågår idag.

Men trots intresset har implementeringen av Grovers algoritm tagit tid på grund av de betydande tekniska utmaningarna. Den första kvantdatorn som kunde implementera den dök upp 1998, men den första skalbara versionen dök inte upp förrän 2017, och även då fungerade den med bara tre qubits. Så nya sätt att implementera algoritmen behövs desperat.

Idag säger Stéphane Guillet och kollegor vid universitetet i Toulon i Frankrike att detta kan vara lättare än någon förväntat sig. De säger att de har bevis för att Grovers sökalgoritm är ett naturligt förekommande fenomen. Vi tillhandahåller det första beviset på att under vissa förhållanden kan elektroner naturligt bete sig som en Grover-sökning, och letar efter defekter i ett material, säger de.

Det har uppenbara konsekvenser för kvantberäkningar, men dess verkliga betydelse kan vara mycket djupare. Under en tid har teoretiker diskuterat huruvida kvantsökning skulle kunna förklara ett av de största mysterierna om livets ursprung. Tanken att Grover-sökningar förekommer i naturen kan äntligen lösa gåtan.

Först lite bakgrund. Eftersom det är så grundläggande kan Grovers sökalgoritm omformuleras på en mängd olika sätt. En av dessa är som en kvantvandring över en yta - hur en kvantpartikel skulle röra sig slumpmässigt från en punkt till en annan.

Relaterad berättelse

Vad är kvantkommunikation? Forskare och företag skapar ultrasäkra kommunikationsnätverk som kan ligga till grund för ett kvantinternet. Så här fungerar det.

Uppenbarligen är denna process ett slags sökande efter tvådimensionellt rum. Men eftersom en kvantpartikel kan utforska många vägar samtidigt är den mycket snabbare än en klassisk sökning.

Ytans beskaffenhet har ett viktigt inflytande på sökningen. Till exempel består en typ av yta av ett kvadratiskt rutnät där kvantpartikeln har fyra möjliga rörelser vid varje vertex.

Men det finns många andra möjliga rutnät; en triangulär, till exempel, där kvantpartikeln har tre val vid varje vertex. Det triangulära nätet är av särskilt intresse på grund av dess likhet med flera naturligt förekommande kristallliknande material, säger Guillet och co.

Teamet fokuserade på att simulera hur en Grover-sökning fungerar efter elektroner som utforskar triangulära och kvadratiska rutnät, men de inkluderade också andra fysiskt realistiska effekter, såsom defekter i rutnätet i form av hål, och kvantegenskaper som störningseffekter.

Resultaten är ögonöppnande. Frågan de ställer är hur snabbt en elektron kan hitta hålet i ett rutnät. Och lagets stora genombrott är att visa att dessa simuleringar återger hur verkliga elektroner beter sig i verkliga material.

Med andra ord är detta bevis på att fria elektroner naturligt implementerar Grovers sökalgoritm när de rör sig över ytan av vissa kristaller.

Relaterad berättelse

Relaterad historia

Det har omedelbara konsekvenser för kvantberäkningar. [Detta arbete] kan vara vägen till ett seriöst tekniskt språng, där experimentalist skulle kringgå behovet av en fullfjädrad skalbar och felkorrigerande kvantdator, och ta genvägen att leta efter 'naturliga händelser' av Grover-sökningen istället, säger laget.

Arbetet har också implikationer för vårt tänkande om den genetiska koden och livets ursprung. Varje levande varelse på jorden använder samma kod, där DNA lagrar information med hjälp av fyra nukleotidbaser. Nukleotidernas sekvenser kodar för information för att konstruera proteiner från ett alfabet på 20 aminosyror.

Men varför dessa siffror – fyra och 20 – och inte några andra? Tillbaka år 2000, bara några år efter att Grover publicerade sitt arbete, Apoorva Patel vid Indian Institute of Science i Bangalore visade hur Grovers algoritm kunde förklara dessa siffror .

Patels idé är relaterad till hur DNA sätts ihop inuti celler. I denna situation måste det molekylära maskineriet inuti en cell söka igenom den molekylära soppan av nukleotidbaser för att hitta den rätta. Om det finns fyra val tar en klassisk sökning i genomsnitt fyra steg. Så maskineriet skulle behöva prova fyra olika baser under varje monteringssteg.

Men en kvantsökning med Grovers algoritm är mycket snabbare: Patel visade att när det finns fyra val, kan en kvantsökning skilja mellan fyra alternativ i ett enda steg. Fyra är faktiskt det optimala antalet.

Detta tänkande förklarar också varför det finns 20 aminosyror. I DNA definierar varje uppsättning av tre nukleotider en enda aminosyra. Så sekvensen av tripletter i DNA definierar sekvensen av aminosyror i ett protein.

Men under proteinsammansättningen måste varje aminosyra väljas från en soppa med 20 olika alternativ. Grovers algoritm förklarar dessa siffror: en trestegs kvantsökning kan hitta ett objekt i en databas som innehåller upp till 20 typer av poster. Återigen är 20 det optimala antalet.

Med andra ord, om sökprocesserna som är involverade i sammansättningen av DNA och proteiner ska vara så effektiva som möjligt, bör antalet baser vara fyra och antalet aminosyror bör vara 20 - exakt som man hittat. Den enda förbehållet är att sökningarna måste vara av kvanttyp.

När Patel publicerade sin idé, slängde kvantfysiker den omedelbart. På den tiden fastnade de i sina egna försök att kontrollera kvantprocesser, vilket de bara kunde göra genom att isolera kvantpartiklar i extrema miljöer som vid temperaturer nära absolut noll.

Det uppenbara problemet, sa de, var att levande saker fungerar i en varm, rörig miljö där kvanttillstånd omedelbart skulle förstöras.

Biologer var lika avvisande och sa att kvantprocesser omöjligt kunde vara verksamma inuti levande varelser.

Sedan dess har allt fler bevis dykt upp för att kvantprocesser spelar en viktig roll i ett antal biologiska mekanismer. Fotosyntes, till exempel, anses nu vara en väsentligen kvantprocess.

Guillet och cos arbete kastar ett nytt perspektiv på allt detta. Det antyder att Grovers algoritm inte bara är möjlig i vissa material; det verkar vara en naturegenskap. Och om det är sant, börjar invändningarna mot Patels idéer att falla sönder.

Det kan vara så att livet bara är ett exempel på Grovers kvantsökning på jobbet, och att denna algoritm i sig är en grundläggande egenskap hos naturen. Det är en stor idé om det någonsin fanns en.

Ref: arxiv.org/abs/1908.11213 : Grover-sökningen som ett naturligt förekommande fenomen

Dölj