Kvantinė kompiuterija dabar turi galingą paieškos įrankį

Groverio algoritmas

1996 m. kompiuterių mokslininkas Lovas Groveris iš Bell Labs Naujajame Džersyje pristatė neįprastą paieškos duomenų bazėje algoritmą. Paieškos algoritmai yra vieni svarbiausių kompiuterių moksle. Jie leidžia atlikti kasdienes užduotis, tokias kaip medžioklė per telefonų knygas, bet ir egzotiškesnes užduotis, tokias kaip kriptografinių kodų sulaužymas. Toks algoritmas yra visur paplitęs kompiuterių moksle.

Taigi bet koks būdas pagreitinti užduotį yra labai svarbus. Standartinė paieška trunka tam tikrą laikotarpį, kuris yra maždaug proporcingas paieškoje esančių elementų skaičiui. Taip yra todėl, kad blogiausiu atveju algoritmas turi ieškoti visų elementų, kad rastų tik vieną.

Tačiau Groverio algoritmas skiriasi. Laikas, kurio reikia, yra proporcingas elementų skaičiaus kvadratinei šakniai. Kompiuterių mokslininkai tai vadina kvadratiniu greičiu. Ir pasaulyje, kuriame greičio padidėjimas keliomis procentų dalimis yra labai vertingas, kvadratinis pagreitis yra didžiulis pasiekimas.

Groverio gudrybė buvo panaudoti keistas, bet galingas kvantinės mechanikos idėjas. Klasikiniame pasaulyje bitai yra tik 0 ir 1. Tačiau kvantiniame pasaulyje vienas kvantinis bitas arba kubitas gali būti 0 ir 1 tuo pačiu metu. Fizikai teigia, kad kubitas yra būsenų superpozicijoje.

Superpozicija yra raktas. Šioje būsenoje algoritmas gali ieškoti ir 0, ir 1 tą pačią akimirką. Kadangi kvantinis algoritmas gali ieškoti daugiau nei vieno elemento vienu metu, jis gali ieškoti sąraše daug greičiau nei algoritmas, kurį riboja sparčiai augantis klasikinės fizikos tempas.

Kvantinius algoritmus turi įgyvendinti kvantinis kompiuteris, o 1996 m., kai Groveris atliko savo darbą, tai buvo tik tolima svajonė. Tačiau lūžis atėjo greitai. Fizikai pademonstravo pirmąjį primityvų kvantinį kompiuterį 1998 m. ir parodė, kaip tais pačiais metais jis gali vykdyti Groverio algoritmą.

Tačiau ši konkreti kvantinio skaičiavimo forma buvo labai ribota. Jis veikė keliais kubitais, bet ne daugiau ir net iš esmės niekada negalėjo būti padidintas iki didesnių skaičiavimų. Ši keičiamo dydžio kvantinių kompiuterių kūrimo ir demonstravimo problema nuo to laiko kamuoja discipliną.

Dabar, praėjus maždaug 20 metų, fizikai pradeda kurti kvantinius kompiuterius, kurie gali padidinti mastelį ir todėl gali atlikti galingesnius skaičiavimus. Ir šiandien Caroline Figgatt ir draugai iš Merilendo universiteto sako, kad pirmą kartą įvykdė Groverio algoritmą keičiamo dydžio kvantiniame kompiuteryje.

Darbas demonstruoja spartų kvantinių skaičiavimų pagreitį ir atveria kelią ambicingesniam darbui naudojant algoritmą, kuris galėtų pradėti įveikti realaus pasaulio iššūkius, tokius kaip kodo laužymas.

Kvantinis kompiuteris, su kuriuo dirba Figgattas ir bendradarbiai, susideda iš penkių iterbio jonų, pakibusių elektromagnetiniame lauke, eilutės. Kiekvienas jonas yra tarsi mažas magnetas, kurį galima nukreipti aukštyn arba žemyn ir persukti iš vienos būsenos į kitą lazeriu. Tokiu būdu kiekvienas jonas gali saugoti informaciją: pavyzdžiui, 1 – sukimuisi aukštyn ir 0 – sukimui žemyn. Ir kadangi jie yra kvantiniai objektai, jonai gali egzistuoti šių būsenų superpozicijoje.

