Obliczenia kwantowe mają teraz potężne narzędzie wyszukiwania

Algorytm Grovera

W 1996 roku informatyk Lov Grover z Bell Labs w New Jersey ujawnił niezwykły algorytm przeszukiwania bazy danych. Algorytmy wyszukiwania należą do najważniejszych w informatyce. Umożliwiają wykonywanie przyziemnych zadań, takich jak polowanie w książkach telefonicznych, ale także bardziej egzotycznych zadań, takich jak łamanie kodów kryptograficznych. Ten rodzaj algorytmu jest wszechobecny w informatyce.

Tak więc każdy sposób na przyspieszenie zadania ma ogromne znaczenie. Wyszukiwanie standardowe zajmuje czas, który jest w przybliżeniu proporcjonalny do liczby elementów w wyszukiwaniu. Dzieje się tak, ponieważ w najgorszym przypadku algorytm musi przeszukać wszystkie elementy, aby znaleźć tylko jeden.

Ale algorytm Grovera jest inny. Czas potrzebny jest proporcjonalny do pierwiastka kwadratowego liczby elementów. Informatycy nazywają to przyspieszeniem kwadratowym. A w świecie, w którym wzrost prędkości o kilka ułamków procenta jest niezwykle cenny, przyspieszenie kwadratowe jest ogromnym osiągnięciem.

Sztuczka Grovera polegała na wykorzystaniu dziwnych, ale potężnych pomysłów mechaniki kwantowej. W świecie klasycznym bity to tylko zera i jedynki. Ale w świecie kwantowym pojedynczy bit kwantowy lub kubit może być jednocześnie 0 i 1. Fizycy twierdzą, że kubit jest w superpozycji stanów.

Kluczem jest superpozycja. W tym stanie algorytm może przeszukiwać zarówno 0, jak i 1 w tym samym momencie. Ponieważ może przeszukiwać więcej niż jeden element jednocześnie, algorytm kwantowy może przeszukiwać listę znacznie szybciej niż algorytm ograniczony tempem klasycznej fizyki.

Algorytmy kwantowe muszą być zaimplementowane przez komputer kwantowy, aw 1996 roku, kiedy Grover wykonywał swoją pracę, były to tylko odległe marzenia. Ale przełom nastąpił szybko. Fizycy zademonstrowali pierwszy prymitywny komputer kwantowy w 1998 roku i pokazali, jak może wykonać algorytm Grovera w tym samym roku.

Ale ta konkretna forma obliczeń kwantowych była bardzo ograniczona. Działał na kilku kubitach, ale nie więcej i, nawet w zasadzie, nigdy nie można go było skalować do większych obliczeń. Ten problem budowania i demonstrowania skalowalnych komputerów kwantowych od tamtej pory nęka dyscyplinę.

Teraz, około 20 lat później, fizycy zaczynają budować komputery kwantowe, które mają potencjał skalowania, a tym samym są zdolne do potężniejszych obliczeń. A dzisiaj Caroline Figgatt i koledzy z University of Maryland twierdzą, że po raz pierwszy wykonali algorytm Grovera na skalowalnym komputerze kwantowym.

Prace pokazują szybkie przyspieszenie obliczeń kwantowych i torują drogę do bardziej ambitnych prac z algorytmem, który może rozpocząć rozwiązywanie rzeczywistych wyzwań, takich jak łamanie kodu.

Komputer kwantowy, z którym współpracuje Figgatt, składa się z łańcucha pięciu jonów iterbu zawieszonych w polu elektromagnetycznym. Każdy jon jest jak maleńki magnes, który można skierować w górę lub w dół i przerzucić z jednego stanu do drugiego za pomocą lasera. W ten sposób każdy jon może przechowywać informacje: na przykład 1 oznacza rozkręcenie, a 0 oznacza rozkręcenie. A ponieważ są to obiekty kwantowe, jony mogą istnieć w superpozycji tych stanów.

