NSA buduje komputer kwantowy

[KopalniaWiedzy.pl 357]

W ramach projektu "Penetrating Hard Targets" NSA buduje "kryptologicznie użyteczny komputer kwantowy". The Washington Post, powołując się na dokumenty udostępnione przez Edwarda Snowdena twierdzi, że na wspomniany projekt przeznaczono 79,7 miliona dolarów. Budowa kwantowego komputera zdolnego do złamania niemal każdego szyfru to tylko jedna z części projektu.

Eksperci od dawna zastanawiają się, czy NSA nie jest bliższa zbudowania kwantowego komputera niż ktokolwiek inny. Jednak z ujawnionych przez Snowdena dokumentów wynika podobno, że Agencja nie prowadzi bardziej zaawansowanych prac. Wydaje się mało prawdopodobne, by NSA w jakimś znaczącym stopniu wyprzedzała resztę świata i zdołała utrzymać to w tajemnicy - mówi profesor Scott Aaronson z MIT-u. Podobno sama NSA uważa, że idzie łeb w łeb z laboratoriami finansowanymi przez UE czy rząd Szwajcarii. Nikt jednak nie jest bliski jakiegoś znaczącego przełomu. Z takim poglądem zgadza się profesor Seth Lloyd, specjalista ds. mechaniki kwantowej z MIT-u.

NSA pracuje nad kwantowym komputerem nie tylko dlatego, że chce podsłuchiwać innych, ale również dlatego, iż obawia się, że sama może zostać podsłuchana jeśli ktoś wybuduje kwantowy komputer szybciej. W jednym z ujawnionych przez Snowdena dokumentów czytamy, że zastosowanie technologii kwantowych do tworzenia algorytmów wpłynie dramatycznie zarówno ma możliwość ochrony tajemnic rządowych USA jak i na możliwość śledzenia komunikacji innych rządów.

Jeszcze przed 10 laty mówiono, że pierwszy duży komputer kwantowy może powstać w ciągu 10-100 lat, przed pięcioma laty eksperci zaczęli twierdzić, iż na taką maszynę trzeba będzie poczekać około 20 lat.

Kanadyjska firma D-Wave Systems od 2009 roku chwali się, że wyprodukowała komputer kwantowy. W 2011 roku jedną z takich maszyn kupił Lockheed Martin,  a w 2012 roku sprzedała taką maszynę Google'owi, NASA i Universities Space Research Association, które założyły Kwantowe Laboratorium Sztucznej Inteligencji.

Jednak, jak zauważa profesor Matthew Green z Uniwersytetu Johnsa Hopkinsa, nawet jeśli wszystko, co mówią o swoim komputerze jest prawdziwe, to nie można na nim uruchomić algorytmu Shora. W 1994 roku Peter Shor z Bell Laboratories zaprezentował kwantowy algorytm rozkładu wielkich liczb na liczby pierwsze. Rozłożenie szyfru, czyli liczby naturalnej składającej się z wielu cyfr, na liczby pierwsze, oznacza jego złamanie. Shor wykazał, że komputery kwantowe - w przeciwieństwie do komputerów tradycyjnych - byłyby w stanie błyskawicznie dokonać takiej operacji. Maszyna D-Wave nie była budowana z myślą o uruchomieniu na niej algorytmu Shora, zatem nie nadaje się do łamania szyfrów.

Jeśli chcielibyśmy porównać zaawansowanie prac nad kwantowym komputerem do komputera tradycyjnego, należałoby stwierdzić, że ludzkość nie wynalazła jeszcze abakusa. Z dokumentów NSA wynika, że Agencja miała nadzieję, iż do września 2013 roku uda jej się kontrolować dwa kwantowe bity (kubity). Do łamania szyfrów potrzebne zaś będą setki lub tysiące kubitów.

« powrót do artykułu

[Jarek Duda 138]

Te 20 lat brzmią dość optymistycznie ... co do D-Wave, to sprowadza się tutaj problem do szukania minimum Hamiltonianu (Shor jest bardziej wyrafinowany), do którego próbujemy zejść w sposób adiabatyczny. Tylko że wymaga to żeby istniało pojedyncze globalne minimum energetyczne, które jest odseparowane od reszty - co dla trudnych problemów po prostu nie jest prawdą - mają one wykładniczo wiele lokalnych minimów, czyli układ czysto termicznie nie jest w stanie ich odróżnić, szczególnie że ewolucja nie jest idealnie adiabatyczna.

Chyba największy sukces D-Wave to aktualnie liczba Ramseya R(3,3):

http://physicsworld.com/cws/article/news/2013/sep/27/has-a-quantum-computer-solved-the-party-problem

