Co to jest kwantowy model obliczeniowy?

Od czasu do czasu słyszałem, jak ludzie mówią o algorytmach kwantowych oraz o stanach i możliwości rozważenia wielu możliwości naraz, ale nigdy nie udało mi się przekonać kogoś do wyjaśnienia stojącego za tym modelu obliczeniowego. Żeby było jasne, nie pytam o to, jak fizycznie zbudowane są komputery kwantowe, ale raczej, jak patrzeć na nie z obliczeniowego punktu widzenia.

Powtórzę zalecenie Martina Schwartza dotyczące Nielsen & Chaung jako standardowego odniesienia; jest też wiele innych.

Badania w tej dziedzinie preferują rozważenie jednolitych rodzin obwodów kwantowych, które (jak na ironię) są ukierunkowanymi sieciami acyklicznymi opisującymi, w jaki sposób stan jednego lub więcej rejestrów przekształca się w czasie, w sposób podobny do klasycznych obwodów boolowskich. Jeśli chcesz dowiedzieć się więcej, polecam naukę w zakresie tego modelu.

Chciałbym udzielić kilku jakościowych odpowiedzi uzupełniających odpowiedź Martina.

1. Obliczenia kwantowe w rzeczywistości nie uwzględniają „wielu możliwości naraz” - a dokładniej, niezależnie od tego, czy rozważają one rozważenie wielu możliwości naraz, jest to kwestia wyboru interpretacji mechaniki kwantowej , tj. Wyboru filozoficznego, który nie ma zależnie od zdolności lub prognoz modelu obliczeniowego. („Rozważanie wielu możliwości naraz” odpowiada „interpretacji wielu światów” QM.)
   
   Przynajmniej można powiedzieć, że komputer kwantowy rozważa wiele możliwości w tym samym czasie tylko w takim stopniu, w jakim obliczenia losowe przy użyciu monety- flips bierze pod uwagę wiele możliwości jednocześnie. To dlatego, że:

2. Stany kwantowe są uogólnieniami „zwykłych” rozkładów prawdopodobieństwa --- z pewnymi prostymi, ale ważnymi różnicami. Rozkład prawdopodobieństwa może być reprezentowany jako nieujemny wektor rzeczywisty, którego wpisy sumują się do 1: to znaczy wektor jednostkowy w normie ℓ ¹ . Obliczenia probabilistyczne muszą mapować ℓ ¹ -wektory jednoczące na inne takie wektory, a więc są one opisane przez mapy stochastyczne. Można opisać obliczenia kwantowe w podobny sposób, z wyjątkiem zastosowania ℓ ² wektorów jednoczęściowych nad restricted (nieograniczone do rzeczywistych lub nieujemnych); transformacje są przez te mapy, które zachowują ℓ ^2- normę, tj. operacje jednostkowe.
   
   Ta różnica nie jest oczywiście trywialna, ani nie wyjaśnia jeszcze, co oznaczają współczynniki wektorów stanu kwantowego . Ale może pomóc wyjaśnić, co się dzieje z przestrzeniami Hilberta i produktami tensorowymi w obliczeniach kwantowych: innymi słowy dokładnie te same rzeczy, co dzieje się w obliczeniach probabilistycznych. Przestrzeń konfiguracji losowego bitu jest wektorem w ℝ ₊ ² (gdzie are ₊ są liczbami nieujemnymi); ale ponieważ bity losowe mogą być skorelowane, łączymy przestrzenie konfiguracyjne jednego lub więcej losowych bitów, biorąc iloczyn tensora. Zatem przestrzeń konfiguracji dwóch losowych bitów to is ₊ ²  ⊗ ℝ ₊ ²  ≅ ℝ ₊ ⁴ lub w pełni ogólna przestrzeń rozkładów prawdopodobieństwa dla czterech różnych łańcuchów dwubitowych. Operację A na pierwszym z tych losowych bitów, która nie działa na drugi, reprezentuje operator A  ⊗  I ₂  . I tak dalej. Te same konstrukcje dotyczą bitów kwantowych; i możemy rozpatrywać rejestry kwantowe nad zbiorami wyróżnialnych elementów w taki sam sposób, w jaki rozważamy rozkłady prawdopodobieństwa dla takich zbiorów, ponownie używając ℓ ² -wektorowych wektorów ponad ℂ.
   
   Opis ten faktycznie opisuje „czyste” stany kwantowe - te, dla których można zasadniczo przekształcić w sposób zachowujący informacje w rozkład delta w ciągu bitowym 00 ... 0 (a ściślej podać dowolnie blisko tego w normie ℓ ² ). Oprócz losowości kwantowej (o której jeszcze nie wspomniałem nic wyraźnego), można rozważyć losowość waniliowo-wypukłą-losową odpowiadającą probabilistycznym mieszankom stanów kwantowych: są one reprezentowane przez operatory gęstości , które mogą być reprezentowane przez dodatnie określone macierze ze śladem 1 (ponownie uogólniając „klasyczne” rozkłady prawdopodobieństwa, które mogą być reprezentowane przez specjalny przypadek dodatnich macierzy diagonalnych ze śladem 1).
   
   Ważne jest w tym, że chociaż stany kwantowe są często opisywane jako „wykładniczo duże”, dzieje się tak, ponieważ są one zwykle opisywane przy użyciu tych samych struktur matematycznych, co rozkłady prawdopodobieństwa; dlaczego rozkłady prawdopodobieństwa nie są opisywane jako „wykładniczo duże” w ten sam sposób, jest niejasne (ale ostatecznie nieistotne). Trudność w symulacji stanów kwantowych wynika z tego faktu, wraz z faktem, że złożone współczynniki tych ℓ ^2- rozkładów (lub złożone warunki nie-diagonalne operatorów gęstości, jeśli wolisz) mogą anulować w sposób, którego prawdopodobieństwa nie mogą , co utrudnia oszacowanie ich.

