Referencje na temat porównania komputerów kwantowych i maszyn Turinga

Powiedziano mi, że komputery kwantowe nie są obliczeniowo mocniejsze niż maszyny Turinga. Czy ktoś mógłby pomóc w udzieleniu referencji literaturowych wyjaśniających ten fakt?

— Mok-Kong Shen
źródło

Wygląda na to, że masz zarejestrowane konto na innych stronach Stack Exchange. Powinieneś zarejestrować swoje konto CS i powiązać je z innymi (zobacz centrum pomocy ). Między innymi pozwoli ci to uczestniczyć w czacie z CS.

— Gilles „SO- przestań być zły”

Odpowiedzi:

W rzeczywistości wszystko, co komputer kwantowy może obliczyć, może również obliczyć maszyna Turinga. (Jest to bez komentarza w ogóle od tego, jak długo trwa maszynę Turinga obliczyć funkcję w porównaniu do komputera kwantowego).

W rzeczywistości nie jest to trudne do zauważenia, pod warunkiem, że rozumiesz obliczenia kwantowe. Na przykład w przypadku obwodu kwantowego w typowym zestawie bramek wynik zależy od rozkładu prawdopodobieństwa, który jest określony przez współczynniki macierzy jednolitej. Ta jednolita matryca jest po prostu iloczynem macierzy bramek i może być obliczona - jeśli jesteś wystarczająco cierpliwy - za pomocą klasycznego komputera. Tak więc dla czystej obliczalności (w przeciwieństwie do wydajności) nie ma korzyści z używania komputerów kwantowych.

Całe wyzwanie wynikające z mechaniki kwantowej polega na ustaleniu, czy takie współczynniki można obliczyć wydajnie , co jest trudniejszym problemem niż to, czy można je w ogóle obliczyć .

— Niel de Beaudrap
źródło

Chociaż wiedza mojego początkującego mówi mi, że obwód kwantowy reprezentuje transformację macierzy Hadamarda, nie widzę jeszcze, w jaki sposób programowa możliwość wykonywania dowolnych obliczeń macierzowych na klasycznym komputerze może być substytutem fizycznego posiadania obwodu kwantowego. Na przykład moja książka mówi o generowaniu liczb losowych w następujący sposób: 1. | x> <- | 0> 2. | x> <- H | x> 3. Zmierz | x> Co w szczególności odpowiada krokowi 3 programujesz na klasycznym komputerze?

— Mok-Kong Shen

(Właściwie znormalizowana) macierz Hadamarda jest tylko jedną możliwą transformacją jednostkową. Do twoich obliczeń możemy rozpoznać, że deterministyczna maszyna Turinga może obliczyć rozkład prawdopodobieństwa (0,5, 0,5) składający się z kwadratów norm z pierwszej kolumny macierzy Hadamarda

, a dla losowej maszyny Turinga (która może wykonywać rzut monetą) możemy pójść o krok dalej i uzyskać próbkę z tego rozkładu prawdopodobieństwa. W każdym razie dowolna funkcja obliczona przez obwód kwantowy z błędem <1/2, może również klasyczna maszyna.

| ⟨ b | H | 0 ⟩ |^{2}

$\bigl|\langle b |H|0\rangle\bigr|^2$

— Niel de Beaudrap,

@ Mok-Kong Shen: jeśli z moich uwag na temat nieefektywności lub spowolnienia nie wynika jasno, powszechnie uważa się, że komputery kwantowe mają większą moc obliczeniową w sensie możliwości szybszego obliczania . Mówiłem o tym, że nie są w stanie obliczyć rzeczy, których klasyczny komputer nie byłby w stanie również obliczyć (gdzie odrzucam pojęcie „rzucania monetą” jako obliczenia).

— Niel de Beaudrap,

Rozważ bramę kwantową. Wygładzanie wszystkie szczegóły techniczne, może być reprezentowana jako matrycy . Wejście do bramki, powiedz tylko wektor , a wyjście bramki jest wektorem . $G$ $\vert \phi \rangle$ $v$ $Gv$

Teraz rozważ obwód. Układ jest tylko kilka bramek , I układ sam może być postrzegane jako „brama” uogólnione , który pracuje w oparciu o stan wejść (wektor ). [Ponownie, jest to bardzo szorstka abstrakcja.] $\{G_1, G_2, ... \}$ $C=G_n \cdots G_2 G_1$ $v$

