Die klassische Turing-Maschine gibt es in verschiedenen Geschmacksrichtungen. Die Basisversion ist diejenige, die zuerst von Turing skizziert wurde, die nicht-deterministische Version erlaubt eine endliche Verzweigung bei jeder Berechnung und bei der jeder Verzweigung gefolgt wird, oder in der probabilistischen wird eine einzelne Verzweigung zufällig ausgewählt.
Eine nicht-deterministische Turing-Maschine löst nachweislich genau die gleichen Probleme wie die grundlegende, aber sie tut es exponentiell schneller, und die probabilistischen Maschinen können durch die grundlegende Maschine mit polynomialer Verlangsamung effizient simuliert werden.
Daher scheint es, dass trotz der Unterschiede diese Geschmacksrichtungen in Bezug auf die Lösbarkeit (aber nicht die Rechenleistung) gleichwertig sind.
Was fügt hier der Qualifier Quantum hinzu. Der Artikel in Wikipedia ist hier nicht eindeutig:
a. Wie unterscheidet es sich von der klassischen Version in Bezug auf die Lösbarkeit ? Das heißt, löst es genau die gleiche Klasse von Problemen oder unterscheiden sie sich in einigen wesentlichen Aspekten?
b. Wie unterscheiden sie sich in Bezug auf die Rechenleistung? Die einfachste Vermutung wäre eine exponentielle Beschleunigung – was uns zu nichtdeterministischen Turning-Maschinen führen würde. Ist das richtig?
Vergleichen Sie die Komplexitätsklassen BQP (Quantum) und BPP (Classical). Sie sind vielleicht besser mit P vs. NP vertraut; Beachten Sie, dass BPP ⊆ BQP ist und wir nicht wissen, wie sich BPP auf NP bezieht. BPP ist eine probabilistische Version von P. Nach dem BQP-Modell der Quantenberechnung sind Quantencomputer lediglich schneller bei der Lösung einiger Arten von Problemen. Ich meine zwei Dinge, wenn ich den sehr informatischen Begriff "nur schneller" verwende:
Warum kann BQP schneller sein? Nun, es stellt sich heraus, dass wir physikalisch berechenbare „Funktionen“ nutzen können, wie z. B. die Periodenfindung, was es ermöglicht, dass Primzahlfaktorisierung in der BQP-Komplexitätsklasse ist. Weitere Informationen finden Sie unter Quantenalgorithmus . Es ist nicht richtig, die Quantenberechnung als „alle Antworten gleichzeitig auszuprobieren“ zu betrachten – dies würde das Lösen von NP-Problemen in P-Zeit ermöglichen – denn es gibt kein bekanntes physikalisches Berechnungsmodell, das dies ermöglichen würde. Nun, Informatiker sprechen über "was wäre, wenn wir NP-Probleme in konstanter Zeit lösen könnten?"; siehe Orakelmaschinen .
Was wäre eine leistungsfähigere Art der Berechnung als Turing-Maschinen? Schauen Sie sich das unentscheidbare Problem an . Falls Sie mit Entscheidungsproblemen nicht ganz vertraut sind, können Sie sich eine Berechnung, die bei einer Eingabe eine komplexe Ausgabe erzeugt, stattdessen als eine Berechnung vorstellen, die zwei Eingaben nimmt – die Eingabe und den „Lösungsversuch“ – und einfach ergibt Sie ein 'Ja' oder ein 'Nein' als Ausgabe. Beispiele für Probleme, die etwas „Stärkeres“ als klassisches oder [bekanntes] Quantencomputing angehen könnte, finden Sie in der Liste der unentscheidbaren Probleme .
Ein Merkmal von unentscheidbaren Problemen ist, dass das Problem von uns verlangt, herauszufinden, ob es eine beliebig lange Sequenz gibt, die unser Problem löst. Erinnern Sie sich an die Probleme, bei denen Sie in wenigen Schritten von einem Wort zum anderen gelangen müssen, wobei jeder einzelne Buchstabe geändert werden muss und jedes dazwischen liegende „Wort“ gültig ist? Stellen Sie sich vor, Sie könnten so viele Schritte wie nötig haben: Es wird nicht immer der Fall sein, dass eine Turing-Maschine Ihnen sagen könnte, ob eine Reihe von Schritten in einer bekannten Zeit- / Raumgrenze existiert. Dies liegt daran, dass die Zeit-/Raumgrenze eine Funktion der Eingabe ist, nicht der Ausgabe. Wenn der Output beliebig groß werden kann, ist sozusagen „alle Wetten aus“.
Wenn wir über „Quanten“ hinausgehen zur „wahren Beschreibung des Universums“, werden wir vielleicht feststellen, dass unser Universum mächtiger ist als Turing-Maschinen. Zum Beispiel könnten wir irgendwie in der Lage sein, unendliche (oder beliebig große) Berechnungen in begrenzten Zeiten durchzuführen – Zeiten, die nicht so „explodieren“, dass bestimmte Probleme nach dem Turing-Maschinenmodell unentscheidbar werden. Der klassische → Quantum-Übergang bringt uns das nicht, aber wenn wir bei diesem Schritt Induktion durchführen, könnten wir zukünftige Übergänge erwarten, die ebenso unerwartet sind; Einer von ihnen könnte das Turing-Maschinenmodell der physikalischen Realität zerstören.
Einige der hier beschriebenen Unterschiede zwischen den Fähigkeiten klassischer Turing-Maschinen und Quantencomputer:
http://www.cs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf
In diesem Abschnitt stelle ich ein allgemeines, vollständiges Quantenmodell für Berechnungen vor. Anschließend beschreibe ich den universellen Quantencomputer Q, der in der Lage ist, jedes endlich realisierbare physikalische System perfekt zu simulieren. Es kann ideale geschlossene (Nulltemperatur-)Systeme, einschließlich aller anderen Instanzen von Quantencomputern und Quantensimulatoren, mit beliebig hoher, aber nicht perfekter Genauigkeit simulieren. Bei der Berechnung strenger Funktionen von Z bis Z erzeugt es genau die klassischen rekursiven Funktionen C(T ) (eine Manifestation des Korrespondenzprinzips). Im Gegensatz zu T kann es jeden endlichen klassischen diskreten stochastischen Prozess perfekt simulieren. Darüber hinaus, wie wir in x3 sehen werden, gibt es so viele bemerkenswerte und potenziell nützliche Fähigkeiten, die keine klassischen Analoga haben.
Benutzer3164
Niel de Beaudrap
Mosibur Ullah