Svarbus kvantinis algoritmas iš tikrųjų gali būti gamtos savybė

Konceptuali DNR dvigubos spiralės iliustracija Ponia Tech; Originalus vaizdas: Wikimedia commons

1996 m. kvantinis fizikas iš Bell Labs Naujajame Džersyje paskelbė naują receptą, kaip ieškoti duomenų bazėje. N įrašų. Kompiuterių mokslininkai jau seniai žinojo, kad šis procesas trunka maždaug N veiksmus, nes blogiausiu atveju paskutinis sąrašo elementas gali būti dominantis.

Tačiau šis fizikas Lovas Groveris parodė, kaip keistos kvantinės mechanikos taisyklės leido atlikti paiešką keliais žingsniais, lygiais kvadratinei šaknis. N .

Tai buvo didelis dalykas. Ieškoti duomenų bazėse yra pagrindinė kompiuterių mokslo užduotis, naudojama viskam – nuo ​​telefono numerių paieškos iki kriptografinių kodų sulaužymo. Taigi bet koks pagreitis yra reikšminga pažanga.

Susijusi istorija

Kas yra kvantinė kompiuterija?

Kvantinė mechanika suteikė papildomo posūkio. Tuo metu Groverio receptas buvo tik antrasis kvantinis algoritmas, kuris buvo įrodytas greičiau nei jo klasikinis atitikmuo. (Pirmasis buvo Piterio Šoro algoritmas faktoringo skaičiavimo skaičiams, kurį jis atrado 1994 m.) Groverio darbas buvo svarbus veiksnys ruošiant kelią kvantinio skaičiavimo revoliucijai, kuri tebevyksta ir šiandien.

Tačiau nepaisant susidomėjimo, Groverio algoritmo įgyvendinimas užtruko dėl didelių techninių iššūkių. Pirmasis kvantinis kompiuteris, galintis jį įgyvendinti, pasirodė 1998 m., tačiau pirmoji keičiamo dydžio versija pasirodė tik 2017 m. ir net tada dirbo tik su trimis kubitais. Taigi labai reikalingi nauji algoritmo įgyvendinimo būdai.

Šiandien Stéphane'as Guillet ir kolegos iš Tulono universiteto Prancūzijoje sako, kad tai gali būti lengviau nei bet kas tikėjosi. Jie sako, kad turi įrodymų, kad Groverio paieškos algoritmas yra natūralus reiškinys. Mes pateikiame pirmuosius įrodymus, kad tam tikromis sąlygomis elektronai gali natūraliai elgtis kaip Groverio paieška, ieškodami medžiagos defektų, sako jie.

Tai turi akivaizdžių pasekmių kvantiniam skaičiavimui, tačiau tikroji jos reikšmė gali būti daug gilesnė. Kurį laiką teoretikai diskutavo, ar kvantinė paieška galėtų paaiškinti vieną didžiausių gyvybės kilmės paslapčių. Idėja, kad Groverio paieškos vyksta gamtoje, pagaliau galėtų išspręsti mįslę.

Pirmiausia šiek tiek fono. Kadangi Groverio paieškos algoritmas yra toks esminis, jį galima performuluoti įvairiais būdais. Vienas iš jų yra kvantinis ėjimas per paviršių – būdas, kuriuo kvantinė dalelė atsitiktinai judėtų iš vieno taško į kitą.

Susijusi istorija

Kas yra kvantinė komunikacija? Mokslininkai ir įmonės kuria itin saugius ryšio tinklus, kurie galėtų būti kvantinio interneto pagrindas. Tai veikia taip.

Akivaizdu, kad šis procesas yra savotiška dvimatės erdvės paieška. Tačiau kadangi kvantinė dalelė gali vienu metu tyrinėti daug kelių, tai daug greičiau nei klasikinė paieška.

Paviršiaus pobūdis turi didelę įtaką paieškai. Pavyzdžiui, vieno tipo paviršių sudaro kvadratinis tinklelis, kuriame kvantinė dalelė turi keturis galimus judesius kiekvienoje viršūnėje.

Tačiau yra daug kitų galimų tinklelių; pavyzdžiui, trikampis, kur kvantinė dalelė turi tris pasirinkimus kiekvienoje viršūnėje. Trikampė tinklelis yra ypač įdomus dėl savo panašumo į keletą natūraliai pasitaikančių į kristalą panašių medžiagų, tarkime, Guillet ir kt.

Komanda daugiausia dėmesio skyrė modeliavimui, kaip Groverio paieška veikia elektronams, tyrinėjantiems trikampius ir kvadratinius tinklus, tačiau jie taip pat apėmė kitus fiziškai realistiškus efektus, tokius kaip tinklelio defektai skylių pavidalu ir kvantinės savybės, pvz., trukdžių efektai.

Rezultatai atveria akis. Jie užduoda klausimą, kaip greitai elektronas gali rasti tinklelyje esančią skylę. Ir didelis komandos proveržis yra parodyti, kad šie modeliai atkuria tai, kaip tikri elektronai elgiasi tikrose medžiagose.

