En viktig kvantealgoritme kan faktisk være en egenskap ved naturen

Konseptuell illustrasjon av DNA-dobbelthelix Ms. Tech; Originalbilde: Wikimedia commons

Tilbake i 1996 publiserte en kvantefysiker ved Bell Labs i New Jersey en ny oppskrift for å søke gjennom en database med N innganger. Dataforskere har lenge visst at denne prosessen tar rundt N trinn fordi i verste fall kan det siste elementet på listen være det av interesse.

Imidlertid viste denne fysikeren, Lov Grover, hvordan kvantemekanikkens merkelige regler tillot søket å gjøres i et antall trinn lik kvadratroten av N .

Det var en stor sak. Å søke i databaser er en grunnleggende oppgave innen informatikk, som brukes til alt fra å finne telefonnumre til å bryte kryptografiske koder. Så enhver hastighetsoppgang er et betydelig fremskritt.

Relatert historie

Hva er kvanteberegning?

Kvantemekanikk ga en ekstra vri. På den tiden var Grovers oppskrift bare den andre kvantealgoritmen som hadde blitt bevist raskere enn dens klassiske motstykke. (Den første var Peter Shors algoritme for faktorisering av tall, som han oppdaget i 1994.) Grovers arbeid var en viktig faktor for å forberede veien for kvanteberegningsrevolusjonen som fortsatt pågår i dag.

Men til tross for interessen, har implementeringen av Grovers algoritme tatt tid på grunn av de betydelige tekniske utfordringene som er involvert. Den første kvantedatamaskinen som var i stand til å implementere den dukket opp i 1998, men den første skalerbare versjonen dukket ikke opp før i 2017, og selv da fungerte den med bare tre qubits. Så det er et desperat behov for nye måter å implementere algoritmen på.

I dag sier Stéphane Guillet og kolleger ved universitetet i Toulon i Frankrike at dette kan være enklere enn noen forventet. De sier de har bevis på at Grovers søkealgoritme er et naturlig forekommende fenomen. Vi gir det første beviset på at elektroner under visse forhold naturlig kan oppføre seg som et Grover-søk, på jakt etter defekter i et materiale, sier de.

Det har åpenbare implikasjoner for kvanteberegning, men dens virkelige betydning kan være mye mer dyptgripende. I noen tid har teoretikere diskutert om kvantesøk kan forklare et av de største mysteriene om livets opprinnelse. Ideen om at Grover-søk forekommer i naturen kan endelig løse gåten.

Først litt bakgrunn. Fordi den er så grunnleggende, kan Grovers søkealgoritme omformuleres på en rekke måter. En av disse er som en kvantevandring over en overflate - måten en kvantepartikkel vil bevege seg tilfeldig fra ett punkt til et annet.

Relatert historie

Hva er kvantekommunikasjon? Forskere og bedrifter lager ultrasikre kommunikasjonsnettverk som kan danne grunnlaget for et kvanteinternett. Slik fungerer det.

Det er klart at denne prosessen er en slags søk etter todimensjonalt rom. Men fordi en kvantepartikkel kan utforske mange veier samtidig, er den mye raskere enn et klassisk søk.

Overflatens beskaffenhet har en viktig innflytelse på søket. For eksempel består en type overflate av et kvadratisk rutenett der kvantepartikkelen har fire mulige bevegelser ved hvert toppunkt.

Men det er mange andre mulige rutenett; en trekantet, for eksempel, hvor kvantepartikkelen har tre valg ved hvert toppunkt. Det trekantede rutenettet er av spesiell interesse på grunn av dets likhet med flere naturlig forekommende krystalllignende materialer, sier Guillet og co.

Teamet fokuserte på å simulere måten et Grover-søk fungerer etter elektroner som utforsker trekantede og firkantede rutenett, men de inkluderte også andre fysisk realistiske effekter, som defekter i rutenettet i form av hull, og kvanteegenskaper som interferenseffekter.

Resultatene er øyeåpnende. Spørsmålet de stiller er hvor raskt et elektron kan finne hullet i et rutenett. Og teamets store gjennombrudd er å vise at disse simuleringene gjengir måten ekte elektroner oppfører seg i virkelige materialer.

