Referenzen zum Vergleich zwischen Quantencomputern und Turingmaschinen

Mir wurde gesagt, dass Quantencomputer nicht rechnerisch leistungsfähiger sind als Turing-Maschinen. Könnte jemand freundlich helfen, einige Literaturhinweise zu geben, die diese Tatsache erklären?

computability reference-request turing-machines quantum-computing Mok-Kong Shen
quelle

Sie scheinen ein registriertes Konto auf anderen Stack Exchange-Sites zu haben. Sie sollten Ihr CS-Konto registrieren und mit den anderen verknüpfen (siehe Hilfe ). Auf diese Weise können Sie unter anderem am Chat von CS teilnehmen.

Gilles 'SO - hör auf böse zu sein'

Antworten:

Was tatsächlich der Fall ist, ist, dass alles, was ein Quantencomputer berechnen kann, auch eine Turing-Maschine berechnen kann. (Dies ist ohne zu kommentieren, wie lange die Turing-Maschine benötigt, um die Funktion im Vergleich zu einem Quantencomputer zu berechnen.)

Dies ist eigentlich nicht schwer zu erkennen, vorausgesetzt, Sie verstehen die Quantenberechnung. Für eine Quantenschaltung über einen typischen Gatesatz wird das Ergebnis beispielsweise durch eine Wahrscheinlichkeitsverteilung bestimmt, die durch die Koeffizienten einer einheitlichen Matrix bestimmt wird. Diese einheitliche Matrix ist nur ein Matrixprodukt derjenigen der Tore und kann - wenn Sie geduldig genug sind - von einem klassischen Computer berechnet werden. Aus Gründen der Berechenbarkeit (im Gegensatz zur Effizienz) bietet die Verwendung von Quantencomputern keinen Vorteil.

Die ganze Herausforderung, die sich aus der Quantenmechanik ergibt, besteht darin, zu bestimmen, ob solche Koeffizienten effizient berechnet werden können , was ein anspruchsvolleres Problem darstellt, als ob sie überhaupt berechnet werden können .

Niel de Beaudrap
quelle

Während mir das Wissen meines Anfängers sagt, dass eine Quantenschaltung eine Hadamard-Matrixtransformation darstellt, kann ich noch nicht sehen, wie eine Programmiermöglichkeit, beliebige Matrixberechnungen auf einem klassischen Computer durchzuführen, ein Ersatz für eine physikalische Quantenschaltung sein könnte. In meinem Buch heißt es beispielsweise, Zufallszahlen wie folgt zu generieren: 1. | x> <- | 0> 2. | x> <- H | x> 3. Messen Sie | x> Was würde insbesondere Schritt 3 entsprechen? Programmieren auf einem klassischen Computer?

Mok-Kong Shen

Eine (richtig normalisierte) Hadamard-Matrix ist nur eine mögliche einheitliche Transformation. Für Ihre Berechnung können wir erkennen , dass eine deterministische Turing - Maschine die Wahrscheinlichkeitsverteilung berechnen kann (0,5, 0,5) , bestehend aus den Normen-squared der ersten Spalte der Hadamard - Matrix

, und dass wir für eine randomisierte Turing-Maschine (die Münzwürfe ausführen kann) einen Schritt weiter gehen und eine Stichprobe aus dieser Wahrscheinlichkeitsverteilung erstellen können. In jedem Fall kann jede Funktion, die von der Quantenschaltung mit einem Fehler <1/2 berechnet wird, auch eine klassische Maschine.

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

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

Niel de Beaudrap

@ Mok-Kong Shen: falls es nicht klar , aus meinen Bemerkungen über Ineffizienz oder Langsamkeit ist, ist es allgemein angenommen , dass Quantencomputer sind rechenleistungsfähig mehr im Sinne des in der Lage zu berechnen schnell . Ich habe die Tatsache angesprochen, dass sie nicht in der Lage sind, Dinge zu berechnen, die ein klassischer Computer nicht auch berechnen kann (wobei ich den Begriff "Münzwurf" als Berechnung außer Acht lasse).

Niel de Beaudrap

Betrachten Sie ein Quantentor. Es glättet alle technischen Details und kann als Matrix . Ein Eingang zum Gate, sagen wir ist nur ein Vektor , und der Ausgang des Gatters ist die Vektor . $G$ $\vert \phi \rangle$ $v$ $Gv$

