Login lub e-mail Hasło   

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.
Wyświetlenia: 20.820 Zamieszczono 25/02/2011

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.

Podobne artykuły


10
komentarze: 9 | wyświetlenia: 1914
108
komentarze: 32 | wyświetlenia: 55744
53
komentarze: 68 | wyświetlenia: 29234
53
komentarze: 55 | wyświetlenia: 30246
49
komentarze: 27 | wyświetlenia: 60736
48
komentarze: 18 | wyświetlenia: 62659
36
komentarze: 29 | wyświetlenia: 26163
35
komentarze: 9 | wyświetlenia: 26128
34
komentarze: 36 | wyświetlenia: 19424
33
komentarze: 76 | wyświetlenia: 11010
33
komentarze: 22 | wyświetlenia: 24997
31
komentarze: 12 | wyświetlenia: 24590
 
Autor
Artykuł

Powiązane tematy





  ykes,  27/02/2011

Dodam ciekawostkę wyczytaną bodaj w Focusie. Otóż komputer złożony z 500 kubitów może mieć moc obliczeniową porównywalną z komputerem, zbudowanym z procesorów w ilości odpowiadającej liczbie atomów we Wszechświecie (szacunkowo 10^80).

Takie szacunki są trochę ryzykowne, ale stosując podany przeze mnie wzór 2^n można wyliczyć ile stanów jednocześnie może maksymalnie przechowywać 500 qbitowy komputer tj. 2^500=(2^10)^50=(10^3)^50=10^150 a więc nawet większą wartość, ale trzeba ją znacznie pomniejszyć dla porównania z jakimś procesorem.

Naprawdę mi się podobało, gratuluję :)

Dziękuję. Jestem mile zaskoczony, że również informatyczce przed dyplomem spodobały się moje mocno popularno-naukowe zapiski. :)

  gibro,  03/03/2011

niech Polacy zrobią komputer to wtedy prawa będą się łamać

niestety ale wraz z wiekiem nasi rodacy są zbyt leniwi...

Nie chcę polemizować z tezą o lenistwie Polaków, zwłaszcza podobno potęgującym się z wiekiem, ale zrobienie czegoś takiego wymaga ogromnych nakładów na badania i dobrze rozwiniętej technologii, a tego w Polsce brakuje.

Fajny artykuł. A ostatni wpis jeszcze lepszy

Polacy pierwszy swój komputer zrobili już w 1958 roku!
Jeśli idzie o myśl techniczną to nie było z nami źle, gorzej z organizacją produkcji, która w gospodarce niedoborów musiała kuleć.
Wiadomo, że wielu polskich naukowców interesuje się komputerami kwantowymi, ale na razie brakuje tu wielkich osiągnięć.

Dla ścisłości (a może rzetelności) trzeba dodać, że nie znany jest obecnie (nawet czysto teoretycznie) żaden algorytm dla problemu NP-zupełnego na komputer kwantowy i może się okazać, że takowy nie istnieje. Wyszukiwanie elementu w zbiorze ma złożoność O(n^1/2), a były nadzieje na dużo lepszy wynik...

Algorytm Shora http://pl.wikipedia.org/wiki/A(...)m_Shora rozwiązuje problem, który opisałem tj. rozkładu liczby na czynniki pierwsze (FAKTORYZACJI) w czasie wielomianowym O((log N)3).

FAKTORYZACJA jest na "bieżący stan wiedzy" problemem klasy NP o złożoności średniej około O(n*e^(n^1/3)) - tyle daje średnio najszybszy znany algoryt

...  wyświetl więcej

Problem faktoryzacji nie jest NP-zupełny (rozkładając liczbę na czynniki nie da się rozwiązać np. problemu komiwojażera ang. TSP), a na "bieżący stan wiedzy" tak naprawdę nie wiadomo czy jest NP (złożoność najlepszego znanego algorytmu nie jest tożsama z dowodem). Tak samo "na bieżący stan wiedzy" nie wiadomo czy komputer kwantowy jest w stanie rozwiązać problem o którym na pewno wiadomo, że jest ...  wyświetl więcej

Jeśli problem faktoryzacji nie jest NP to znaczy, że komputer kwantowy potrafi rozwiązać problem trudniejszy niż NP-zupełny, a więc nie ma powodu wątpić, że poradzi sobie również z innymi problemami trudnymi obliczeniowo. Algorytm Shora dowodzi, że komputer kwantowy radzi sobie z trudnymi problemami obliczeniowymi i powstaje tylko pytanie o jaką ich klasę chodzi.

