Kvantu skaitļošanai tagad ir jaudīgs meklēšanas rīks

Grovera algoritms

Tālajā 1996. gadā datorzinātnieks Lovs Grovers no Bell Labs Ņūdžersijā atklāja neparastu algoritmu meklēšanai datu bāzē. Meklēšanas algoritmi ir vieni no svarīgākajiem datorzinātnēs. Tie ļauj veikt ikdienišķus uzdevumus, piemēram, medības, izmantojot tālruņu grāmatas, kā arī eksotiskākus uzdevumus, piemēram, kriptogrāfisko kodu uzlaušanu. Šāda veida algoritms ir visuresošs datorzinātnēs.

Tāpēc jebkurš veids, kā paātrināt uzdevumu, ir ļoti nozīmīgs. Standarta meklēšana aizņem laika posmu, kas ir aptuveni proporcionāls meklēšanas elementu skaitam. Tas ir tāpēc, ka sliktākajā gadījumā algoritmam ir jāmeklē visi elementi, lai atrastu tikai vienu.

Bet Grovera algoritms ir atšķirīgs. Laiks, kas nepieciešams, ir proporcionāls elementu skaita kvadrātsaknei. Datorzinātnieki to sauc par kvadrātveida paātrinājumu. Un pasaulē, kur ātruma palielināšana par dažām procenta daļām ir ļoti vērtīga, kvadrātiskais paātrinājums ir milzīgs sasniegums.

Grovera triks bija izmantot dīvainās, bet spēcīgas idejas aiz kvantu mehānikas. Klasiskajā pasaulē biti ir tikai 0 un 1. Bet kvantu pasaulē viens kvantu bits jeb kubits var būt 0 un 1 vienlaikus. Fiziķi saka, ka kubīts atrodas stāvokļu superpozīcijā.

Superpozīcija ir galvenais. Šajā stāvoklī algoritms var meklēt gan 0, gan 1 vienā un tajā pašā mirklī. Tā kā kvantu algoritms var meklēt vairāk nekā vienu elementu vienlaikus, tas var meklēt sarakstā daudz ātrāk nekā algoritms, ko ierobežo klasiskās fizikas straujais temps.

Kvantu algoritmi jārealizē ar kvantu datoru, un 1996. gadā, kad Grovers veica savu darbu, tas bija tikai tāls sapnis. Taču izrāviens nāca ātri. Fiziķi 1998. gadā demonstrēja pirmo primitīvo kvantu datoru un parādīja, kā tajā pašā gadā tas var izpildīt Grovera algoritmu.

Bet šis konkrētais kvantu skaitļošanas veids bija ārkārtīgi ierobežots. Tas darbojās ar dažiem kubitiem, bet ne vairāk, un pat principā to nekad nevarēja palielināt līdz lielākiem aprēķiniem. Šī mērogojamu kvantu datoru izveides un demonstrēšanas problēma kopš tā laika ir nomocījusi šo disciplīnu.

Tagad, apmēram 20 gadus vēlāk, fiziķi sāk veidot kvantu datorus, kuriem ir potenciāls mērogot un tādējādi veikt jaudīgākus aprēķinus. Un šodien Kerolaina Figata un draugi no Merilendas universitātes saka, ka viņi pirmo reizi ir izpildījuši Grovera algoritmu mērogojamā kvantu datorā.

Darbs demonstrē kvantu aprēķinu straujo paātrinājumu un paver ceļu vērienīgākam darbam ar algoritmu, kas varētu sākt risināt reālās pasaules problēmas, piemēram, koda laušanu.

Kvantu dators, ar kuru strādā Figgats un viņa kolēģi, sastāv no piecu iterbija jonu virknes, kas suspendēti elektromagnētiskajā laukā. Katrs jons ir kā mazs magnēts, ko var virzīt uz augšu vai uz leju un ar lāzeru pārslēgt no viena stāvokļa uz otru. Tādā veidā katrs jons var saglabāt informāciju: 1, piemēram, griešanās augšup un 0, piemēram, griešanai. Un, tā kā tie ir kvantu objekti, joni var pastāvēt šo stāvokļu superpozīcijā.

