Czy komputer kwantowy złamie prawa matematyczne i fizyczne?

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

Komputer kwantowy posiadający n elementów(qbitów) potrafi zapamiętać i w jednym cyklu przetworzyć 2n informacji, a nie jak zwykły komputer tylko n. Tak policzymy miliony razy szybciej.

W nagłówku mojego bloga po lewej jest historyczny już ale uroczy superkomputer CRAY-1, a po prawej współczesny komputer kwantowy

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

Szczerze mówiąc to był jedyny cel tego artykułu – 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ć, ż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. A ten „uboczny produkt” pracy – matematyczny model komputera zyskał w literaturze miano „Maszyny Turinga”, którą po dziś dzień każdy szanujący się student informatyki musi dobrze znać.

Maszyna Turinga

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ło 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 rosnącej wolniej niż kwadratowa. 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.

Są to tzw. funkcje eksponencjalne, które rosną tak szybko, że problemy, które rozwiązują tylko takie algorytmy, co prawda teoretycznie dałoby się rozwiązać, ale trzeba by na to wieków. 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 eksponencjalne. Są też takie problemy, dla których nie da się tego udowodnić, ale nie znaleziono też jak dotąd algorytmu wielomianowego. Klasę tę nazwano problemami NP-zupełnymi, gdyż okazało się, że są one ze sobą powiązane i gdyby 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.

O ile efektywne rozwiązywania tych problemów na klasycznych komputerach zdaje się być przesądzone negatywnie to komputery kwantowe dają zupełnie nowe możliwości. Przykładowo dla trudnego problemu badania czy dana liczba jest pierwszą(albo próby znajdowania jej wszytkich możliwych podzielników), który gdy liczba badana ma wartość x wymaga danych o wielkości n=log10x, dla których należy wykonać x operacji dzielenia(przez każdą z liczb od 2 do x-2), a więc x= 10n operacji, znaleziono algorytm 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 np. dla n=3 będą to: 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ń.

Richard Feynman

Na koniec trzeba wyraźnie sobie powiedzieć, że współczesne próbne komputery kwantowe obarczone są wieloma wadami uniemożliwiającymi 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.

Tym niemniej luźna uwaga jednego z wielkich fizyków XX wieku Richarda Feynmana na temat niemożności śledzenia przemian kwantowych zwykłymi komputerami przeistoczyła się w namacalne dowody wskazujące na możliwość pokonania tej niedoskonałości zwykłych komputerów.

Bibliografia

  1. Alan Turing: On computable numbers, with an application to entscheidungsproblem, 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 , https://android.com.pl/news/383755-komputer-kwantowy-ibm-przyspiesza/, 05-02-2021.
  6. Firma Ion pokazała najbardziej wydajny na świecie komputer kwantowy https://www.geekweek.pl/news/2018-12-19/firma-ionq-pokazala-najbardziej-obecnie-wydajny-na-swiecie-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, https://www.rp.pl/Nowe-technologie/200919476-IBM-oglasza-kwantowy-przelom.html
  9. https://www.honeywell.com/pl/pl/news/2020/07/how-quantum-will-transform-the-future-of-5-industries

You may also like...

5 komentarzy

  1. 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).

  2. 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!

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.