Przeprowadzono już wiele e

...  wyświetl więcej

Z przykrością muszę stwierdzić, że błędnie używa Pan bardzo precyzyjnych matematycznych pojęć, których nie rozumie. Faktoryzacja jest łatwiejsza niż NP (bo być może jest P). Problemy NP-zupełne to podzbiór NP o bardzo ciekawej właściowości, że można jeden sprowadzić do drugiego, czyli rozwiązując jeden z nich rozwiązujemy wszystkie. Inne problemy NP mogą być jeszcze trudniejsze. Klasyfikacja probl ...  wyświetl więcej

Niestety to pan wyraża się mocno nieprecyzyjnie, gdyż do klasy NP należą również wszystkie problemy klasy P. Proszę sobie sprawdzić w podręcznikach. Zwłaszcza schemat, w którym klasa P jest narysowana w NP. W ten sposób pisząc, że faktoryzacja nie wiadomo czy należy do NP sugerował pan, że problem może należeć do szerszej klasy, którym nie wystarcza czas wielomianowy na niedeterministycznej maszyn ...  wyświetl więcej

Mea culpa, przepraszam. Faktycznie NP zawiera P, pisząc NP chodziło mi o problemy NP trudne, których na dzień dzisiejszy komputerem kwantowym nie da się ugryźć. Znaczy to mniej więcej tyle, że na polu złożoności obliczeniowej nic się nie zmieniło oprócz faktoryzacji. Być może lepsze efekty uzyskalibyśmy budując komputery chemiczne lub biologiczne, zamiast inwestować w zabawkę, która może nigdy nie będzie potrafiła więcej niż rozłożyć liczbę pierwszą na czynniki.

Cieszę, że się wyjaśniło:) i w ogóle dziękuję za ciekawą dyskusję:)
W pełni rozumiem wątpliwości i próby pohamowania mnie przed zbytnim optymizmem.
Jednak rozmawiamy o przyszłości, która jeszcze dla nikogo nie jest znana i prawie każde przypuszczenie jest równoprawne.
Fascynującą cechą techniki kwantowej jest to, że do przechowywania danych obliczeniowych sięgamy po gigantyczn ...  wyświetl więcej

Niestety właśnie w splątaniu stanów cząstek może leżeć problem z komputerami kwantowymi.
Polscy naukowcy odkryli że z powodu zaszumienia stanu układu, splątania może już nie dać się wydobyć.
http://www.polskieradio.pl/23/(...)stnieja
Zaś proste podniesienie dwójki do potę ...  wyświetl więcej

"dla których nalezy wykonać x operacji dzielenia(przez każdą z liczb od 2 do x-2)"

Czemu x-2? Powinno chyba być do pierwiastka z x.

Zgadza się, ale to już wynika ze znajomości nieco sprytniejszego algortmu. Poza tym przekształcenie byłoby ciut mniej przejrzyste, a wynik w swej istocie taki sam, a więc postaci O(k^n), a mnie tu chodziło tylko o tę wykładniczość wyniku.

  nse,  04/03/2011

"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."

Czy mam rozumieć że z przetwarzania cyfrowego przechodzimy na przetwarzanie analogowe ?

Nie.To nie jest również probabilistyka. Dalej to jest wyjaśnione, że każdy qbit wiąże się z postałymi qbitami maszyny w wektory, w których może przyjmować zarówno wartości 0 jak i 1. Więc trudno ocenić jaka jest jego wartość w danym momencie.

  nse,  05/03/2011

Mam rozumieć że to wszystko to założenia teoretyczne ?
Z tego co zrozumiałem jeden qbit został rozbity na cyfrę 0 do 8 ? i jest traktowany jak do tej pory jeden bit czyli z jednej magistrali równoległej przykładowo 32bitowej wychodzi wyjdzie 96 bitowa w 32 połączeniach ? Tak z ciekawości pytam , bo nie jestem pewny czy dobrze rozumie ?

Troszkę inaczej! Przedstawiłem przykład komputera 3 qubitowego. Każdy qubit może pomieścić tylko 0 albo 1 ale może być ich naraz więcej. Przykładowo dla 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. Pierwszy qubit będzie w sumie gromadził 4 zera i 4 jedynki, ale każde z nich będzie powiązane z zerami i jedynkami z pozostałych qbitów tworząc wymienione wektory. Oczywiście w jakimś sta ...  wyświetl więcej

  nse,  05/03/2011