Med andre ord er dette bevis på at frie elektroner naturlig implementerer Grover-søkealgoritmen når de beveger seg over overflaten til visse krystaller.

Relatert historie

Beslektet historie

Det har umiddelbare implikasjoner for kvanteberegning. [Dette arbeidet] kan være veien til et seriøst teknologisk sprang, der eksperimentelt ville omgå behovet for en fullverdig skalerbar og feilkorrigerende kvantedatamaskin, og ta snarveien til å se etter 'naturlige forekomster' av Grover-søket i stedet, sier teamet.

Arbeidet har også implikasjoner for vår tenkning om den genetiske koden og livets opprinnelse. Hver levende skapning på jorden bruker den samme koden, der DNA lagrer informasjon ved hjelp av fire nukleotidbaser. Sekvensene til nukleotider koder for informasjon for å konstruere proteiner fra et alfabet på 20 aminosyrer.

Men hvorfor disse tallene – fire og 20 – og ikke noen andre? Tilbake i 2000, bare noen få år etter at Grover publiserte arbeidet sitt, Apoorva Patel ved Indian Institute of Science i Bangalore viste hvordan Grovers algoritme kunne forklare disse tallene .

Patels idé er relatert til måten DNA er satt sammen inne i celler. I denne situasjonen må det molekylære maskineriet inne i en celle søke gjennom den molekylære suppen av nukleotidbaser for å finne den rette. Hvis det er fire valg, tar et klassisk søk ​​fire trinn i gjennomsnitt. Så maskineriet måtte prøve fire forskjellige baser under hvert monteringstrinn.

Men et kvantesøk ved hjelp av Grovers algoritme er mye raskere: Patel viste at når det er fire valg, kan et kvantesøk skille mellom fire alternativer i et enkelt trinn. Faktisk er fire optimalt tall.

Denne tenkningen forklarer også hvorfor det er 20 aminosyrer. I DNA definerer hvert sett med tre nukleotider en enkelt aminosyre. Så sekvensen av tripletter i DNA definerer sekvensen av aminosyrer i et protein.

Men under proteinsamlingen må hver aminosyre velges fra en suppe med 20 forskjellige alternativer. Grovers algoritme forklarer disse tallene: et tre-trinns kvantesøk kan finne et objekt i en database som inneholder opptil 20 typer oppføringer. Igjen, 20 er det optimale tallet.

Med andre ord, hvis søkeprosessene som er involvert i å sette sammen DNA og proteiner skal være så effektive som mulig, bør antall baser være fire og antall aminosyrer bør være 20 - nøyaktig slik det er funnet. Det eneste forbeholdet er at søkene må være kvantemessige.

Da Patel publiserte ideen sin, slo kvantefysikere den umiddelbart. På den tiden satt de fast i sine egne forsøk på å kontrollere kvanteprosesser, noe de bare kunne gjøre ved å isolere kvantepartikler i ekstreme miljøer som ved temperaturer nær absolutt null.

Det åpenbare problemet, sa de, var at levende ting opererer i et varmt, rotete miljø der kvantetilstander umiddelbart ville bli ødelagt.

Biologer var like avvisende og sa at kvanteprosesser umulig kunne virke inne i levende ting.

Siden den gang har det dukket opp stadig flere bevis for at kvanteprosesser spiller en viktig rolle i en rekke biologiske mekanismer. Fotosyntese, for eksempel, antas nå å være en hovedsakelig kvanteprosess.

Arbeidet til Guillet og co kaster et nytt perspektiv på alt dette. Det antyder at Grovers algoritme ikke bare er mulig i visse materialer; det ser ut til å være en naturegenskap. Og hvis det er sant, begynner innvendingene mot Patels ideer å smuldre.

Det kan være at livet bare er et eksempel på Grovers kvantesøk på jobb, og at denne algoritmen i seg selv er en grunnleggende egenskap ved naturen. Det er en stor idé hvis det noen gang har vært en.

Ref: arxiv.org/abs/1908.11213 : Grover-søket som et naturlig forekommende fenomen

gjemme seg