En vigtig kvantealgoritme kan faktisk være en egenskab ved naturen

Konceptuel illustration af DNA dobbelt helix Ms. Tech; Originalbillede: Wikimedia commons

Tilbage i 1996 udgav en kvantefysiker ved Bell Labs i New Jersey en ny opskrift på at søge gennem en database med N indgange. Dataloger har længe vidst, at denne proces tager rundt N trin, fordi i værste fald kan det sidste punkt på listen være det, der er af interesse.

Denne fysiker, Lov Grover, viste imidlertid, hvordan kvantemekanikkens mærkelige regler tillod søgningen i et antal trin svarende til kvadratroden af N .

Det var en stor ting. At søge i databaser er en grundlæggende opgave inden for datalogi, der bruges til alt fra at finde telefonnumre til at bryde kryptografiske koder. Så enhver fremskyndelse er et betydeligt fremskridt.

Relateret historie

Hvad er kvanteberegning?

Kvantemekanikken gav et ekstra twist. På det tidspunkt var Grovers opskrift kun den anden kvantealgoritme, der var blevet bevist hurtigere end dens klassiske modstykke. (Den første var Peter Shors algoritme til faktorisering af tal, som han opdagede i 1994.) Grovers arbejde var en vigtig faktor i at bane vejen for kvantecomputerrevolutionen, der stadig er i gang i dag.

Men på trods af interessen har implementeringen af ​​Grovers algoritme taget tid på grund af de betydelige tekniske udfordringer, der er involveret. Den første kvantecomputer, der var i stand til at implementere det, dukkede op i 1998, men den første skalerbare version dukkede ikke op før 2017, og selv da fungerede den med kun tre qubits. Så der er et desperat behov for nye måder at implementere algoritmen på.

I dag siger Stéphane Guillet og kolleger ved universitetet i Toulon i Frankrig, at dette kan være lettere, end nogen havde forventet. De siger, at de har beviser for, at Grovers søgealgoritme er et naturligt forekommende fænomen. Vi giver det første bevis på, at elektroner under visse forhold naturligt kan opføre sig som en Grover-søgning, der leder efter defekter i et materiale, siger de.

Det har indlysende implikationer for kvanteberegning, men dets reelle betydning kan være meget mere dybtgående. I nogen tid har teoretikere diskuteret, om kvantesøgning kunne forklare et af de største mysterier om livets oprindelse. Ideen om, at Grover-søgninger finder sted i naturen, kunne endelig løse gåden.

Først lidt baggrund. Fordi det er så fundamentalt, kan Grovers søgealgoritme omformuleres på en række forskellige måder. En af disse er som en kvantevandring hen over en overflade - den måde en kvantepartikel ville bevæge sig tilfældigt fra et punkt til et andet.

Relateret historie

Hvad er kvantekommunikation? Forskere og virksomheder skaber ultrasikre kommunikationsnetværk, der kan danne grundlag for et kvanteinternet. Sådan fungerer det.

Det er klart, at denne proces er en slags søgen efter todimensionelt rum. Men fordi en kvantepartikel kan udforske mange veje på samme tid, er den meget hurtigere end en klassisk søgning.

Overfladens beskaffenhed har en vigtig indflydelse på søgningen. For eksempel består en type overflade af et kvadratisk gitter, hvor kvantepartiklen har fire mulige bevægelser ved hvert toppunkt.

Men der er mange andre mulige gitter; en trekantet, for eksempel, hvor kvantepartiklen har tre valgmuligheder ved hvert toppunkt. Det trekantede gitter er af særlig interesse på grund af dets lighed med flere naturligt forekommende krystallignende materialer, siger Guillet og co.

Holdet fokuserede på at simulere den måde, en Grover-søgning fungerer efter elektroner, der udforsker trekantede og firkantede gitter, men de inkluderede også andre fysisk realistiske effekter, såsom defekter i gitteret i form af huller, og kvanteegenskaber såsom interferenseffekter.

Resultaterne er øjenåbnende. Spørgsmålet, de stiller, er, hvor hurtigt en elektron kan finde hullet i et gitter. Og holdets store gennembrud er at vise, at disse simuleringer gengiver den måde, rigtige elektroner opfører sig på i rigtige materialer.

