Co pokazało D-Wave?

Kilka dni temu pisaliśmy o planowanej prezentacji Oriona - komputera kwantowego skonstruowanego przez kanadyjską firmę D-Wave. Czy faktycznie na naszych oczach dokonuje się rewolucja w informatyce?

Prezentacja na pewno nie mogła przekonać sceptyków, i pewnie tak pozostanie dopóki publikacje naukowców z D-Wave nie przejdą przez sito recenzenckie któregoś z renomowanych czasopism naukowych. Niemiłe skojarzenia może także budzić wybór konferencji prasowej jako sposobu komunikacji ze środowiskiem naukowym - ludzie z D-Wave twierdzą jednak, że wzorem dla nich jest raczej Craig Venter z Celera Genomics, a nie Fleischmann i Pons.

D-Wave zademonstrowało działanie Oriona uruchamiając na nim aplikacje rozwiązujące trzy problemy: przeszukiwania bazy danych białek, usadzenia gości przy stole weselnym oraz łamigłówkę Sudoku. Oczywiście, marne 16 qubitów nie jest w stanie zapewnić Orionowi konkurencyjności w stosunku do klasycznych komputerów... jednak D-Wave potwierdziło, że będzie się starało pod koniec 2008 roku zbudować maszynę 1024-qubitową.

Do czego może się przydać taki komputer? Celem D-Wave jest realizacja 'akceleratora kwantowego' - urządzenia podłączanego do zwykłego komputera i przyspieszającego pewne rodzaje obliczeń. Pomijając specjalistyczne zagadnienie symulacji układów kwantowych, podstawowym komercyjnym zastosowaniem akceleratora kwantowego byłoby szybkie przeszukiwanie baz danych, tu bowiem obliczenia kwantowe oferują przyspieszenie kwadratowe w stosunku do algorytmów klasycznych.

Przykładowo, wyobraźmy sobie nieuporządkowaną listę 100 nazwisk, w której trzeba znaleźć jedną konkretną osobę. W najgorszym przypadku zwykły komputer musiałby wykonać 100 operacji porównania kolejnych wpisów ze wzorcem - nie mamy bowiem żadnej wskazówki na temat pozycji, gdzie znajduje się konkretne nazwisko. Komputer kwantowy, taki jak Orion, radzi sobie w takiej sytuacji zdecydowanie lepiej - wystarczyłoby mu zaledwie 10 operacji.

Nie jest to tak naprawdę zbyt spektakulatny wynik - nie wystarcza na przykład, by rozwiązać problem komiwojażera w czasie wielomianowym. Jednak przy 'dużych' problemach nawet przyspiesznie kwadratowe robi różnicę: przykładowo, złamanie funkcji haszującej MD5 poprzez przeszukiwanie wszystkich możliwych wyników wymagałoby porównania 2¹²⁸ = 340282366920938463463374607431768211456 możliwości - rzecz niewykonalna w rozsądnym czasie. Komputer kwantowy poradziłby sobie w zaledwie 18446744073709551616 krokach.

Przywrócić bezpieczeństwo takiego systemu kryptograficznego można poprzez zwiększenie długości używanego klucza - i takie są właśnie najnowsze rekomendacje specjalistów od kryptografii. Jednak niektóre rodzaje szyfrów (w których bezpieczeństwo gwarantowane jest przez niemożność szybkiego znalezienia dzielników danej liczby, takich jak RSA) nigdy już nie będą bezpieczne, zakładając że zapowiedzi D-Wave o zwiększeniu skali systemu (oraz zapewnienia jego uniwersalności) zostaną zrealizowane.

Chociaż więc postępy w dziedzinie obliczeń kwantowych są ogromne, jeszcze przez wiele lat będziemy używać 'klasycznych' komputerów - tyle że wielordzeniowych albo wykorzystujących nanorurki węglowe zamiast krzemu.

Kilka filmików z wczorajszej konferencji D-Wave można znaleźć tutaj.