Czy komputer kwantowy złamie prawa fizyki?

Komputer kwantowy firmy IonQ
Firma IonQ pokazała obecnie najbardziej wydajny na świecie komputer kwantowy

Komputer kwantowy posiadający n elementów potrafi zapamiętać i w jednym cyklu przetworzyć 2n informacji. Nie jak zwykły komputer tylko od 4 do 128 bitów naraz, a więc dzięki niemu policzymy miliony razy szybciej.

Maszyna Turinga – problemy nierozwiązywalne

Wiara w możliwości komputera bywa złudna. Już w 1936 roku Alan Turing podał w słynnym artykule problem arytmetyczny, którego żaden komputer nie jest w stanie policzyć.

Alan Turing

Alan Turing w latach 30. XX wieku – Źródło Wikipedia

Szczerze mówiąc to był jedyny cel tego artykułu. Turing chciał udowodnić, że istnieją problemy matematyczne, których matematyka nie jest w stanie rozstrzygnąć. Komputer, a ściślej jego matematyczny model, powstał tu jedynie jako narzędzie mające wykazać nierozstrzygalność. To znaczy, że nie da się stworzyć żadnej systematycznej metody obliczeniowej dla pewnego problemu, który wymyślił Turing. Od tego czasu tzw. problemów nierozstrzygalnych namnożyło się wiele, co wcale nie znaczy, że już zupełnie nie da się ich “ugryźć”, ale wymaga to wielu zabiegów, których efekt nie zawsze jest pewny. A ten “uboczny produkt” pracy, matematyczny model komputera, zyskał w literaturze miano “Maszyny Turinga”.

 

Schemat maszyny Turinga

Schemat maszyny Turinga – Źródło EDUX

Po dziś dzień każdy szanujący się student informatyki musi ją dobrze znać .
Maszyna Turinga dysponuje nieskończoną taśmą, na której głowica może zapisywać i z której odczytywać różne symbole przesuwając taśmę w przód lub w tył. O tym co maszyna robi z taśmą decyduje tablica przejść na podstawie aktualnego stanu maszyny i symbolu pod głowicą. Tablica przejść zmienia też stan maszyny. Pomimo, że Maszyna   Turinga różni się zarówno od współczesnego sprzętu komputerowego jak też bardzo już rozwiniętych jezyków programowania to ten teoretyczny model jest równoważny każdemu dawnemu i współczesnemu komputerowi z wyjątkiem … komputera kwantowego.

 

Złożoność obliczeniowa czyli klasyfikacja trudności problemów 

Po wielu latach od tego odkrycia zaczęto badać wydajność programów komputerowych i algorytmów (czyli ich abstrakcyjnych wzorców). Okazało się, że dobrym wskaźnikiem wydajności jest wzór uzależniający czas obliczeń od wielkości danych wprowadzanych do programu. Najszybsze programy liczyły z czasem oznaczanym jako O(n) – co oznaczało, że czas obliczeń zależał liniowo od wielkości danych. Ale już na przykład prymitywne metody porządkowania danych (tzw. sortowanie) wymagały czasu obliczeń rzędu O(n2) – czyli n do kwadratu. Metody bardziej wyszukane natomiast działały w czasie zależnym przeciętnie od funkcji O(n·log(n)) – a więc funkcji o pośredniej między liniową, a kwadratową złożoności. Są oczywiście również funkcje szybciej rosnące, ogólnie określane mianem wielomianowych. Jeśli jednak zmienna powędruje do wykładnika (np. O(2n)) to mamy do czynienia z funkcją wykładniczą o diametralnie różnych od wielomianowych własnościach.

Złożoność obliczeniowa - wielomianowa kontra wykładnicza

Zasadnicza różnica pomiędzy spokojną złożonością wielomianową, a ostro w górę idącą wykładniczą