Med andre ord er dette bevis på, at frie elektroner naturligt implementerer Grover-søgealgoritmen, når de bevæger sig hen over overfladen af ​​visse krystaller.

Relateret historie

Relateret historie

Det har umiddelbare konsekvenser for kvanteberegning. [Dette arbejde] kan være vejen til et seriøst teknologisk spring, hvor eksperimentelt ville omgå behovet for en fuldgyldig skalerbar og fejlkorrigerende kvantecomputer og tage genvejen til at lede efter 'naturlige forekomster' af Grover-søgningen i stedet, siger holdet.

Værket har også betydning for vores tænkning om den genetiske kode og livets oprindelse. Alle levende væsener på Jorden bruger den samme kode, hvori DNA lagrer information ved hjælp af fire nukleotidbaser. Nukleotidsekvenserne koder for information til konstruktion af proteiner ud fra et alfabet på 20 aminosyrer.

Men hvorfor disse tal – fire og 20 – og ikke nogle andre? Tilbage i 2000, blot et par år efter Grover udgav sit arbejde, Apoorva Patel ved Indian Institute of Science i Bangalore viste, hvordan Grovers algoritme kunne forklare disse tal .

Patels idé er relateret til den måde, DNA er samlet inde i celler. I denne situation skal det molekylære maskineri inde i en celle søge gennem den molekylære suppe af nukleotidbaser for at finde den rigtige. Hvis der er fire valgmuligheder, tager en klassisk søgning i gennemsnit fire trin. Så maskineriet skulle prøve fire forskellige baser under hvert monteringstrin.

Men en kvantesøgning ved hjælp af Grovers algoritme er meget hurtigere: Patel viste, at når der er fire valg, kan en kvantesøgning skelne mellem fire alternativer i et enkelt trin. Faktisk er fire det optimale tal.

Denne tankegang forklarer også, hvorfor der er 20 aminosyrer. I DNA definerer hvert sæt af tre nukleotider en enkelt aminosyre. Så sekvensen af ​​tripletter i DNA definerer sekvensen af ​​aminosyrer i et protein.

Men under proteinsamlingen skal hver aminosyre vælges fra en suppe med 20 forskellige muligheder. Grovers algoritme forklarer disse tal: en tre-trins kvantesøgning kan finde et objekt i en database, der indeholder op til 20 slags indtastninger. Igen er 20 det optimale tal.

Med andre ord, hvis søgeprocesserne involveret i at samle DNA og proteiner skal være så effektive som muligt, skal antallet af baser være fire, og antallet af aminosyrer skal være 20 - præcis som det er fundet. Det eneste forbehold er, at søgningerne skal være kvantemæssige.

Da Patel offentliggjorde sin idé, pjuskede kvantefysikere den med det samme. På det tidspunkt var de bundet fast i deres egne forsøg på at kontrollere kvanteprocesser, hvilket de kun kunne gøre ved at isolere kvantepartikler i ekstreme miljøer såsom ved temperaturer tæt på det absolutte nulpunkt.

Det åbenlyse problem, sagde de, var, at levende ting opererer i et varmt, rodet miljø, hvor kvantetilstande øjeblikkeligt ville blive ødelagt.

Biologer var lige så afvisende og sagde, at kvanteprocesser umuligt kunne være på arbejde inde i levende ting.

Siden da er der dukket et stigende antal beviser på, at kvanteprocesser spiller en vigtig rolle i en række biologiske mekanismer. Fotosyntese, for eksempel, menes nu at være en i det væsentlige kvanteproces.

Guillet og co's arbejde kaster et nyt perspektiv på alt dette. Det tyder på, at Grovers algoritme ikke kun er mulig i visse materialer; det synes at være en egenskab ved naturen. Og hvis det er sandt, så begynder indvendingerne mod Patels ideer at smuldre.

Det kan være, at livet blot er et eksempel på Grovers kvantesøgning på arbejde, og at denne algoritme i sig selv er en fundamental egenskab ved naturen. Det er en stor idé, hvis der nogensinde har været en.

Ref: arxiv.org/abs/1908.11213 : Grover-søgningen som et naturligt forekommende fænomen

skjule