... którą zwykły komputer jest w stanie znaleźć w ułamek sekundy ...

[Astroboy 34]

Obawiam się, że informatycy nazbyt frywolnie szastają terminologią fizyczną, ale niech tam. Może miast intelektualnych wygibasów, coś strawnego dla czytelników? Swoją drogą, myślę, że potrafię podać całkiem prosty hamiltonian, którego D-Wave nie ugryzie. I jeszcze - schodzenie w sposób 'adiabatyczny' niekoniecznie musi być możliwe.

[Flaku 26]

Mógłbyś mi wyjaśnić, co oznacza, że mają "wykładniczo wiele lokalnych minimów"? Słyszałem sformułowanie "wykładniczo wiele" wiele razy, zawsze jeśli tylko mam możliwość pytam o jego znaczenie, nikt jak do tej pory nie był w stanie mi precyzyjnie określić co to oznacza.

[Astroboy 34]

Flaku, z grubsza ujmując, wiele lokalnych minimów, zwłaszcza wykładniczo, oznacza ni mniej, ni więcej, że w uj kochany wiemy, o co biega.

[Jarek Duda 138]

Wykładniczo oznacza że wzrost jest typu exp(wielkośc problemu).

Podczas gdy jeśli P!=NP, na standardowych komputerach koszt rozwiązywania trudnych problemów rośnie zawsze wykładniczo z wielkością, nadzieją komputerów kwantowych jest wielomianowy wzrost - np. koszt faktoryzacji rosnący wielomianowo z ilością cyfr (Shor).

Natomiast adiabatyczne komputery kwantowe działają na innej zasadzie niż te "standardowe QC" pozwalające na algorytm Shora - one szukają minimum Hamiltonianu w sposób adiabatyczny - czyli zaczynamy od prostego Hamiltonianu dla którego łatwo mu znaleźć minimum, i powoli przełączamy do Hamiltonianu naszego problemu - zakładając że cały czas pozostajemy w jakimś minimum:

http://en.wikipedia.org/wiki/Adiabatic_theorem

... ale to ostateczne minimum wcale nie musi być tym globalnym ... i dodatkowo termodynamika wszystko psuje.

 

NP trudny problem możemy łatwo zamienić na globalną minimalizację. Np. 3SAT to pytanie czy dana koniugacja alternatyw trójek może być prawdziwa. Alternatywę dwóch zmiennych: x OR y można zamienić na zerowanie nieujemnego wielomianu:

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

analogicznie dla trójek mamy wielomian stopnia 14 (można zmniejszyć do 10). Sumując takie wielomiany dla poszczególnych trójek, oryginalny problem 3SAT jest równoważny z znalezieniem globalnego minimum tego wielomianu.

Czyli jeśli miałby tylko wielomianowo wiele lokalnych minimów, w czasie wielomianowym moglibyśmy przeszukać wszystkie, czyli P=NP ... co sugeruje że dla trudnych problemów ilość minimów rośnie wykładniczo - a więc i odległości energetyczne między nimi maleją wykładniczo, czyli dla takiego komputera adiabatycznego musielibyśmy obniżać temperaturę jak exp(- wielkość problemu).

[Astroboy 34]

Wykładniczo oznacza że wzrost jest typu exp(wielkośc problemu).

A kto to powiedział? 2^(wielkośc problemu), jak i milion^(wielkośc problemu) jest tego samego typu. Zanegujesz?

 

"nadzieją komputerów kwantowych jest wielomianowy wzrost - np. koszt faktoryzacji rosnący wielomianowo z ilością cyfr (Shor)."

A kto Ci przeczy? Ale masz jakikolwiek dowód na to, że algorytm Shore'a da się jakoś racjonalnie na istniejących komputerach kwantowych? Nie słyszałem.........

 

"Natomiast adiabatyczne komputery kwantowe działają..."

Nie ma takich komputerów. Wiesz co to jest ADIABATA? Czekam na rękawiczkę - zapewne spali się nim doleci do mnie...

 

"czyli zaczynamy od prostego Hamiltonianu dla którego łatwo mu znaleźć minimum"

Wybacz, ale nie traktuj mnie jak debila. Takie hamiltoniany w naturze to zdecydowana RZADKOŚĆ. Wiem, że zaczynacie od ZERA. DODAJECIE jedynkę... ALE, wybacz, to nazbyt MAŁO. I nie uderzajcie takim niczym w RZECZYWISTOŚĆ.

 

"NP trudny problem możemy łatwo zamienić na globalną minimalizację." :D:D Dostałeś już Nobla?

Może prościej - chcesz porozmawiać o grupach Galois?

 

