Maszyna D-Wave starła się z klasycznym pecetem

[KopalniaWiedzy.pl 357]

Po raz pierwszy w historii komputer kwantowy zmierzył się z tradycyjnym pecetem. Naprzeciwko siebie stanęły maszyna kanadyjskiej firmy D-Wave oraz highendowy komputer stacjonarny.

D-Wave sprzedaje swoje komputery od 2011 roku. Krytycy twierdzą, że nie są to typowe komputery kwantowe, gdyż podczas obliczeń wykorzystują niestandardową metodę adiabatycznych obliczeń kwantowych. Początkowo nawet sama firma D-Wave przyznawała, że nie jest pewna, czy podczas obliczeń zachodzą procesy kwantowe. Jednak w marcu bieżącego roku dwa testy maszyn D-Wave pośrednio dowiodły, że pomiędzy używanymi do obliczeń kubitami zachodzi splątanie kwantowe, a zatem istnieje warunek konieczny do uznania obliczeń za kwantowe

Catherine McGeoch z Amherst College w Massachusetts, która pracuje jako konsultantka w D-Wave, we współpracy z Congiem Wangiem z Simon Fraser University, przeprowadziła eksperymenty, podczas których użyto maszyny D-Wave Two korzystającej z 439 kubitów utworzonych z nadprzewodzących pętli z niobu oraz highendowego peceta. Jako że D-Wave jest stworzony z myślą o rozwiązywaniu konkretnych problemów obliczeniowych - służy do określenia gęstości prawdopodobieństwa, czyli wybrania spośród wszystkich możliwych rozwiązań równania grupy tych najbardziej prawdopodobnych - przed obiema maszynami postawiono takie właśnie zadanie.

Każdy z komputerów miał pół sekundy na zoptymalizowanie wyników pewnego równania. Każdy poddano 100 próbom z różnymi zmiennymi. Później każdy z komputerów miał do rozwiązania jeszcze bardziej skomplikowane równanie z większa liczbą zmiennych.

D-Wave za każdym razem podał odpowiedź w ciągu pół sekundy. Tymczasem tradycyjne algorytmy potrzebowały znacznie więcej czasu na znalezienie rozwiązań równań z około 100 zmiennymi. Najszybszy z nich, CPLEX, szukał rozwiązania najbardziej skomplikowanych problemów przez pół godziny. Oznacza to, że D-Wave był 3600 razy szybszy niż highendowy pecet.
McGeoch oficjalnie przedstawi wyniki swoich badań juz w najbliższym tygodniu podczas ACM International Conference on Computing Frontiers.

Uzyskane wyniki wskazują, że niezwykłą moc komputerów kwantowych uda się wykorzystać szybciej niż sądzono. Oczywiście wciąż istnieje prawdopodobieństwo, że D-Wave nie wykorzystuje efektów kwantowych, ale w jakiś świetnie zoptymalizowany sposób przeprowadza wysoko wydajne klasyczne obliczenia. Konieczne będzie zatem powtórzenie powyższych eksperymentów.

McGeoch zauważa również, że szanse obu maszy nie były równe, gdyż komputery zoptymalizowane pod kątem konkretnych zadań zawsze będą miały przewagę nad komputerami ogólnego przeznaczenia. Jeremy O'Brien z University of Bristol uważa, że w kolejnych eksperymentach należałoby wykorzystać specjalne zbudowany na ich potrzeby klasyczny procesor zoptymalizowany pod kątem rozwiązania konkretnych problemów.

Collin Williams z D-Wave'a wierzy jednak w maszynę swojej firmy. Zwraca uwagę na różnice w sposobie przeprowadzania obliczeń. Maszyna klasyczna rozpoczyna je bardzo powoli, potem gwałtowanie przyspiesza, a następnie powoli generuje nalepsze odpowiedzi. D-Wave Two znajduje odpowiedzi niemal natychmiast. Nigdy czegoś podobnego nie widziałem w wykonaniu żadnego klasycznego algorytmu - mówi Williams.