W sensie obliczeniowym tak na mój prosty rozum , to myślę że głownie chodzi o wielkość kawałka jaki maszyna przetwarza w tym samym czasie , dotychczasowe procesory przetwarzają liczby 2 łączone dając większe liczby ... , przykładowo 2^32 , zaś według koncepcji którą zrozumiałem była by przetwarzana liczba 8^32 ... Proszę wybaczyć dziwne pytania , ja staram sobie to jakoś uzmysłowić w bardziej jada ...  wyświetl więcej

Może nie odchodźmy od mojego przykładu. Tam komputer kwantowy jednocześnie w 3 qubitach potrafił przetworzyć: 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. Natomiast tradycyjny procesor trzybitowy tylko trzy bity. Gdy liczba qubitów wzrasta ta przestrzeń rośnie w gigantycznym tempie.

  nse,  05/03/2011

Czyli przetwarzamy liczby ósemkowe w gigantycznym tempie taktowania ?
Więc jaka jest różnica miedzy bitem , a qbitem ?

W jednym takcie! Układy elektroniczne są w miarę zwyczajne, muszą tylko spełniac regułę odracalności obliczeń i to wystacza by z naszego przykładu wszystkie trzybitowe wektory przetworzyły się w jednym takcie. One wszystkie "upakują się" też w pojedynczych komórkach pamięci. Wszystko to za sprawą tego, że wektory wykorzystują przestrzeń fizyki kwantowej.

  nse,  05/03/2011

Czyli czas i energia potrzebna do wykorzystania podczas zapisu i odczytu pamięci się minimalizują dzięki fizyce kwantowej ?

Układy z odwracalnością obliczeń powodują, że nie jest potrzebna dodatkowa energia na każdy z przetwarzanych wektorów, a więc nawet przy olbrzymiej ilości równolegle przetwarzanych danych będzie cały czas niewielka. Ponieważ dane przetwarzane są jednocześnie nie trzeba nic manipulować z czasem.

  nse,  05/03/2011

Coś w rodzaju maszyny Turinga z olbrzymie szeroką taśmą ? Tyko że nie rozumie jak taki komputer może złamać prawa matematyczne ?

Może to dobry pomysł by taśma w maszynie Turinga była nieskończenie szeroka i wszystkie znaki w jednym rządku przetwarzane jednocześnie. "Złamanie praw" może się tylko tak wydawać jeśli nie uwzględnimy nowych możliwości fizycznych. Dotychczas wszystkie komputery odpowiadały matematycznie Maszynie Turinga. Wydaje sie, że komputer kwantowy rządzi się innymi prawami. Pewnie niebawem dowiemy się jak to dokładnie wygląda.

  nse,  05/03/2011

Może z liczenia arytmetycznego przyjdzie przejść na liczenie wektorowe ? ... tylko to nie maszyna złamie reguły matematyczne to my dla tej maszyny będziemy musieli nieco wzbogacić własne umiejętności liczenia ?

Istnieje coś takiego ja paradoks EP

Nazwa pochodzi od nazwisk trzech fizyków: Einsteina, Podoskyeg i Rosena. Fizycy ci zaproponowali pewien eksperyment myślowy w celu wykazania niekompletności mechaniki kwantowej, lansowanej przez Bohra. Eksperyment ten został opisany we wspólnie wydanej w 1935 pracy pod tytułem: „Can Quantum Mechanical Description of Physical Reality Be Considered Complet

...  wyświetl więcej

Tytuł " Komputer kwantowy złamie prawa matematyczne? " jest bardziej prowokacją niż prawdą. Prawa fizyki i matematyki są w przeciwieństwie do praw teologicznych niezmienne.

  nse,  05/03/2011

Może pod tą prowokacją mieści się konieczność większego sprecyzowania dotychczasowych praw ?

To prowokacja! Zachęta by się zapoznać z artykułem.
Ale też fascynacja niezwykłymi możliwościami komputera kwantowego.
Wszystkie twierdzenia teorii obliczeń powstały w oparciu o Maszynę Turinga.
To wydaje się być nowym modelem obliczeń, którego relacje z MT nie są proste.