3. Splątanie to kolejna forma korelacji. W przypadku obliczeń probabilistycznych np. Łańcuchów boolowskich, jedyne „czyste” stany (które mogą być odwzorowane przez transformacje zachowujące informacje do rozkładu piku delta na 000 ... 0) są „standardową podstawą” rozkładów piku delta na różne łańcuchy boolowskie. Zatem ta podstawa ℝ ₊ ^{2 n}jest wyróżniony. Ale, o ile możemy powiedzieć, nie ma tak wyodrębnionej podstawy w mechanice kwantowej - jest to najbardziej zrozumiałe dla bitów kwantowych (spójrz na spin 1/2 cząstek, jeśli chcesz wiedzieć, dlaczego). W konsekwencji zachodzi więcej transformacji zachowujących informacje niż tylko permutacje: w rzeczywistości ich ciągła grupa. Pozwala to potencjalnym komputerom kwantowym przekształcać stany w sposób, który nie jest możliwy dla komputerów probabilistycznych, potencjalnie uzyskując asymptotyczną przewagę nad nimi.
   
   Ale co z splątaniem, które wielu ludzi uważa za tajemnicze i twierdzi, że jest przyczyną przyspieszenia komputerów kwantowych w porównaniu z klasycznymi? „Splątanie” tutaj jest tak naprawdę tylko formą korelacji: tak jak dwie zmienne losowe są skorelowane, jeśli ich rozkład jest wypukłą kombinacją więcej niż jednego rozkładu produktu (z różnymi marginesami na każdej zmiennej), dwie „zmienne kwantowe” są splątane, jeśli ich rozkład jest kombinacją liniową (z jednostką ℓ ²-norm) dwóch prawidłowych dystrybucji produktów; jest to ta sama koncepcja w ramach innej normy i odgrywa podobną rolę w zadaniach komunikacyjnych. (Na przykład: „teleportacja kwantowa” w komunikacji kwantowej odpowiada klasycznemu kodowaniu i dekodowaniu wiadomości za pomocą jednorazowego pada.) Jest to forma korelacji, która jest bardziej ogólna niż tylko klasycznie skorelowane bity; ale jedynym sposobem na wykazanie tego jest to, że korelacje zakodowane w stanie splątanym dotyczą więcej niż jednej uprzywilejowanej podstawy . Mówiąc w pewnym sensie, uwikłanie jest konsekwencją braku uprzywilejowanej podstawy.
   
   Ludzie lubią powoływać się na splątanie jako kluczowy element obliczeń kwantowych, ale to po prostu nie wydaje się utrzymywać wody: istnieją wyniki wskazujące, żesplątanie nie jest ilościowo ważne, aby algorytm Shora uwzględniał duże liczby całkowite, i że w rzeczywistości układ kwantowy może mieć zbyt duży splątanie, aby był przydatny do obliczeń. W rzeczywistości wszędzie, gdzie jestem świadomy tego, że splątanie odgrywa ważną rolę w protokole kwantowym, jest zasadniczo komunikacją (w przypadku której oczekuje się, że korelacje odegrają ważną rolę w przypadku protokołu klasycznego).