[Arlic 4]

Czyli mówiąc prościej nie wykorzystali GPGPU na standardowym PCcie.

 

Tak czy siak i tak najważniejszy jest perf/Wat.

[pk1001100011 0]

Warto wspomnieć, że komputer kwantowy D-Wave jest nie tylko 3600 razy szybszy od Intel Xeon E5-2690 ale także 4080 razy droższy ($10kk vs $2450).

Oni porównali wielką szafę schładzaną azotem do komputera który każdy może mieć pod biurkiem w standardowej pctowej obudowie.

 

Prawdopodobnie znacznie bardziej opłaca się wynająć moc obliczeniową standardowego superkomputera niż kupować komputer D-Wave.

[Jarek Duda 139]

Równie dobrze możemy powiedzieć że komputery mechaniczne są lepsze ... np. wiele problemów dalej lepiej analizować w tunelu aerodynamicznym niż porównywalnie dokładnie liczyć z Naviera-Stokesa ...

Nic dziwnego że fizyka pozwala szybciej bezpośrednio liczyć jej własne problemy (np. dalej nie potrafimy satysfakcjonująco policzyć co się dzieje w pojedynczym protonie, co dla fizyki jest trywialne), pytanie czy możemy to zastosować do pożytecznych problemów algorytmicznych jak np. obiecywany algorytm Shora ... którego raczej nie uruchomimy na adiabatycznym komputerze kwantowym ... http://physics.stackexchange.com/questions/10496/what-can-the-d-wave-quantum-computer-do

 

Ale ogólnie wierzę że warto szukać alternatywnych podejść "podstawienia" fizyce, idealnej w rozwiązywaniu swojej teoriopolowej mechaniki Lagranżowskiej, trudnych problemów algorytmicznych do rozwiązania - na przykład myślałem o asynchronicznym komputerze z pętlą:

Weźmy jakiś problem NP-trudny, czyli szybko możemy stwierdzić czy dane wejście jest satysfakcjonujące, ale sęk w tym że jest wykładniczo wiele różnych możliwych wejść, np. mamy zaszyfrowaną wiadomość ale rozszyfrowanie tylko z poprawnym kluczem nas satysfakcjonuje - dla innych kluczy dostajemy praktycznie biały szum.

Ten weryfikator stwierdzający poprawność wejścia może być zrealizowany przez kilka warstw podstawowych bramek (bez pętli, np. przez sprowadzenie do 3SAT) - załóżmy że mamy układ elektroniczny (bez zegara!) który w taki sposób sprawdza czy dane wejście jest poprawne.

Połączmy go w pętlę w ten sposób:

 

- Jeśli wejście poprawne zwróć wejście, w przeciwnym razie zwróć wejście+1

- Podaj wyjście na wejście

 

Czyli z zegarem taki układ sprawdzałby po kolei wszystkie możliwości aż do stabilizacji w jakimś satysfakcjonującym (załóżmy że istnieje).

Ale co gdy nie ma zegara? Mamy czystą hydrodynamikę elektronów, które płyną przez pętlę i żeby zminimalizować energię powinny szukać stacjonarnego przepływu - naszego rozwiązania ... pytanie czy mogą to zrobić szybciej niż z zegarem ??? czy np. rzeka optymalizuje przepływ badając kolejne możliwości, czy może płynnie przechodzi do optymalnego przepływu ...

[Przemek Kobel 65]

Nie jestem pewien czy te bramki prawidłowo zagrają, bo one często miewają "obszar nieokreślony" między 0 a 1, więc jest szansa że na końcu dostaniemy jakiś wynik analogowy, i do tego uzależniony od wewnętrznej elektroniki bramek, a nie konstrukcji układu.

 

