Dlaczego i jak komputer kwantowy jest szybszy niż zwykły komputer?

Obecnie czytam książkę (i wiele Wikipedii) na temat fizyki kwantowej i jeszcze nie zrozumiałem, w jaki sposób komputer kwantowy może być szybszy niż komputery, które mamy dzisiaj.

W jaki sposób komputer kwantowy może rozwiązać problem w czasie wykładniczym, który klasyczny komputer może rozwiązać tylko w czasie wykładniczym?

Sam komputer kwantowy nie jest szybszy. Zamiast tego ma inny model obliczeń . W tym modelu istnieją algorytmy dla niektórych (nie wszystkich!) Problemów, które są asymptotycznie szybsze niż najszybsze możliwe (lub najszybsze znane, dla niektórych problemów) algorytmy klasyczne.

Polecam lekturę The Limits of Quantum autorstwa Scotta Aaronsona: jest to krótki popularny artykuł wyjaśniający, czego możemy oczekiwać od komputerów kwantowych.

$2^n$

jest to otwarty problem podlegający najnowocześniejszym badaniom, czy algorytmy kwantowe będą kiedykolwiek szybsze niż algorytmy „klasyczne” zarówno na poziomie teoretycznym, jak i stosowanym. w teorii złożoności znajduje to odzwierciedlenie w pytaniu np. BQP =? P tj. Czy klasa „P” obliczeń kwantowych jest równoważna klasycznej klasie P (czas wielomianowy) i istnieje wiele innych powiązanych pytań otwartych.

istnieje jeden bardzo intrygujący i znaczący punkt danych: wielokrotnie nagradzany algorytm Shorsa uwzględnia liczby w czasie kwantowym P, ale nadal nie wiadomo, czy istnieje klasyczny algorytm faktoringu w czasie P.

nowym kierunkiem w ciągu ostatnich kilku lat są prace nad adiabatycznym obliczeniem kwantowym, które jest łatwiejsze do wdrożenia / inżynierii niż inne standardowe metody obejmujące transport qbit (ale wciąż niezwykle trudne do wdrożenia).

jedynym komputerem (-ami) kwantowym, jaki do tej pory zbudowano, są systemy Dwave i jest obecnie przedmiotem intensywnej analizy naukowej i kontrowersji dotyczących jego rzeczywistych efektów kwantowych i wydajności; jest bardzo drogi i w zasadzie nie przewyższa komputera stacjonarnego, gdy klasyczny kod jest w pełni zoptymalizowany (ludzki / ręczny). jednak można uczciwie stwierdzić, że jak dotąd żaden inny podmiot badawczy korporacyjny, rządowy lub uniwersytecki nie jest w pobliżu swojego zaawansowania technicznego / technicznego / inżynierskiego.

naukowej perspektywy jest mętny w tej chwili i niektórzy eksperci naukowy / krytycy / sceptycy np Dyakonov dawna wierzył / twierdzą stanowczo, że skalowalne komputery QM będzie nigdy do skutku z powodu nie do pokonania trudności technicznych i / lub bariery.

Mam dowód, że nawet moc kwantowa ma swoje granice.

Komputery kwantowe mają trudności z dotarciem nawet do kilobitów qbitów. Ale nawet jeśli się tam dostaną, jest to dość potężne.

16384 qbity stworzyłoby 128 wymiarów przestrzeni na 128 kroków czasu, pełne wyczerpujące wyszukiwanie, to niesamowite, drzewo prawdopodobieństwa 100 kroku czasu 100 wymiarów !!! ale nie oczekuj więcej w tej kwocie w najbliższej przyszłości.

Układ kwantowy to układ, który istnieje w stanie (stanach) kwantowym przy różnych prawdopodobieństwach określonych przez ograniczenia środowiskowe. Zakładając, że komputer kwantowy zawiera wszystkie stany n-bitowego układu kwantowego, ekstrakcja jednego z tych stanów powoduje zapadnięcie układu do jednego ze stanów. Jest to podobne do funkcji skrótu używającej O (1) do wyszukiwania segmentu bez iteracji. Potrzebne są dwie rzeczy: pamięć kwantowa systemów n-bitowych i funkcja przypominająca skrót, aby zwinąć potrzebny stan. Więzy odgrywają rolę różnych funkcji haszujących dla zwijania systemu n-bitowego do pożądanego stanu.

Pomyśl o tym w ten sposób: Istnieją problemy, które można rozwiązać, rozwiązując wiele pojedynczych przypadków (na przykład: faktoring według podziału na próby). Problemy te wymagają długiego czasu do rozwiązania, jeśli trzeba rozwiązać pod-przypadki jedna po drugiej. Można je rozwiązać znacznie szybciej, jeśli można zapewnić wystarczającą ilość sprzętu do równoległego rozwiązania wszystkich podelementów, ale nie jest to praktyczne, ponieważ ilość potrzebnego sprzętu wzrasta wraz z rozmiarem problemu. Obliczenia kwantowe wykorzystują funkcję superpozycji stanów Mechaniki Kwantowej do symulacji zapewniania wystarczającej ilości sprzętu - tj. Każdy stan w superpozycji jest „maszyną” dla jednego z pod-przypadków. Zauważ, że ta symulacja odbywa się NIE przez oprogramowanie, ale przez samą Naturę.