W tym momencie zaczynam brodzić w domenie osobistej opinii, więc zatrzymam się tutaj. Ale miejmy nadzieję, że te uwagi mogą de-mistifikować niektóre z niejasnych aspektów obliczeń kwantowych i sposobu ich opisu.

Lance Fortnow napisał artykuł wyjaśniający obliczenia kwantowe bez korzystania z mechaniki kwantowej. Przedstawia to zasadniczo w ten sam sposób, w jaki przedstawia się obliczenia probabilistyczne. Podejrzewam, że może to być szybszy punkt wyjścia niż coś takiego jak Nielson i Chuang (choć zgadzam się, że jeśli naprawdę chcesz się tym zająć, to Nielson i Chung zdecydowanie powinni znaleźć się na twojej liście czytelniczej).

L. Fortnow. Pogląd jednego z teoretyków złożoności na temat obliczeń kwantowych. Theoretical Computer Science, 292 (3): 597-610, 2003. Specjalne wydanie artykułów zaprezentowanych podczas drugiego warsztatu na temat algorytmów przetwarzania informacji kwantowej.

No cóż, standardowy tekst to Obliczenia kwantowe i Informacje kwantowe Nielsena i Chuanga. Obejmuje wiele różnych aspektów na rozsądnym poziomie. Prawie wszyscy pracujący w terenie mają kopię tego na swojej półce. Książka Kaye, Laflamme i Mosca jest również dobra, ale obejmuje mniej (choć nieco więcej uwagi poświęcono algorytmom).

Chociaż jest całkiem możliwe wyjaśnienie obliczeń kwantowych bez wchodzenia w mechanikę kwantową, nie sądzę, że jest to koniecznie dobry sposób na podejście do nauki obliczeń kwantowych. Znajomość teorii fizycznej wymaga intuicji, ponieważ wiele nowszych modeli obliczeń kwantowych (tj. Modele adiabatyczne, topologiczne i oparte na pomiarach) ma większą motywację fizyczną niż kwantowa maszyna Turinga lub model obwodu.

To powiedziawszy, mechanika kwantowa wymagana do zrozumienia obliczeń kwantowych jest dość prosta i dość dobrze opisana w Nielsen i Chuang. Naprawdę możesz poczuć się dobrze, czytając odpowiedni rozdział i próbując ćwiczeń. Jest to rodzaj rzeczy, którą można zrozumieć po kilku dniach pracy. Moja rada nie polega jednak na tym, aby nie pisać standardowego tekstu wprowadzającego do mechaniki kwantowej. Podejście do modelowania atomów, cząsteczek i materiałów wykorzystuje systemy o nieskończonych wymiarach i zajmuje o wiele więcej wysiłku, aby je opanować. W przypadku informacji kwantowej znacznie lepiej zacząć patrzeć na skończone systemy wymiarowe. Tradycyjnie problemy badane przez fizyków polegają zwykle na znajdowaniu stanów podstawowych i zachowaniach w stanie ustalonym, i to właśnie obejmie większość tekstów wprowadzających (począwszy od niezależnego od czasu równania falowego Schroingerera). W przypadku obliczeń kwantowych jesteśmy bardziej zainteresowani ewolucją systemów w czasie, i jest to bardziej zwięźle przedstawione w tekstach obliczeń kwantowych niż w ogólnych tekstach wprowadzających do mechaniki kwantowej (które z definicji są bardziej ogólne).

