Komputer kwantowy złamie prawa matematyczne?

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

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ć.
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(n^2) - 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ówniez funkcje szybciej rosnące, ogólnie okreslane mianem wielomianowych. Jeśli jednak zmienna powędruje do wykładnika (np. O(2^n)) 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ą tez 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 dla choćby jednego problemu z tej klasy to i pozostałe dałoby się rozwiązać.
O ile efektywne rozwiązywania tych problemów na klasycznych komputerach zdaje się być przesądzone negatywnie to komputery kwantowe daja zupełnie nowe możliwości. Przykładowo dla trudnego problemu badania czy dana liczba jest pierwszą(albo znajdowania jej podzielników), który gdy liczba badana ma wartość x wymaga danych o wielkości n=log10(x), dla których nalezy wykonać x operacji dzielenia(przez każdą z liczb od 2 do x-2), a więc x= 10^n 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  maszyna może przechowywać jednocześnie 2^n 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ń.
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 zadanich praktycznych. Np. działania wielu elemntó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 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.

Autor  Andrzej P Urbański

Artykuł pobrano ze strony www.eioba.pl