Betrachten Sie nun eine Schaltung. Eine Schaltung ist nur ein Bündel von Toren , und die Schaltung selbst kann als "verallgemeinertes Gatter" , das mit dem Eingangszustand (dem Vektor ) arbeitet. [Auch dies ist eine sehr grobe Abstraktion.] $\{G_1, G_2, ... \}$ $C=G_n \cdots G_2 G_1$ $v$

Berechnen einer Schaltung an einem Eingang , lediglich wird die Berechnung des Vektors oder . Es ist klar, dass eine solche Aufgabe (Matrixmultiplikation und Multiplikation der Matrix mit dem Vektor) von einem klassischen TM ausgeführt werden kann, daher ist TM mindestens so stark wie ein Quanten-TM (QTM) [ok, klassische Schaltungen sind so stark wie Quanten Schaltungen. vergiss das.] $\vert \phi \rangle$ $Cv$ $G_n \cdots G_2 G_1 v$

Auf der anderen Seite ist QTM trivial so stark wie TM, und daher sind beide Modelle gleichwertig.

BEARBEITEN aufgrund von Kommentaren
Um zu fragen, welcher "Computer" leistungsfähiger ist, müssen wir zunächst klären, was es bedeutet, "rechnerisch leistungsfähiger" zu sein. Und diese halbphilosophische Diskussion beginnt mit der Frage

Was ist Berechnung ?

Ist das Abspielen von MP3-Dateien eine Berechnung? Ist die Ausgabe von Zufallszahlen eine Berechnung?

Die Standarddefinition besagt, dass eine Berechnung "eine Funktion berechnen" ist. Das heißt, für jede Eingabe (die eine beliebige Zeichenfolge beliebiger endlicher Länge sein kann) wird ausgegeben $x$ , wobei wiederumeine Zeichenfolge beliebiger (endlicher) Länge sein kann. Wenn Ihr Computer für ein beliebiges ausgebenkann, sagen wir, dasser berechnen kann. $y=f(x)$ $y$ $y$ $x$ $f$

Zu sagen, dass Computer "A" leistungsfähiger als "B" ist, bedeutet nur, dass A mehr Funktionen als berechnet . Ähnlich, $f$ $B$

Zwei Modelle, und $A$ $B$ werden als äquivalent , wenn für jede Funktion , berechnet , wenn und nur wenn berechnet . $f$ $A$ $f$ $B$ $f$

OK, sagst du, aber warte eine Sekunde, es gibt eine Randomisierung. Ein Quantencomputer gibt nicht nur . Es gibt mit Wahrscheinlichkeit aus $y$ $y_1$ oder mit der Wahrscheinlichkeit oder .... $p_1$ $y_2$ $p_2$ $^0$

In der Tat. Und dies erweitert die Standarddefinition der Berechnung einer Funktion. Wir können es lösen und unsere Definitionen auf verschiedene Arten verallgemeinern. (1) Eine Option besteht darin zu sagen, dass die Antwort von das spezifische , das eine Wahrscheinlichkeit (und es gibt höchstens einen solchen Wert) . Wenn wir annehmen, dass nur ein einziges Bit ausgibt, dann ist "die Ausgabe von immer gut definiert Andernfalls, wenn kein solcher Wert existiert und alle Ausgaben eine geringe Wahrscheinlichkeit haben, können wir sagen $f(x)$ $y_i$ $p_i>0.75$ $^1$ $f$ $f(x)$ $^2$ $f$ ist für diesen Eingang nicht definiert; (2) Eine zweite Option besteht darin, zu sagen, dass die Ausgabe von die Liste . Damit dies genau definiert ist, müssen wir eine endliche Liste haben, da die Ausgabezeichenfolge endlich sein muss. $f(x)$ $(y_1,p_1), (y_2,p_2),...$

Mit dem oben Gesagten sollte klar sein, dass Wahrscheinlichkeiten die Leistung des Modells nicht ändern, und ein klassisches TM kann nur die Liste möglicher Ausgaben zusammen mit der Wahrscheinlichkeit für jede Ausgabe ausgeben. Dies ist genau das, was passiert, wenn ein TM Matrizen multipliziert und einen Vektor ausgibt - der Vektor repräsentiert die Wahrscheinlichkeit jeder möglichen Messausgabe.