Zasadniczo, obliczanie obwodu na wejściu jest jedynie obliczenie wektora lub . Oczywiste jest, że takie zadanie (mnożenie macierzy i mnożenie macierzy przez wektor) może być wykonane przez klasyczną TM, dlatego TM jest co najmniej tak samo silna jak kwant-TM (QTM) [ok, klasyczne obwody są tak silne jak kwant obwody nieważne.] $\vert \phi \rangle$ $Cv$ $G_n \cdots G_2 G_1 v$

Z drugiej strony QTM jest tak samo mocny jak TM, a zatem oba modele są równoważne.

EDYCJA z powodu komentarzy
Aby zapytać, który „komputer” ma większą moc, musimy najpierw wyjaśnić, co to znaczy być bardziej „mocnym obliczeniowo”. I ta na wpół filozoficzna dyskusja zaczyna się od pytania

Co to jest obliczenie ?

Czy „odtwarzanie plików MP3” jest obliczeniem? Czy wyprowadzanie liczb losowych jest obliczeniem?

Standardowa definicja mówi, że obliczenia to „obliczanie funkcji”. Oznacza to, że dla każdego wejścia (który może być dowolnym łańcuchem o dowolnej skończonej długości), należy wyprowadzić , gdzie ponownie może być łańcuchem o dowolnej (skończonej) długości. Jeśli twój komputer może wyprowadzić dla dowolnego , mówimy, że może obliczyć . $x$ $y=f(x)$ $y$ $y$ $x$ $f$

Teraz, aby powiedzieć, że komputer „A” jest mocniejszy niż „B” po prostu oznacza, że nalicza więcej funkcji niż . Podobnie, $f$ $B$

Dwa modele, i są uważane za równoważne , jeżeli dla dowolnej funkcji , Oblicza wtedy i tylko wtedy, gdy Oblicza . $A$ $B$ $f$ $A$ $f$ $B$ $f$

OK, mówisz, ale poczekaj chwilę, następuje losowość. Komputer kwantowy nie tylko generuje . Wyprowadza z prawdopodobieństwem lub z prawdopodobieństwem lub .... $y$ $y_1$ $p_1$ $y_2$ $p_2$ $^0$

Rzeczywiście .. I to rozszerza standardową definicję obliczania funkcji. Możemy to rozwiązać i uogólnić nasze definicje na kilka sposobów. (1), jedną z opcji jest, aby stwierdzić, że odpowiedź jest specyficzny który ma prawdopodobieństwo (a jest co najwyżej jedna taka wartość) . Jeżeli założymy, że wyprowadza tylko jeden bit, wówczas „wynik jest zawsze dobrze zdefiniowany W przeciwnym razie, jeśli taka wartość nie istnieje, a wszystkie wyjścia mają małe prawdopodobieństwo, możemy powiedzieć, że $f(x)$ $y_i$ $p_i>0.75$ $^1$ $f$ $f(x)$ $^2$ $f$ nie jest zdefiniowany na tym wejściu; (2) Druga opcja to znaczy, że produkcja jest lista . Aby to dobrze zdefiniować, musimy mieć skończoną listę, ponieważ wymagaliśmy, aby łańcuch wyjściowy był skończony. $f(x)$ $(y_1,p_1), (y_2,p_2),...$

W związku z powyższym powinno być jasne, że posiadanie prawdopodobieństwa nie zmienia mocy modelu, a klasyczna TM może po prostu wypisać listę możliwych wyników wraz z prawdopodobieństwem dla każdego wyjścia. dokładnie tak się dzieje, gdy TM zwielokrotnia macierze i wysyła wektor - wektor reprezentuje prawdopodobieństwo każdego możliwego wyniku pomiaru.

^{Ten problem nie dotyczy wyłącznie komputerów kwantowych. Klasyczne obliczenia probabilistyczne „cierpią” na ten sam problem. Dlaczego ? Bez powodu. Wszelkie stała większa niż będzie działać. zakładać, że wyprowadza jeden bit? bo to wystarczy. Możemy zredukować każdą bardziej złożoną funkcję do jednej lub więcej funkcji z wyjściem jednobitowym. Ale to nie ma znaczenia dla naszej dyskusji.
$^0$

$^1$ $p=0.75$ $1/2$

$^2$ $f$}