Jonai taip pat sąveikauja vienas su kitu per atstumiančias jėgas, susijusias su jų teigiamu krūviu. Ši sąveika leidžia vienam kubitui sąveikauti su kitu kubitu, kad apdorotų informaciją. Tai yra kvantinio skaičiavimo esmė. Šio skaičiavimo žingsnių tvarka yra kvantinis algoritmas, šiuo atveju Groverio algoritmas.

Figgatt ir bendradarbiai naudoja savo sistemą, kad sukurtų trijų kubitų kvantinį kompiuterį, kuriame duomenų bazėje galima saugoti iki aštuonių elementų. Tada jie atlieka Groverio algoritmą, kad parodytų, jog galima rasti elementą vidutiniškai žymiai greičiau nei klasikiniame kompiuteryje, kuriam reikėtų bent aštuonių bitų. Mes pranešame apie viso trijų kubitų Groverio paieškos algoritmo, naudojant keičiamo dydžio įstrigusių atominių jonų kvantinio skaičiavimo technologiją, kurios našumas yra geresnis nei klasikinis, rezultatus, sako Figgatt ir kt.

Tai įdomus darbas, turintis didelį potencialą. Tai atveria kelią plačiau naudoti Grover paieškos algoritmą sprendžiant didesnes kvantinių kompiuterių problemas, įskaitant grandinės naudojimą kaip kitų kvantinių algoritmų paprogramę, teigia komanda.

Tačiau šis darbas taip pat suteikia įdomų žvilgsnį į galingų kvantinių kompiuterių kūrimo lenktynes. Tikėtina, kad šių lenktynių nugalėtojas gaus didžiulį finansinį atlygį, tačiau niekas nėra tikras, kuri technologija yra geriausia.

Šį pasaulį sumaišė Kanados startuolis, pavadintas „D-Wave Systems“, kuris pardavė iš pažiūros galingus kvantinius kompiuterius tokioms įmonėms kaip „Google“ ir „Lockheed Martin“. Šie kompiuteriai veikia su 1000 kubitų, daug daugiau nei bet kuri kita technologija.

Tačiau daugelis teoretikų teigia, kad D-Wave teiginiai yra pernelyg išpūsti ir kad jos mašinos negali pagaminti beveik tokios skaičiavimo galios, kokią turėtų turėti kiti kvantiniai kompiuteriai.

Štai kodėl daugelis grupių bando komercializuoti kitas kvantines technologijas, kurios labai skiriasi tuo, kaip saugo ir apdoroja kvantinę informaciją. Jie įvairiai remiasi fotonais, elektronais, atomais, jonais ir molekulėmis, kad galėtų atlikti savo kvantinį pasiūlymą.

Iš šių metodų vienas iš seniausių ir geriausiai išvystytų yra jonų gaudyklės kvantinė kompiuterija, o Merilendo universiteto grupė yra pasaulinė lyderė šioje srityje. Iš tiesų, grupės lyderis Chrisas Monroe turi startuolį IonQ, kuris siekia komercializuoti šią technologiją.

Taigi keičiamo dydžio kvantinio kompiuterio, kuris gali įgyvendinti Groverio algoritmą, nors ir tik su trimis kubitais, demonstravimas gali būti vertinamas kaip ketinimų pareiškimas.

1998 m., pirmą kartą įgyvendinus Groverio algoritmą, buvo įvairių nuomonių apie tai, kiek laiko fizikai užtruks, kad kitą žingsnį pakeistų kompiuteriai. Nemažai startuolių tinkamai susikūrė ir žlugo remiantis optimistinėmis prognozėmis. Tačiau tuo metu 20 metų buvo pesimistiška prognozių spektro pabaiga. Tai, kad tai užtruko taip ilgai, parodo užduoties sudėtingumą.

Sunku valdyti visatą kvantine skale. Technologams ir rizikos kapitalistams dabar įdomus klausimas, ar galima žymiai paspartinti technologijų pažangą.

Nuoroda: arxiv.org/abs/1703.10535 : Užbaikite 3 Qubit Grover paiešką programuojamame kvantiniame kompiuteryje

paslėpti