Funkcje wykładnicze (zielone na wykresie) rosną bowiem tak szybko, że duże problemy wymagałyby na ich rozwiązanie wieków, gdy dla funkcji wielomianowej (żółte i niebieskie na wykresie) przy tym samym n to zaledwie sekundy. Mamy oczywiście na myśli jakieś większe, o praktycznym znaczeniu wielkości n. W trakcie badań okazało się, że nie wszystkie problemy są z gruntu skazane na algorytmy wykładnicze. Są też takie problemy, dla których nie da się tego udowodnić, ale nie znaleziono też jak dotąd algorytmu wielomianowego. Te problemy zaliczamy do klasy NP-zupełnych, gdyż są one ze sobą powiązane algorytmami przekształcającymi dane jednego problemu w drugi. Gdyby więc udało się znaleźć algorytm wielomianowy dla choćby jednego problemu z tej klasy to i pozostałe dałoby się rozwiązać w czasie wielomianowo-zależnym od rozmiaru problemu. Jednak nadzieje na takie rozstrzygnięcie są coraz mniejsze, bo było już tyle zakończonych niepowodzeniem prób znalezienia takich algorytmów.

Komputer kwantowy – pogromca złożoności wykładniczej?

Efektywne rozwiązywanie problemów NP-zupełnych na klasycznych komputerach zdaje się być przesądzone negatywnie. Natomiast komputery kwantowe dają zupełnie nowe możliwości. Przykładowo weźmy trudny problem badania czy dana liczba jest pierwszą (albo próby znajdowania jej wszytkich możliwych podzielników). Gdy liczba badana ma wartość x wymaga danych o wielkości n=log10x (t o jest tylu znaków wymaga zapisanie liczby o wartości x), dla których należy wykonać x operacji dzielenia (przez każdą z liczb od 2 do x-2), a więc jak wynika ze wzoru z logarytmem x= 10n operacji. Dla tego właśnie problemu znaleziono algorytm działający na komputerze kwantowym znajdujący podzielniki w czasie ograniczonym wielomianem.

Można zadać pytanie skąd taki zaskakujący wynik? Otóż komputer kwantowy wykonuje obliczenia nie na bitach a na qbitach. Każdy qbit może nie jak bit przechowywać albo 0 albo 1 lecz przechowuje informację o tym w jakiej części to jest 0 a w jakiej 1. Ważne jest przy tym powiązanie z innymi qbitami danej maszyny. Mając n qbitów komputer kwantowy może przechowywać jednocześnie 2n wektorów stanów bitów o długości n. I tak na przykład dla n=3 będą to maksymalnie: 0-0-0, 0-0-1, 0-1-0, 0-1-1, 1-0-0, 1-0-1, 1-1-0 oraz 1-1-1. I co ciekawe w jednym cyklu wykonywać przetwarzanie wszystkich tych wektorów naraz. Przy większych ilościach qbitów daje to olbrzymie przyspieszenie obliczeń.

Komputer kwantowy – wciąż niedoskonały

Richard Feynman

Richard Feynman – Źródło Wikipedia
Paine Mansion Woods 1984 copyright Tamiko Thiel


Richard Feynman

Na koniec trzeba wyraźnie sobie powiedzieć, że współczesne próbne komputery kwantowe mają wiele wad uniemożliwiających efektywne ich wykorzystanie w zadaniach praktycznych. Np. działania wielu elementów komputera obarczone jest błędami statystycznymi, których eliminacja do rozsądnego poziomu wymaga powtarzania obliczeń. Trudne jest też odczytywanie wyników obliczeń, bowiem takie próby powodują zniszczenie całego zbioru wyników i sprowadzenie ich do jednego z wielu wyznaczonych.

Jeden wielkich fizyków XX wieku Richard Feynman rzucił kiedyś luźną uwagę  na temat niemożności śledzenia przemian kwantowych zwykłymi komputerami. Przeistoczyła się ona najpierw w namacalne dowody wskazujące na możliwość pokonania tej niedoskonałości zwykłych komputerów, a potem wiele nowatorskich konstrukcji komputerów kwantowych zdolnych tego dokonać.