Co do samego sprzętu - trochę toto kojarzy mi się z antycznymi pamięciami (kiedyś były w użyciu np. rtęciowe linie opóźniające), ale w sumie to ciekawe, że kawałek blachy liczy coś kilka tysięcy razy szybciej niż najnowszy procesor pewnej znanej firmy (żart). A czy to obliczenia "klasy kwantowej" czy nie, to można wszak sprawdzić zwiększając skalę "trudnego" problemu. Jeśli obliczenia będą wydłużały się liniowo, to mamy sprzęt (co najmniej) porównywalny z kwantowym, a jeśli wykładniczo - to raczej nie.

 

-p

[Jarek Duda 139]

Trudne problemy algorytmiczne od zawsze próbujemy atakować pozostając w dyskretnym świecie zerojedynek - uciąglenie problemu, wyjście poza 0/1 np. w takim "asynchronicznym komputerze pętlowym" jest właśnie przejściem do innego królestwa matematyki/fizyki, gdzie może (ale nie musi) istnieć szybszy sposób - to jest ciężkie zadanie, ale myślę że warto je eksplorować. Szczególnie że fizyka jest idealna właśnie w ciągłych problemach jak np. minimalizacja energii - działanie takiego komputera zdecydowanie zależałoby od użytej elektroniki, pośrednich zachowań bramek, ale może istnieje też taka w której by działał ... np. błyskawicznie znajdujący klucz kryptograficzny dla zaszyfrowanej wiadomości ... ?

Zresztą taki adiabatyczny komputer kwantowy jak D-Wave też polega na ciągłej ewolucji pomiędzy klasycznymi 0 i 1 ...

 

 

Skoro fizyka jest idealna w minimalizacji energii, może da się skonstruować ciągły potencjał którego (globalna!) minimalizacja rozwiązywałaby nasz problem? I owszem ...

Problemy NP-zupełne możemy sprowadzić do 3SAT, czyli pytanie o istnienia wartościowań zmiennych, takich że wszystkie alternatywy trójek (x lub y lub z, gdzie dodatkowo zmienne mogą być zanegowane) są spełnione. Zauważmy że (x lub y) możemy sprowadzić do minimalizacji wielomianu 6 stopnia:

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

Analogicznie dla alternatywy trójki zmiennych mamy wielomian 14 stopnia (można zredukować przynajmniej do 8). Sumujemy takie nieujemne wielomiany dla wszystkich trójek z 3SAT i rozwiązanie problemu jest równoważne ze znalezieniem zera - globalnego minimum wielomianu.

Oryginalny problem wychodzi poza 0,1 do ciągłych wartości pomiędzy - mamy tu zupełnie inne narzędzia ciągłej optymalizacji globalnej.

Ta transformacja jest trochę zbyt wysoko wymiarowa żeby bezpośrednio podstawić fizyce, ale może istnieją inne sprowadzenia problemów algorytmicznych do bezpośrednio dostępnych fizyce (jak komputery kwantowe czy asynchroniczny komputer pętlowy) ... ?

[thikim 119]

Może nie jest to uczciwy pojedynek ale jest to ważny krok na drodze do komputerów kwantowych.

[Przemek Kobel 65]

Komputery asynchroniczne... Karpińskiemu się udało, kilka lat temu Amerykanom też (chociaż w obu przypadkach potem była cisza). Ogólnie jest z tym dużo kłopotów, na dzień dobry mamy choćby tzw. racing condition. Dobrze też jest odczarować sobie bramki logiczne: http://pl.wikipedia.org/wiki/Plik:TTL_npn_nand.svg

 

Mnie osobiście zawsze rozkłada ten wynalazek:

[Jarek Duda 139]

Rzeczywiście budowanie standardowych komputerów asynchronicznych przysparza wiele problemów z synchronizowaniem np. pętli ... to o czym mówię nie ma takich pętli: podstawowy układ składa się z kilku warstw bramek logicznych - bez pętli, znalezienie rozwiązania oznacza ustabilizowanie prądów. Dodatkowa zewnętrzna pętla jest tylko żeby ustawić stabilizację na szukane rozwiązania naszego problemu - w celu minimalizacji energii ta rzeka elektronów powinna przejść do stabilnego przepływu - rozwiązać nasz problem szukając wśród ciągłych wartości między 0 i 1.

 