Kitaip tariant, tai yra įrodymas, kad laisvieji elektronai, judėdami tam tikrų kristalų paviršiumi, natūraliai įgyvendina Groverio paieškos algoritmą.

Susijusi istorija

Susijusi istorija

Tai turi tiesioginį poveikį kvantiniam skaičiavimui. [Šis darbas] gali būti kelias į rimtą technologinį šuolį, kai eksperimentatorius apeitų poreikį sukurti visavertį keičiamo dydžio ir klaidų taisymo kvantinį kompiuterį, o vietoj to imtų ieškoti „natūralių Groverio paieškos įvykių“, sako komanda.

Darbas taip pat turi įtakos mūsų mąstymui apie genetinį kodą ir gyvybės kilmę. Kiekvienas gyvas padaras Žemėje naudoja tą patį kodą, kuriame DNR saugo informaciją naudodama keturias nukleotidų bazes. Nukleotidų sekos koduoja informaciją, skirtą baltymams konstruoti iš 20 aminorūgščių abėcėlės.

Bet kodėl šie skaičiai – keturi ir 20 –, o ne kai kurie kiti? 2000 m., praėjus vos keleriems metams po to, kai Groveris paskelbė savo darbą, Apoorva Patel iš Indijos mokslo instituto Bangalore parodė, kaip Groverio algoritmas gali paaiškinti šiuos skaičius .

Patelio idėja yra susijusi su DNR surinkimo būdu ląstelėse. Esant tokiai situacijai, ląstelės viduje esantis molekulinis mechanizmas turi ieškoti nukleotidų bazių molekulinės sriubos, kad surastų tinkamą. Jei yra keturi pasirinkimai, klasikinė paieška vidutiniškai trunka keturis veiksmus. Taigi kiekviename surinkimo etape mašinos turėtų išbandyti keturias skirtingas bazes.

Tačiau kvantinė paieška naudojant Groverio algoritmą yra daug greitesnė: Patelis parodė, kad kai yra keturi pasirinkimai, kvantinė paieška gali atskirti keturias alternatyvas vienu žingsniu. Iš tiesų, keturi yra optimalus skaičius.

Šis mąstymas taip pat paaiškina, kodėl yra 20 aminorūgščių. DNR kiekvienas trijų nukleotidų rinkinys apibrėžia vieną aminorūgštį. Taigi tripletų seka DNR apibrėžia aminorūgščių seką baltyme.

Tačiau baltymų surinkimo metu kiekviena aminorūgštis turi būti pasirinkta iš 20 skirtingų variantų sriubos. Groverio algoritmas paaiškina šiuos skaičius: trijų žingsnių kvantinė paieška gali rasti objektą duomenų bazėje, kurioje yra iki 20 rūšių įrašų. Vėlgi, 20 yra optimalus skaičius.

Kitaip tariant, jei paieškos procesai, susiję su DNR ir baltymų surinkimu, turi būti kuo veiksmingesni, bazių skaičius turi būti keturios, o aminorūgščių skaičius – 20 – tiksliai toks, koks yra nustatytas. Vienintelis įspėjimas yra tas, kad paieškos turi būti kvantinės.

Kai Patelis paskelbė savo idėją, kvantiniai fizikai iš karto ją apėmė. Tuo metu jie buvo įstrigę savo pačių bandymuose kontroliuoti kvantinius procesus, o tai galėjo padaryti tik izoliuodami kvantines daleles ekstremaliose aplinkose, pavyzdžiui, esant absoliučiam nuliui artimai temperatūrai.

Akivaizdi problema, pasak jų, buvo ta, kad gyvi daiktai veikia šiltoje, netvarkingoje aplinkoje, kurioje kvantinės būsenos būtų nedelsiant sunaikintos.

Biologai buvo vienodai atmetę sakydami, kad kvantiniai procesai gyvų būtybių viduje negali veikti.

Nuo tada atsirado vis daugiau įrodymų, kad kvantiniai procesai atlieka svarbų vaidmenį daugelyje biologinių mechanizmų. Pavyzdžiui, dabar manoma, kad fotosintezė iš esmės yra kvantinis procesas.

Guillet ir bendradarbiai į visa tai pažvelgia naujai. Tai rodo, kad Groverio algoritmas įmanomas ne tik tam tikrose medžiagose; atrodo, kad tai gamtos turtas. Ir jei tai tiesa, tada prieštaravimai Patelio idėjoms pradeda byrėti.

Gali būti, kad gyvenimas yra tik Groverio kvantinės paieškos darbe pavyzdys ir kad šis algoritmas pats yra pagrindinė gamtos savybė. Tai didelė idėja, jei tokia buvo.

Nuoroda: arxiv.org/abs/1908.11213 : Groverio paieška kaip natūralus reiškinys

paslėpti