Qbity z jednej strony pozwalają niejako równolegle wykonywać obliczenia, ale nie można ich odczytać ani skopiować w trakcie wykonywania obliczeń, co jest dużą ułomnością w stosunku do zwykłych bitów i czyni wymyślanie algorytmu niezwykle trudnym. Nie można też porównywać równoległości obliczeń na qbitach z wielordzeniowym procesorem, gdyż różne rdzenie mogą wykonywać różne zadania, a zrównoleglone obliczenia to identyczne operacje.

Prowokacja w dobrym znaczeniu tego słowa. Zachęcam do podobnych artykułów. Ja na pewno będę ich wiernym czytelnikiem panie Andrzeju. Pozdrowienia.

W takim razie zapraszam do zapoznania się z innymi moimi artykułami w tym serwisie. Najbardziej zbliżony poznawczo wydaje mi się artykuł http://eiba.pl/8n traktujący o osiągnięciach i przyszłości sterowania wprost myślą: zabawki, komunikatora, pojazdu i ... serwisu społecznosciowego.

Proszę spojrzeć:
http://technologie.gazeta.pl/i(...)ny.html

Jednak w komentarzach pod artykułem zdania są podzielone co do tego, czy to prawda.

Firma D-Wave już wcześniej "prezentowała" komputer kwantowy z 16 Qbitami, w czasie prezentacji nie pokazali jednak faktoryzacji, tylko klasyczne problemy. Póki co nic się nie zmieniło, jedynie naklejka z liczbą Qbitów na obudowie ;).

  Amadeusz  (www),  08/06/2011

nie dojdziemy do tego do póki nie przetestujemy :D

  juicypen  (www),  19/12/2011

Wielu ludzi przecenia możliwości komputerów kwantowych, a prawda jest taka, że komputer kwantowy będzie miał zastosowanie POMOCNICZE dla komputerów klasycznych. Komputery kwantowe, których notabene jeszcze nie ma, są tworzone z myślą o rozwiązywaniu pewnej klasy problemów, np. faktoryzacja dużych liczb (Algorytm Shora), co może być wykorzystane w algorytmach asymetrycznych, czy przeszukiwanie bazy ...  wyświetl więcej

To mi przypomina "prognozę" dyrektora IBM z początku lat pięćdziesiątych, który oszacował zapotrzebowanie na komputery na ... kilka sztuk. Wtedy też można było oceniać, że komputer będzie miał zastosowanie POMOCNICZE, bo wyobrażano sobie, że komputer będzie wyłącznie wykonywał obliczenia arytmetyczne, a takich zastosowań nie było znów tak wiele. Wcześniej prognozując zastosowanie radia widziano je ...  wyświetl więcej

  carpin  (www),  01/10/2013

Patrzcie jak to się czasy zmieniają. Pamiętam jak się bawiłem w programowanie na Commodore 64 i Atari. Programowanie w Basicu. Nie wiem jaką to miało moc obliczeniową, ale obliczenie 2x3 trochę mu zajmowało. Teraz PCty, a co będzie następne, eh.

@carpin: Lepiej to o czym piszesz oddaje inny mój artykuł http://eiba.pl/4 który dotyczy postępu w zakresie tej tradycyjnej informatyki. Informatyka kwantowa to wciąż wiele pytań i niejasnych odpowiedzi. Takie lata 30-te XX wieku w informatyce, a więc tuż przed elektronicznymi komputerami.

Pytanie czemu jeszcze takiego nie zbudowana np: dla potrzeb NASA lub Google ?

@www.optima-md.com: Jedni i drudzy już kupili taką maszynę kanadyjską d-WAVE http://www.spidersweb.pl/2014/(...)wo.html ale jak widać to wyboista droga, co świadczy tylko o tym, ze nie umiemy jeszcze takiego komputera zbudować albo efektywnie użyć. Może moje wnuki się tym zajmą, a ja mam nadzieję, że będą i że zechcą zajmować się informatyką :)

  rookers  (www),  14/01/2017

Takie komputery są już w użyciu, wystarczy trochę czasu poświęcić aby dotrzeć do odpowiednich źródeł na ten temat

@rookers: O!!! Znowu komentarz:) Dzięki:) Artykulik jest sprzed prawie sześciu laty. Zresztą i w nim i w komentarzach jest trochę o aktualnych konstrukcjach komputerów kwantowych. Jednak trzeba dodać, że z jakichś względów nie są to aż tak efektywne jak sugeruję w artykule konstrukcje. Na prawdziwy przełom przyjdzie jeszcze pewnie poczekać.



Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2017 grupa EIOBA. Wrocław, Polska