Jeżeli na zwykłym komputerze problem ma wykładniczą złożoność obliczeniową to zmieniając komputer na kwantowy zmniejszamy złożoność problemu do wielomianowej.
Jak na komputerze kwantowym spada złożoność problemów które na zwykłym mają złożoność n! lub nawet n^n?
To jest bzdura co piszesz. Komputer kwantowy WCALE (!) nie powoduje żadnego spadku złożoności obliczeniowej z wykładniczej do wielomianowej.
Polecam zapoznać sie najpierw z definicją problemów P i NP i z definicja deterministycznej i niedeterministycznej maszyny turinga...
Zwykły komputer to deterministyczna maszyna turinga, a komputer kwantowy to maszyna niedeterministyczna.
Problemy klasy NP są rozwiazywalne w czasie wielomianowym (!) na niedeterministycznej maszynie, ale można ich rozwiązanie symulować na maszynie deterministycznej jednak kosztem wykładniczej złożoności.
Ale zysk z przeniesienia problemu P na maszynę niedeterministyczną jest raczej złudny i w większości przypadków w ogóle nie występuje.
Maszynę niedeterministyczną możesz sobie intuicyjnie wyobrazić jako maszynę która potrafi odpalać sobie równolegle wiele ścieżek obliczeń. Jeśli na przykład masz gdzieś jakies "rozwidlenie" to zwykła maszyna turinga musi sprawdzić oba przypadki i przez to złożoność rośnie 2 razy, a niedeterministyczna maszyna potrafi obie ścieżki wyliczać jednocześnie. Przykładem takiej operacji jest na przykład "znalezienie optymalnego miejsca podziału ciągu liczbowego". Maszyna deterministyczna musiałaby testować wszystkie możliwe podziały (czas liniowy), a maszyna niedeterministyczna może to wykonać w czasie stałym.
W efekcie zysk z maszyny niedeterministycznej możesz uzyskać tylko jeśli w algorytmie występują kroki tego typu.
Polecam filmik, który ładnie to wyjaśnia.
To jest bzdura co piszesz. Komputer kwantowy WCALE (!) nie powoduje żadnego spadku złożoności obliczeniowej z wykładniczej do wielomianowej.
Faktycznie błędna generalizacja. chodziło mi o to:
Problemy klasy NP są rozwiazywalne w czasie wielomianowym (!) na niedeterministycznej maszynie, ale można ich rozwiązanie symulować na maszynie deterministycznej jednak kosztem wykładniczej złożoności.
Patrząc na to od drugiej strony w tych przypadkach ów spadek następuje.
W efekcie zysk z maszyny niedeterministycznej możesz uzyskać tylko jeśli w algorytmie występują kroki tego typu.
Czy w tym specyficznym przypadku złożoność spadałaby z n! do n!1/2 czy n!/n2 ?
Maszynę niedeterministyczną możesz sobie intuicyjnie wyobrazić jako maszynę która potrafi odpalać sobie równolegle wiele ścieżek obliczeń.
Z tym, że tylko jedną mogę sprawdzić, bo jak sprawdzam wynik, to określam stan(czy kot żyje czy nie) i qubity "zmieniają się"(superpozycja przestaje istnieć) w normalne bity.
Jak bredzę, to napisz czego nie rozumiem.
Z tym, że tylko jedną mogę sprawdzić, bo jak sprawdzam wynik, to określam stan(czy kot żyje czy nie) i qubity "zmieniają się"(superpozycja przestaje istnieć) w normalne bity.
tak :) Zauważ ze przykładowy krok który opisywałem ma taką własność - mamy wiele "potencjalnych ścieżek" ale interesuje nas tylko jeden wynik, dla tej najlepszej.
Możemy sobie na NMT wykonywać krok typu "zgadnij cośtam" co normalnie wymaga przeglądania wielu przypadków, ale nie możemy zrobić czegoś w stylu "wylicz i zwróć wszystkie ścieżki" w czasie O(1) ;)
Niedeterminizm maszyny turinga polega właśnie na tym, że będąc w jakimś stanie możemy "zgadnąć" co powinniśmy zrobić w następnym kroku.