$BQP$

$|\phi\rangle$$\cal{H_2}$$\cal{H_2} \otimes ... \otimes \cal{H_2}$$|\psi\rangle$$U$$square$

Bardziej szczegółowe wprowadzenie można znaleźć w standardowym podręczniku Nielsen i Chuang.

Najpierw musisz zrozumieć fizykę kwantową.

Kilka rekomendacji:

1. „ Obliczenia kwantowe dla informatyków ” Nosona S. Yanofsky'ego i Mirco A. Mannucciego
2. „Wprowadzenie do obliczeń kwantowych” Phillipa Kaye, Raymonda Laflamme i Michele Mosca

A po bardziej zabawnej stronie: „Skrót w czasie: ścieżka do komputera kwantowego” George'a Johnsona.

Miłe wprowadzenie można znaleźć w artykule „Wprowadzenie do obliczeń kwantowych dla niefizycznych” autorstwa Eleanor Rieffel i Wolfganga Polaka. Jest może nieco stary, ale nadal jest dobrym, krótkim, samodzielnym wprowadzeniem do tematu: http://arxiv.org/abs/quant-ph/9809016

Kolejny artykuł, o wiele bardziej streszczony, to „Obliczenia kwantowe Pablo Arrighiego wyjaśnione mojej matce” na stronie http://arxiv.org/abs/quant-ph/0305045

Prawdopodobnie już o tym wiesz, ale na swoim blogu Scott Aaronson ma linki do wielu swoich wykładów dotyczących informatyki kwantowej, a także linki do starterów QC innych (przewiń w dół pasek po prawej stronie, aby je znaleźć) .

Jeśli chcesz mieć krótkie książki, ale coś delikatniejszego niż tekst taki jak Nielsen i Chuang, poleciłbym Quantum Computing dla informatyków Yanofsky'ego i Mannucciego. Spędzają sporo czasu, analizując matematyczne warunki wstępne, zanim zanurzą się w samą QC. Jeśli masz solidne podstawy matematyczne, ta książka może wydawać się zbyt prosta, ale uważam ją za bardzo przydatną.

Ogólnie rzecz biorąc, poparłbym radę Joe. Ale dla szybkiego wprowadzenia umieściłem teksty Lance'a Fortnowa i Stephena Fennera na liście czytelników informatyków zajmujących się kwantem.

Jeśli jesteś dość zaawansowany, możesz zacząć od ankiety de Wolfa-Druckera dotyczącej metod kwantowych dla klasycznych problemów. To dobry sposób na zrozumienie technik kwantowych , zanim dojdziesz do problemów kwantowych .

Nie sądzę, że musisz nauczyć się mechaniki kwantowej. Zależy to jednak od tego, w którym obszarze chcesz pracować. Istnieją dziedziny, które naprawdę potrzebują wiedzy na temat mechaniki kwantowej, jednak na przykład obszar, nad którym pracuję, teoria typów i rachunek lambda, nie potrzebuję tego, mogę to zrobić, znając tylko niektóre modele obliczeniowe.

Oprócz swojego standardowego tekstu z Chuangiem Michael Nielsen ma również serię wykładów wideo na Youtube zatytułowanych Quantum Computing for the Determined, które jak dotąd dają przegląd modelu obliczeniowego. Filmy są bardzo łatwe do obejrzenia dla każdego, kto nie rozumie informatyki i algebry liniowej.