Edit: nie mogłem się jednak powstrzymać - globalna minimalizacja? Wybacz, ale jak chcesz to zrobić w przesztrzeni, dajmy na to minimalistycznie, czterdziestowymiarowej? Komputery przyszłości, kwantowe, już się grzeją... Dalej jesteś chłodny? I myślę o szybkozmiennych funkcjach jednej, jedynej tylko zmiennej. Nadążasz?

[Jarek Duda 138]

Po pierwsze, specjalnie napisałem "typu" ext(wielkość problemu) na pytanie co to znaczy wykładniczy wzrost - oczywiście liniowo skalując wykładnik pozostajemy w wykładniczym wzroście.

 

Co do Shora to też jestem sceptyczny - gdzieś tam się udało zfaktoryzować 15 ... gdzieś tam koło 200 ... w eksperymentach dedykowanych żeby dokładnie daną faktoryzację pokazać ...

 

Co do adiabaty, to jasne historycznie kojarzy się np. z cyklem Carnota ... jednak np. od nawiązanego twierdzenia adiabatycznego (1928, Born & Fock), wkroczyła ona do mechaniki kwantowej (i jak dla mnie słusznie), prowadząc do tak nazywanych dzisiaj komputerów:

http://en.wikipedia.org/wiki/Adiabatic_quantum_computation

 

Co do "prostych Hamiltonianów" to oczywiście chodzi o idealizację, które jest podstawą mechaniki kwantowej i takowych komputerów.

Osobiście wierzę że jest to efektywna reprezentacja jakiejś głębszej dynamiki, np. jak kropelkach Coudera:

 

Nie wiem co tu mają do rzeczy grupy Galois, ale transformację 3SAT do globalnej minimalizacji nieujemnego wielomianu podałem w celu pokazania problemu tego typu podejść: wykładniczy wzrost ilości lokalnych minimów.

[Flaku 26]

Być może nie jestem jakiś kształcony, ale z tego co zauważam, to uznajesz, że jeśli problem rośnie szybciej niż wielomianowo, to znaczy, że rośnie wykładniczo. Czy to nie lekkie nadużycie? Skąd wiemy, że nie rośnie jak (e^x)/lnx, albo e^(x^x)

[Astroboy 34]

oczywiście liniowo skalując wykładnik pozostajemy w wykładniczym wzroście.

 

Ja podałem zmianę podstawy, nie wykładnika. Wszak (C+x)^x nie jest wykładnicze...

 

"Co do adiabaty, to jasne historycznie kojarzy się np. z cyklem Carnota"

Niekoniecznie. Ale owszem, masz poniekąd rację. Z terminologią nie chce mi się walczyć.

 

"Osobiście wierzę że jest to efektywna reprezentacja jakiejś głębszej dynamiki, np. jak kropelkach Coudera:"

Osobiście podziwiam głęboką wiarę. SERIO.

 

"Nie wiem co tu mają do rzeczy grupy Galois"

Pewnie dowiesz się niedługo.

 

Flaku, szybciej niż wilomianowo, to co najmniej wykładniczo. Choć, oczywiście, matematycy mnie zglebią. e^(x^x) to znacznie szybciej, niż wykładniczo, zaś (e^x)/lnx jest dalej wykładniczy.

[Jarek Duda 138]

astroboy, zmiana podstawy jest równoważna z liniowym przeskalowaniem wykładnika.

Z adiabatą można się też spotkać np. w mechanice klasycznej Arnolda - jest to ogólnie proces na tyle powolny że odwracalny.

Co do grup Galois, to myślałem że masz na myśli opis płaszczyzn Riemanna, ale tutaj mamy rzeczywisty wielomian (bez pierwiastków).

 

Flaku, oczywiście jest nieskończenie więcej rodzajów wzrostów niż wielomianowy i eksponencjalny (jak exp(x/ln(x)) między nimi), jednak różnica między tymi dwoma jest tą kluczową tutaj.

[Astroboy 34]

Ok. Ale z adiabatą nieco się zagalopowałeś - niekoniecznie musi być odwracalna - nawet zwykle nie BYWA:

http://pl.wikipedia.org/wiki/Przemiana_adiabatyczna

(leniwy jestem, nie chce mi się teraz szukać głębiej)

Co do płaszczyzn Riemanna w tym temacie, to musiałbym doczytać, ale sądzę, że się tu różnimy.

Wielomian zawsze można przeskalować - w fizyce zwykle szukamy minimum (i kij w ucho z 'pionowym' przesunięciem, albo w rzeczy samej - miejsc zerowych - ostatnio raczej rzadko).