^{$^0$

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

$^2$ $f$}

Ran G.
quelle

Ich könnte Matrixberechnungen auf einem klassischen Computer programmieren, weiß aber nicht, wie man einen Code schreibt, um eine Quantenberechnung zu simulieren. Ich brauche sowieso Quantenbits. Ein Quantenbit hat zwei Werte, die üblicherweise mit Alpha und Beta bezeichnet werden. Welche Werte soll ich verwenden? Siehe auch meinen Kommentar zur Antwort von Niel de Beaudrap zum Fall der Zufallszahlengenerierung.

Mok-Kong Shen

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

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

ψ ψ = [α β]^{⊤}

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

@Niel de Beaudrap: Aber wenn ich einen Code schreibe, um eine bestimmte Quantenberechnung zu simulieren, z. B. die von mir erwähnte Zufallszahlengenerierung, muss ich simulierte Quantenbits auf einem klassischen Computer implementieren. Ich weiß nicht, wie ich Code schreiben soll, ohne die Werte dieser Koeffizienten zu kennen.

Mok-Kong Shen

@ Mok-Kong Shen: Der Punkt ist, dass Sie zur Laufzeit wissen; und das Problem ist genau das gleiche wie die Stichprobe aus einer klassischen Wahrscheinlichkeitsverteilung, die am Eingang angegeben ist, dh es reduziert sich auf gut untersuchte Probleme bei der Zufallsstichprobe. Hier gelten beispielsweise Monte-Carlo-Methoden.

Niel de Beaudrap

@ Mok-KongShen Bitte verwenden Sie keine Kommentare (insbesondere nicht zum Beitrag eines anderen) für erweiterte Diskussionen. Gehen Sie zum Chat , entweder im allgemeinen Raum für diese Site oder in einem Chatroom, der für diesen Zweck erstellt wurde.

Gilles 'SO - hör auf böse zu sein'

andere Antworten sind gültig, ich möchte nur eine hinzufügen, die betont, dass dies wirklich eine sehr tiefe (weitgehend noch offene / ungelöste) Frage ist, die im Zentrum vieler moderner Forschungen zu Komplexitätsklassen-Trennungen und Quanten- und klassischem Rechnen steht. Sie sind funktional gleichwertig, sofern TMs und QM-Computer nachweislich vollständig sind . Es gibt verschiedene Möglichkeiten, dies zu beweisen.

Die Äquivalenz in der Komplexitätstheorie hängt jedoch stark von zeitlichen und räumlichen Feinheiten / Effizienzen ab, dh von Ressourcen zur Berechnung bestimmter Algorithmen. und es gibt auch eine große Menge an Forschung, die sich mit "Rauschen" im QM-Computing befasst und berücksichtigt, dass theoretische rauschfreie Modelle möglicherweise nicht "real" oder in der Praxis erreichbar sind und reale Modelle möglicherweise signifikantes Rauschen aufweisen. Es gibt komplexe Schemata, um dieses Rauschen usw. zu mildern. Es gibt einige ausgezeichnete Kommentare dazu in verschiedenen Beiträgen im RJ Liptons-Blog, z. B. Flugmaschinen des 21. Jahrhunderts

Zum Beispiel wurde von Shor bewiesen, dass Factoring in BQP, der Klasse von Quantenalgorithmen, die in P-Zeit ausgeführt werden, enthalten ist. Dies ist ein berühmter Beweis dafür, dass zu dieser Zeit aufgrund der Dramatik auch eine große Menge ernsthafter Studien / Forschungen zum QM-Computing gestartet wurden Ergebnis.

$\stackrel{?}{=}$

Scott Aaronson ist ein ausgezeichneter Schriftsteller / Forscher auf dem Gebiet und hat einige Artikel geschrieben, die für den Laien zugänglich sind. siehe zB Die Grenzen von QM-Computern, SciAm oder QM-Computing versprechen neue Erkenntnisse, NYT .

vzn
quelle

Beachten Sie, dass Aram Egge ein führender Skeptiker von QM-Computing bei Rauschproblemen ist. Ein weiterer guter Anfang, RJ Lipton Blog, ewige Bewegung des 21. Jahrhunderts?

vzn