A może zamiast takiego ciągłego szukania minimum energetycznego, moglibyśmy wykorzystać to że mechanika Lagranżowska już znalazła trajektorie (historie konfiguracji pola) minimalizujące działanie ... pytanie jak zamienić problem algorytmiczny na minimalizację działania.

Teoretycznie można by bardzo prosto - wystarczyłoby tą pętlę zamknąć nie przestrzennie tylko czasowo - gdyby dało się przesłać wyjście w przeszłość, tak żeby ten układ korzystał z niego na wejściu - wtedy w celu minimalizacji działania, fizyka powinna od razu wybrać wejście dające zgodną pętlę przyczynową - rozwiązując nasz problem.

No ale przecież nie da się przesyłać informacji wstecz w czasie ... no ale zarówno mechanika Lagranżowska jak i unitarna mechanika kwantowa są czasowo/CPT symetryczne - nie rozróżniają przeszłości i przyszłości. Więc i są potwierdzone "kwantowe" doświadczenia jak Wheelera, w którym późniejszy wybór ma wpływ na interpretację tego co działo się wcześniej ( http://en.wikipedia.org/wiki/Wheeler%27s_delayed_choice_experiment ) ... albo delayed choice quantum erasure, dla którego np. obrót polaryzatora na jednej drodze optycznej zmienia statystykę na drugiej, czyli wydaje się że zmieniając długości dróg optycznych moglibyśmy wpływać na przeszłą statystykę: http://www.thescienceforum.com/physics/27354-controlled-delayed-quantum-erasure-where-causality.html

 

Osobiście na mechanikę kwantową, jej nieintuicyjność, patrzę jako na rezultat tego że nie żyjemy w "ewoluującym 3D" jak podpowiada nasza intuicja, tylko w prawdziwej "czterowymiarowej czasoprzestrzeni", Einsteinowskim Block Universe - taka czterowymiarowa galareta: teraźniejszość jest rezultatem minimalizacji naprężenia/działania z obu stron. Asymetria jest na poziomie statystyki/termodynamiki - nie ma na nią miejsca w fundamentalnych równaniach, tylko jest rezultatem konkretnego rozwiązania w którym żyjemy - konkretnie bliskości Wielkiego Wybuchu, w którym wszystko było praktycznie w tym samym miejscu, czyli miało małą entropię, więc i wytworzyło jej gradient w który teraz żyjemy: drugą zasadę termodynamiki.

Tutaj jest wytłumaczenie siły algorytmu Shora z tej perspektywy - kluczowe jest że komputer kwantowy potrafi "zamocować" przestrzeń rozwiązań nie tylko z przeszłości (inicjalizacja) ale i z przyszłości (pomiary):

[antykwant 7]

Jarek dużo gdybania w twoim wywodzie. Jednak jeśli wierzysz w to co napisałeś to dlaczego nie rozpocząłeś działania, poszedłeś do jakiegoś profesora (jeśli sam nie jesteś) i omówiłeś swoje przypuszczenia?

[Jarek Duda 139]

To że formalizm Lagranżowski - którego używamy we wszystkich skalach: od kwantowej teorii pola do ogólnej teorii względności, mówi że fizyka już znalazła czterowymiarowe rozwiązanie (np. trajektorię, historię konfiguracji pola, kształt czasoprzestrzeni) optymalizujące działanie to nie moje wywody tylko jest znane od ponad dwóch stuleci ... ( http://en.wikipedia.org/wiki/Lagrangian_mechanics#Lagrangian_and_action )

Pytanie jak przetłumaczyć problemy algorytmiczne na minimalizację działania i podstawić fizyce - żeby się okazywało że ona już rozwiązała nasz problem (np. uzgadniając pętlę przyczynową) ... ?