— Ran G.
źródło

Mógłbym zaprogramować obliczenia macierzowe na klasycznym komputerze, ale nie wiem, jak napisać kod symulujący obliczenia kwantowe. W każdym razie będę potrzebować bitów kwantowych. Bit kwantowy ma 2 wartości powszechnie oznaczone przez alfa i beta. Jakich wartości powinienem użyć? Zobacz także mój komentarz do odpowiedzi Niel de Beaudrap w sprawie generowania liczb losowych.

— Mok-Kong Shen

@ Mok-Kong Shen: te wartości brzmią jak współczynniki w superpozycji

. Przypomnijmy jednak, że notacja Diraca jest jedynie notacją wektorową: jest to dokładnie to samo, co pisanie

| ψ ⟩ = α | 0 ⟩ + β | 1 ⟩

$\def\ket#1{|#1\rangle}\ket\psi = \alpha\ket0 + \beta\ket1$

ze zwykłą konwencją. Współczynniki te są tylko współczynnikami wektor / matryca, co ocenia klasyczny komputer w celu (powolnej) symulacji komputera kwantowego.

ψ ψ = [α β]^{⊤}

$\pmb\psi = [\alpha\quad\beta]^\top$

— Niel de Beaudrap,

@Niel de Beaudrap: Ale kiedy piszę kod symulujący pewne obliczenia kwantowe, np. Wspomniane generowanie liczb losowych, muszę zaimplementować symulowane bity kwantowe na klasycznym komputerze. Nie wiem, jak napisać kod, aby to zrobić, nie znając wartości tych współczynników.

— Mok-Kong Shen

@ Mok-Kong Shen: chodzi o to, że w czasie wykonywania wiesz; problem jest dokładnie taki sam jak próbkowanie z klasycznego rozkładu prawdopodobieństwa, który jest określony na wejściu, tj . sprowadza się do dobrze zbadanych problemów w losowym próbkowaniu. Tutaj obowiązują na przykład metody Monte Carlo.

— Niel de Beaudrap,

@ Mok-KongShen Nie używaj komentarzy (szczególnie do postów innych osób) do długich dyskusji. Przejdź do czatu albo w pokoju ogólnym tej witryny lub w pokoju czatowym utworzonym w tym celu.

— Gilles „SO- przestań być zły”

inne odpowiedzi są poprawne, wystarczy dodać jedną, która podkreśla, że jest to naprawdę bardzo głębokie (w dużej mierze wciąż otwarte / nierozwiązane) pytanie w centrum wielu współczesnych badań nad separacjami klas złożoności i obliczeniami kwantowymi a klasycznymi. są one funkcjonalnie równoważne, o ile udowodniono, że oba TM i komputery QM są kompletne ; istnieje kilka sposobów, aby to udowodnić.

ale równoważność w teorii złożoności w dużej mierze zależy od subtelności / wydajności czasu i przestrzeni, tj. zasobów do obliczania poszczególnych algorytmów. istnieje również ogromna liczba badań dotyczących „szumu” w obliczeniach QM, które uważają, że teoretyczne modele bezgłośne mogą nie być „rzeczywiste” lub osiągalne w praktyce, a rzeczywiste modele mogą / będą mieć znaczny hałas. istnieją złożone systemy ograniczania tego hałasu itp .; jest świetny komentarz na ten temat w różnych postach na blogu RJ Liptons, np. latające maszyny XXI wieku

na przykład udowodniono, że faktoring jest w BQP, klasie algorytmów kwantowych, które działają w czasie P, przez Shora w słynnym dowodzie, że w tym czasie uruchomiono również dużą liczbę poważnych badań / badań z zakresu QM ze względu na dramatyczny wynik.

$\stackrel{?}{=}$

Scott Aaronson jest doskonałym pisarzem / badaczem na ten temat i napisał kilka artykułów dostępnych dla laika. patrz np . Ograniczenia komputerów QM, SciAm lub obliczeń QM obiecują nowe spostrzeżenia, NYT .

— vzn
źródło

uwaga, aram harrow jest wiodącym sceptykiem w obliczeniach problemów związanych z hałasem. kolejne dobre miejsce na rozpoczęcie, blog RJ Lipton, perpetum XXI wieku?

— vzn