Jony oddziałują również ze sobą poprzez siły odpychające związane z ich ładunkiem dodatnim. Ta interakcja pozwala jednemu kubitowi na interakcję z innym kubitem w celu przetwarzania informacji. To jest istota obliczeń kwantowych. Kolejność kroków w tym obliczeniu to algorytm kwantowy, w tym przypadku algorytm Grovera.

Figgatt i spółka wykorzystują swój system do stworzenia trzykubitowego komputera kwantowego, który może przechowywać do ośmiu elementów w bazie danych. Następnie wykonują algorytm Grovera, aby pokazać, że możliwe jest znalezienie przedmiotu średnio znacznie szybciej niż klasyczny komputer, który wymagałby co najmniej ośmiu bitów. Raportujemy wyniki dla kompletnego algorytmu wyszukiwania Grover z trzema kubitami przy użyciu skalowalnej technologii obliczeń kwantowych uwięzionych jonów atomowych, o wydajności lepszej niż klasyczna, mówią Figgatt i spółka.

To ciekawa praca o dużym potencjale. Zdaniem zespołu toruje to drogę do szerszego wykorzystania algorytmu wyszukiwania Grovera w rozwiązywaniu większych problemów na komputerach kwantowych, w tym wykorzystania obwodu jako podprogramu dla innych algorytmów kwantowych.

Ale praca dostarcza również ciekawego wglądu w wyścig do budowy potężnych komputerów kwantowych. Zwycięzca tego wyścigu prawdopodobnie zbierze ogromne nagrody finansowe, ale nikt nie jest do końca pewien, która technologia jest najlepsza.

Ten świat został zamieszany przez kanadyjski startup o nazwie D-Wave Systems, który sprzedał pozornie potężne komputery kwantowe firmom takim jak Google i Lockheed Martin. Te komputery działają z 1000 kubitów, znacznie więcej niż jakakolwiek inna technologia.

Ale wielu teoretyków twierdzi, że twierdzenia D-Wave są przesadzone i że jej maszyny nie są w stanie wyprodukować nawet takiej mocy obliczeniowej, do jakiej powinny być zdolne inne komputery kwantowe.

Dlatego wiele grup próbuje skomercjalizować inne technologie kwantowe, które znacznie różnią się sposobem przechowywania i przetwarzania informacji kwantowych. Różnorodnie polegają one na fotonach, elektronach, atomach, jonach i cząsteczkach, które wykonują swoje kwantowe licytacje.

Spośród tych technik jedną z najstarszych i najlepiej rozwiniętych są obliczenia kwantowe z pułapką jonową, a grupa z University of Maryland jest światowym liderem w tej dziedzinie. Rzeczywiście, lider grupy, Chris Monroe, ma startup o nazwie IonQ, który ma na celu komercjalizację tej technologii.

Tak więc demonstracja skalowalnego komputera kwantowego, który może zaimplementować algorytm Grovera, choć tylko z trzema kubitami, może być postrzegana jako deklaracja intencji.

W 1998 roku, po pierwszym wdrożeniu algorytmu Grovera, pojawiły się różne opinie na temat tego, ile czasu zajmie fizykom stworzenie skalowalnych komputerów w kolejnym kroku. Szereg startupów powstało i upadło w oparciu o optymistyczne prognozy. Ale w tym czasie 20 lat znajdowało się na pesymistycznym krańcu spektrum przewidywań. Fakt, że trwało to tak długo, pozwala spojrzeć na trudność zadania z innej perspektywy.

Kontrolowanie wszechświata w skali kwantowej jest trudne. Interesującym pytaniem dla technologów i inwestorów venture capital jest to, czy tempo postępu technologicznego można znacznie przyspieszyć.

Nr ref.: arxiv.org/abs/1703.10535 : Pełne wyszukiwanie 3-Qubit Grover na programowalnym komputerze kwantowym

ukryć