[Jarek Duda 138]

Co do adiabaty, oczywiście odwracalność to idealizacja: np. dla gazu doskonałego, ruchu bez tarcia czy unitarnej ewolucji - mówienie o prawdziwych procesach że są adiabatyczne jest raczej przybliżeniem ... tak przynajmniej byłem uczony, ale to oczywiście dyskusja o nomenklaturę.

Co do płaszczyzn Riemanna (surface, nie mylić z manifold), to są te dwuwymiarowe rozmaitości w analizie zespolonej wynikłe z tego że np. pierwiastki zespolone stopnia k mają k rozwiązań, logarytm nieskończoność - opisuje się je przy pomocy grup Galois (np. Forster) ... ale jak powiedziałem - tutaj wystarczy skupić się na rzeczywistych wielomianach (choć może metody geometrii algebraicznej mogą być tutaj użyteczne).

[Astroboy 34]

Co do płaszczyzn Riemanna (surface, nie mylić z manifold), to są te dwuwymiarowe rozmaitości w analizie zespolonej wynikłe z tego że np. pierwiastki zespolone stopnia k mają k rozwiązań, logarytm nieskończoność - opisuje się je przy pomocy grup Galois ... ale jak powiedziałem - tutaj wystarczy skupić się na rzeczywistych wielomianach (choć może metody geometrii algebraicznej mogą być tutaj użyteczne).

 

No widzisz, rozmaitość różniczkową (manifold) jakoś rozróżniam, ale wychodzi Ci jakieś masło maślane.

Co do adiabaty - nie idealizuj. Chcesz mówić o RZECZYWISTOŚCI, czy o zerach? Dyskusja o RZECZYWISTOŚCI nie jest dyskusją o nomenklaturze.

 

Edit: w opisie rzeczywistych rzeczy uwzględnia się właśnie poprawki 'nieadiabatyczne' - co zwykle jest ogromnym problemem numerycznym - ale o adiabacie nikt chyba już nie myśli inaczej, jak o 'punkcie startu' dla modeli numerycznych...

[Jarek Duda 138]

http://en.wikipedia.org/wiki/Riemann_surface surface się używa na rozmaitość dwuwymiarową, variety na algebraiczną.

Jak na razie nie mamy lepszej fizyki niż przybliżanie rzeczywistości - idealizacja. Ważne że działa, ważne żeby być świadomym słabości danych przybliżeń ... i ważne żeby szukać lepszych.

Pozdrawiam

[Astroboy 34]

"In mathematics, particularly in complex analysis, a Riemann surface, first studied by and named after Bernhard Riemann, is a one-dimensional complex manifold."

No to sobie zaprzeczyłeś. Pozdrawiam.

[Jarek Duda 138]

"One-dimensional compex" oznacza dwuwymiarową manifold (gdzie liczy się wymiary rzeczywiste).

[Astroboy 34]

Ale ja nie protestuję - zwyczajnie wcześniej powiedziałeś: "Co do płaszczyzn Riemanna (surface, nie mylić z manifold)".

Możesz się do tego odnieść?

[Jarek Duda 138]

Ehh, nie mam siły, weź sobie jakiś podstawowy podręcznik ... płaszczyzna/surface to specjalny przypadek rozmaitości/manifold - mająca dwa wymiary rzeczywiste. Z Riemannem jest trochę namieszane, bo jego manifold to zupełnie coś innego niż surface - używają jej raczej fizycy na rozmaitości o dodatniej sygnaturze (w przeciwieństwie do Minkowskiego) ... matematycy raczej rzadko używają rozmaitości o niedodatniej sygnaturze (choć chodziłem na jeden taki wykład).

Pozdrawiam

[Astroboy 34]

Ehhh, takich podstawowych podręczników u nas Ci dostatek. Ale każdy jakoś uczy po polsku. Sygnatura to już mi wygięła twarz. Słyszałeś może o krzywiźnie?

[Jarek Duda 138]

Sygnatura to np. różnica między wymiarem przestrzennym i czasowym w STW ...

[Astroboy 34]

No to mówisz po polsku o interwale...

Choć wiem, że interwał nie jest starosłowiański.

[Jarek Duda 138]

Interwał to ds^2=dt^2 - (dx^2+dy^2+dz^2) w rozmaitości Minkowskiego.

Natomiast sygnatura to to że tam ma być ten minusik ... w rozmaitości Riemanna byłyby same plusy.

[Astroboy 34]

No to nie gubisz może pojęcia metryki?

[Jarek Duda 138]

Sygnatura to jeden z wielu "parametrów" metryki http://en.wikipedia.org/wiki/Metric_signature