Joni arī mijiedarbojas viens ar otru, izmantojot atgrūšanas spēkus, kas saistīti ar to pozitīvo lādiņu. Šī mijiedarbība ļauj vienam kubitam mijiedarboties ar citu kubitu, lai apstrādātu informāciju. Tāda ir kvantu skaitļošanas būtība. Soļu secība šajā aprēķinā ir kvantu algoritms, šajā gadījumā Grovera algoritms.

Figgatt un co izmanto savu sistēmu, lai izveidotu trīs kubitu kvantu datoru, kas datu bāzē var saglabāt līdz astoņiem vienumiem. Pēc tam viņi izpilda Grovera algoritmu, lai parādītu, ka vienumu ir iespējams atrast vidēji daudz ātrāk nekā klasiskajam datoram, kuram būtu nepieciešami vismaz astoņi biti. Mēs ziņojam par rezultātiem pilnīgam trīs kubitu Grovera meklēšanas algoritmam, izmantojot ieslodzīto atomu jonu mērogojamo kvantu skaitļošanas tehnoloģiju ar labāku nekā klasisko veiktspēju, saka Figgatt un co.

Tas ir interesants darbs ar ievērojamu potenciālu. Tas paver ceļu plašākai Grover meklēšanas algoritma izmantošanai, risinot lielākas problēmas kvantu datoros, tostarp izmantojot ķēdi kā apakšprogrammu citiem kvantu algoritmiem, saka komanda.

Taču darbs sniedz arī interesantu ieskatu sacīkstēs, lai izveidotu jaudīgus kvantu datorus. Šo sacensību uzvarētājs, visticamāk, iegūs milzīgus finansiālus ieguvumus, taču neviens nav īsti pārliecināts, kura tehnoloģija ir labākā.

Šo pasauli ir izraisījis Kanādas jaunuzņēmums D-Wave Systems, kas ir pārdevis šķietami jaudīgus kvantu datorus tādiem uzņēmumiem kā Google un Lockheed Martin. Šie datori darbojas ar 1000 kubitiem, kas ir daudz vairāk nekā jebkura cita tehnoloģija.

Taču daudzi teorētiķi saka, ka D-Wave apgalvojumi ir pārspīlēti un ka tā iekārtas nevar radīt ne tuvu tādu skaitļošanas jaudu, kāda būtu jāspēj citiem kvantu datoriem.

Tāpēc daudzas grupas cenšas komercializēt citas kvantu tehnoloģijas, kas krasi atšķiras kvantu informācijas uzglabāšanas un apstrādes veidā. Tie dažādos veidos paļaujas uz fotoniem, elektroniem, atomiem, joniem un molekulām, lai veiktu savu kvantu soli.

No šīm metodēm viena no vecākajām un vislabāk attīstītajām ir jonu lamatas kvantu skaitļošana, un Merilendas Universitātes grupa ir pasaules līderis šajā jomā. Patiešām, grupas līderim Krisam Monro ir jaunizveidots uzņēmums IonQ, kura mērķis ir komercializēt šo tehnoloģiju.

Tātad mērogojama kvantu datora demonstrāciju, kas var īstenot Grovera algoritmu, lai gan ar tikai trim kubitiem, var uzskatīt par nodomu paziņojumu.

1998. gadā pēc Grovera algoritma pirmās ieviešanas radās dažādi viedokļi par to, cik ilgā laikā fiziķi prasīs, lai nākamo soli izveidotu mērogojamus datorus. Vairāki jaunuzņēmumi pienācīgi izveidojās un sabruka, pamatojoties uz optimistiskām prognozēm. Taču tajā laikā 20 gadi bija prognožu spektra pesimistiskajā galā. Tas, ka tas ir prasījis tik ilgu laiku, parāda uzdevuma sarežģītību.

Ir grūti kontrolēt Visumu kvantu mērogā. Tehnologiem un riska kapitālistiem šobrīd interesants jautājums ir par to, vai tehnoloģiskā progresa ātrumu var ievērojami paātrināt.

Atsauce: arxiv.org/abs/1703.10535 : Pabeidziet 3 kubitu Grover meklēšanu programmējamā kvantu datorā

paslēpties