W końcu w pracy [11] zaproponowano Kwantową Maszynę Turinga, która miała lepiej oddawać naturę obliczeń na tych nowych urządzeniach.

Bibliografia

  1. Alan Turing: On computable numbers, with an application to entscheidungs problem, 1936.
  2. Garey, M. R.; Johnson, D. S., Victor Klee, ed. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences, San Francisco, Calif.: W. H. Freeman and Co., 1979.
  3. Jacek Błażewicz Złożoność obliczeniowa problemów kombinatorycznych, Wydaw. Nauk.-Techn., Warszawa, 1988.
  4. Andrew Hodges, Wiktor Bartol: Enigma: życie i śmierć Alana Turinga, Warszawa: Prószyński i S-ka, 2002.
  5. Paweł Maretycz Wielki sukces IBM – komputer kwantowy firmy bije kolejne rekordy NEWSY ,, 05-02-2021.
  6. Firma Ion pokazała najbardziej wydajny na świecie komputer kwantowy
  7. Google potwierdza supremację kwantową. 10 tys. lat obliczeń w 200 sekund,  https://dzienniknaukowy.pl/nowe-technologie/google-potwierdza-supremacje-kwantowa-10-tys-lat-obliczen-w-200-sekund
  8. IBM ogłasza kwantowy przełom
  9. Jak kwantowość zmieni przyszłość
  10. Inne trudne obliczeniowo problemy rozwiązywane przez współczesną informatykę jeszcze bez komputerów kwantowych
  11. David Deutsch “The fabric of reality”, Penguin Books, 1997, Hrmondsworth, Middlesex, England.

 

Możesz również polubić…

7 komentarzy

  1. Paweł Perekietka pisze:

    Dziękuję za kolejny ciekawy artykuł, który może zrozumieć uczeń czy uczennica szkoły średniej.

    W akapicie o sprawdzaniu pierwszości liczby tacy uczniowie znajdą precyzyjne matematyczne uzasadnienie, że algorytm znany im ze szkoły (test pierwszości liczby) wcale efektywny nie jest, również ten, który szuka dzielników nie do x/2 a do pierwiastka z x!

  2. Paweł pisze:

    We fragmencie “przez każdą z liczb od 2 do x-2” zamiast “x-2” powinno być “x/2”, prawda?

    • Andrzej P. Urbański pisze:

      To do pewnego stopnia nieistotne, bo chodziło mi o pokazanie, że ilość dzieleń zależy od x. Oczywiście, że x/2 to o połowę mniej operacji, chociaż jeszcze lepiej zoptymalizowana granica to pierwiastek kwadratowy z x. (tak naprawdę tej złożonej wielkości na liczbach rzeczywistych nie trzeba wyliczać, bo wystarczy, że obliczając p=x/d poczynając od d=2 po +1 w górę stwierdzimy, że p < d, a więc dalej dzielniki byłyby symetryczne).

  3. www.xmc.pl pisze:

    Fajnego masz bloga i ciekawe na nim treści czy na serwerze wszystko sie zmieści ? pięknie frazujesz słowa zmuszasz przy tym do myślenia tym komentarzem życzę powodzenia 🙂

  1. 10 czerwca 2022

    […] musimy brać pod uwagę możliwości najnowszej generacji komputerów zwanych kwantowymi, które to zawrotne tempo rozwoju informatyki jeszcze podkręcą. Mimo wszystko jednak nadal musimy do rozwiązywania problemów z użyciem komputerów podchodzić […]

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.

The maximum upload file size: 5 MB. You can upload: image, audio, video, document, spreadsheet, interactive, text, archive, code, other. Links to YouTube, Facebook, Twitter and other services inserted in the comment text will be automatically embedded. Drop file here