Was ist der Unterschied zwischen Quanten-TM und nicht-deterministischem TM?

30

Ich habe die Diskussion über die Frage, wie Quanten-Turing-Maschinen zu definieren sind , durchlaufen . und ich fühle, dass Quanten-TM und nicht- deterministisches TM ein und dasselbe sind. Die Antworten auf die andere Frage berühren das nicht. Sind diese beiden Modelle ein und dasselbe?

Wenn nein

  1. Was sind die Unterschiede zwischen Quantum TM und NDTM?
  2. Gibt es eine Berechnung, die ein NDTM schneller als Quantum TM durchführen würde?
  3. Wenn dies der Fall ist, dann ist Quanten-TM ein DTM. Warum steckt dann so viel Unklarheit in dieser Technologie? Wir haben bereits so viele DTM. Warum am Ende einen neuen DTM entwerfen?
Bongubj
quelle
1
"Wenn dies der Fall ist, dann ist Quanten-TM ein DTM." - Wo kommt das her?
Raphael

Antworten:

20

Als allgemeine Präambel sind QTMs, TMs und NTMs alle verschiedene Dinge (unter großen Freiheiten mit einer Reihe von unausgesprochenen Annahmen).

Ich gehe davon aus, dass Sie wissen, was eine Turing-Maschine ist.

  1. Ein NTM ist ein TM, bei dem die Übergangsfunktion in jedem Zustand mit einem beliebigen Symbol eine Reihe von Auswahlmöglichkeiten für eine Aktion haben darf, die nicht genau , dh oder mehr als (ein deterministisches TM muss genau eine Aktion für haben jedes Symbol in jedem Zustand, obwohl der Fall leicht zu behandeln ist). In einer Situation, in der es mehrere Übergangswahlen gibt, trifft ein NTM die Wahl, die ihn letztendlich in einen akzeptierenden Zustand versetzt, falls eine solche Option besteht. Im Gegensatz dazu ist ein QTM ein Modell für die Quantenberechnung , wie in dem von Ihnen verknüpften Thread beschrieben. Es ist nicht0 1 01 010

    nicht deterministisch, nicht alle. Wahrscheinlich besteht der Hauptunterschied zwischen einem QTM und einem TM darin, dass ein QTM eine lineare Kombination der Basiszustände als Zustand hat (wieder alles in diesem anderen Thread) und dass es probabilistisch ist, dh die Genauigkeit seiner Ausgabe ist begrenzt durch eine Wahrscheinlichkeit von weniger als (im Allgemeinen). Nur um wirklich klar zu sein, was viele Menschen angeht, Nichtdeterminismus ist keine Zufälligkeit, es ist keine Parallelität, es ist ein theoretisches Konstrukt, das mit keinem von beiden etwas zu tun hat. 1

  2. Die vollständige Antwort darauf hängt von einigen komplexitätstheoretischen Annahmen ab. Unter einem bestimmten Gesichtspunkt (dieser und ) lautet die Antwort ja. vollständige Probleme können von einem NTM in Polynomialzeit gelöst werden, und es scheint auch, dass , so dass sie von einem QTM in Polynomialzeit nicht gelöst werden können. Auch dies hängt alles davon ab, in welche Richtung die Karten mit einer Vielzahl von Komplexitätsklassen fallen. Wenn sich herausstellt, dass ist, lautet die Antwort beispielsweise nein. N P P N P N P -komplette B Q P = Q M A = B Q PQ.MEINBQ.PNPPNPNP-KomplettBQ.P=

    Q.MEIN=BQ.P
  3. Das erste, was Sie hier sagen müssen, ist, vorsichtig zu sein, um TMs (jeglicher Art) und Computer zu verwechseln. Ein TM ist kein Computer, ein QTM ist kein Quantencomputer. TMs (jeglicher Art) Modellberechnung. Was ein bestimmter Computer tun kann, hängt davon ab, aber das ist etwas ganz anderes als zu sagen, dass ich hier einen TM eintippe.

    Wenn wir jedoch QTMs mit Quantencomputern und TMs mit Standardcomputern locker und träge identifizieren, können Quantencomputer (wiederum unter bestimmten Komplexitätsannahmen) schnell bestimmte Aufgaben ausführen, die für Standardcomputer schwierig erscheinen (Faktorisierung, diskrete Protokolle) , eine wirklich besondere Art der Suche, und ein paar andere). Es ist jedoch nicht bekannt, dass diese Probleme imN PNPEs scheint, als ob Quantencomputer Funktionen bieten, die einen Standardcomputer erweitern, aber in eine andere Richtung als die, die zur raschen Lösung von Problemen erforderlich wäre . NP

Um noch einmal ganz klar zu sein, ich habe hier viel Rechenaufwand beschönigt. Wenn Sie wirklich verstehen wollen, wie alles zusammenpasst, müssen Sie sich mit der Literatur befassen.

Luke Mathieson
quelle
Vielen Dank @LukeMathieson. Ich werde versuchen, alles zu verdauen und alle Fragen, die ich bekommen könnte, zurückzuschicken.
Bongubj
Froh, dass ich helfen konnte. Offensichtlich fehlen viele technische Details, um zu Sinn und Intuition zu gelangen. Der Wikipedia-Artikel über Turing Machines ist recht anständig, um die technischen Dinge dort zu behandeln. Die QTM ist traurig, aber der andere Thread ist trotzdem hervorragend. Das QTM-Zeug kann jedoch etwas dunkel sein, wenn Sie noch keinen Kurs über Hilbert Spaces oder ähnliches gemacht haben.
Luke Mathieson
3
"Nichtdeterminismus ist keine Zufälligkeit, es ist keine Parallelität, es ist ein theoretisches Konstrukt, das mit beiden nichts zu tun hat." - Das ist hier wahrscheinlich ein Schlüsselsatz.
Raphael
13

Über die Bedeutung des Nichtdeterminismus

Hier geht es um zwei verschiedene Bedeutungen des Nichtdeterminismus. Die Quantenmechanik wird gewöhnlich als "nicht deterministisch" beschrieben, aber das Wort "nicht deterministisch" wird in der theoretischen Informatik auf spezielle Weise verwendet.

  1. Eine Bedeutung, die für die Quantenmechanik gilt, ist einfach "nicht deterministisch ". Dies ist normalerweise eine vernünftige Art, das Wort zu interpretieren, und tatsächlich sind weder Quanten-Turing-Maschinen noch probabilistische Turing-Maschinen deterministisch in der Art, wie sie Entscheidungsprobleme lösen.

  2. Bei der Beschreibung von Rechenmodellen wird nichtdeterministisch jedoch speziell verwendet, um zu bedeuten, dass die Maschine (in gewissem Sinne) Entscheidungen treffen kann, die nicht durch ihren Zustand oder ihre Eingabe bestimmt werden, um ein bestimmtes Ziel zu erreichen. Diese Bedeutung wird an anderer Stelle bei der Beschreibung von Berechnungsmodellen verwendet, z. B. bei nicht deterministischen endlichen Automaten .

Quanten-Turing-Maschinen sind also ein Rechenmodell, das nicht deterministisch ist, sondern sich von einer "nicht deterministischen Turing-Maschine " unterscheidet.

Nichtdeterministische Turingmaschinen

Eine nicht deterministische Turing-Maschine ist eine Maschine, die mehrere mögliche Übergänge untersuchen kann. Der Übergang, den es bei einem bestimmten Schritt ausführt, hängt vom Status und dem Symbol, das es liest, ab, ist jedoch nicht davon abhängig. Es gibt zwei Möglichkeiten, wie dies allgemein dargestellt wird:

  • Insbesondere zum Zwecke der Definition der Komplexitätsklasse NP kann man die Maschine als Treffen von Entscheidungen (oder Vermutungen) bei jedem Schritt beschreiben, um zu versuchen, einen akzeptierenden Zustand zu erreichen . Wenn Sie sich vorstellen, dass die nicht deterministische Maschine einen Entscheidungsbaum untersucht, sucht sie nach einem akzeptierenden Pfad im Baum. Während es keinen Mechanismus gibt, der beschreibt, wie ein solcher Pfad gefunden werden sollte, stellen wir uns vor, dass er einen akzeptierenden Pfad finden wird, wenn nur einer existiert.

  • Es ist auch durchaus üblich , zu sagen , dass eine nichtdeterministische Maschine alle möglichen Pfade in dem Entscheidungsbaum parallel untersucht, und gibt eine Antwort „ja“ , wenn jeder von ihnen erweisen sich als eine akzeptierende Weg sein.

Neuere Behandlungen des Nichtdeterminismus berücksichtigen nicht nur die Existenz, sondern auch die Anzahl der akzeptierenden Pfade. und dies ist gut geeignet für die Beschreibung der parallelen Erkundung aller Pfade. Wir können zusätzliche Einschränkungen auferlegen, zum Beispiel, dass alle Berechnungspfade die gleiche Länge haben (dass die Maschine immer die gleiche Zeit benötigt, um eine Berechnung durchzuführen) und dass jeder Pfad bei jedem Schritt oder bei jedem zweiten Schritt eine Schätzung ausführt, selbst wenn Die Vermutung wird nicht verwendet. Wenn wir dies tun, können wir probabilistische Berechnungsmodelle wie zufällige Turing-Maschinen (motivierende Komplexitätsklassen wie BPP ) in Bezug auf die Anzahl formulierenWege einer nichtdeterministischen Turingmaschine zu akzeptieren. Wir können dies auch umkehren und nichtdeterministische Turing-Maschinen in Form von randomisierten Computern beschreiben, die auf irgendeine Weise zwischen Ergebnissen mit einer Wahrscheinlichkeit von null und solchen mit einer Wahrscheinlichkeit von ungleich null unterscheiden können .

Quantenturing-Maschinen

Der Hauptunterschied zwischen einer Quantenturing-Maschine und einer nicht deterministischen Maschine besteht darin, dass eine Quantenturing-Maschine einen Übergang zu einer Überlagerung von einem oder mehreren möglichen Übergängen durchführt, anstatt einen einzelnen Übergang aus zwei oder mehreren Schritten nicht deterministisch auszuwählen. Der vollständige Zustand der Maschine wird als Einheitsvektor in einem komplexen Vektorraum definiert, der durch lineare Kombinationen von Basiszuständen definiert wird, die durch klassische Zustände des Bandes, die Position des Maschinenkopfes und den "internen Zustand" des Maschinenkopfes beschrieben werden . (Siehe z . B. Seite 9, Definition 3.2.2 der QuantenkomplexitätstheorieFür die vollständige Beschreibung, wie Quanten-Turing-Maschinen Übergänge durchführen.) Die Bedingung, unter der die Quanten-Turing-Maschine eine Eingabe akzeptiert, ist ebenfalls restriktiver und beinhaltet von Natur aus eine Wahrscheinlichkeit, die eine erhebliche Wahrscheinlichkeit erfordert, das richtige Ergebnis zu beobachten, um erfolgreich zu sein.

Infolgedessen unterscheiden sich Quanten-Turing-Maschinen von nichtdeterministischen Maschinen darin, dass die Art und Weise, wie sie ihre Übergänge ausführen, nicht vollständig unbekannt ist. Auch wenn der Übergang "mysteriös erscheint", ist es mit der Zeit dieselbe Art von Evolution, auf die unsere beste Theorie der Materie hinweist, dass sie in der realen Welt stattfindet. Obwohl es üblich ist, Quantencomputer so zu beschreiben, dass sie "verschiedene Rechenpfade parallel erkunden", ist dies nicht besonders nützlich: Die Amplituden auf den verschiedenen Pfaden bedeuten, dass sie nicht alle die gleiche Bedeutung haben, und anders als nicht deterministische Turing-Maschinen ist nicht genug, um eine Amplitude ungleich Null für ein bestimmtes Ergebnis zu haben; Es muss möglich sein, eine sehr große Wahrscheinlichkeit für das Erreichen des korrekten Ergebnisses zu erhalten, z. B. 2/3. (Die Klasse der Probleme BQPdie eine Quanten Turing - Maschine effizient lösen erfordert eine Wahrscheinlichkeitslücke der gleichen Art wie BPP für randomisierte Berechnung hat.) Darüber hinaus sehr viel im Gegensatz zu nichtdeterministischen Turing - Maschinen, eine Quanten Maschine Turing diejenigen miteinander interferieren können , nachdem sie gespalten haben , Das ist bei der typischen Formulierung einer nichtdeterministischen Turing-Maschine einfach unmöglich (und macht die Beschreibung in Form eines Entscheidungsbaums in erster Linie weniger nützlich).

Vergleich der beiden Modelle

Wir wissen nicht, ob eine dieser Maschinen leistungsstärker ist als die andere. Die unterschiedlichen Arten, in denen sie nicht deterministisch sind, scheinen sich zu unterscheiden und sind schwer zu vergleichen.

Was die Probleme betrifft, die jede Maschine schnell lösen kann, die die andere nicht kann (soweit wir wissen):

  • Wir wissen nicht, wie eine Quantenturing-Maschine das Problem der ZUFRIEDENHEIT schnell lösen kann . Eine nichtdeterministische Turingmaschine kann das leicht.
  • Arbeiten von Aaronson und Archipov ( The Computational Complexity of Linear Optics ) legen nahe, dass es unwahrscheinlich ist, dass nichtdeterministische Turingmaschinen bestimmte Experimente der linearen Optik, die mit einer Quantenturingmaschine simuliert werden könnten, effizient simulieren können.

Aber selbst wenn jemand zeigt, wie man die beiden Maschinentypen miteinander in Beziehung setzt - und selbst in dem äußerst unwahrscheinlichen Szenario, dass jemand BQP  =  NP zeigt (die Probleme, die eine Quantenturingmaschine und eine nicht deterministische Turingmaschine jeweils schnell lösen können) ) - Die beiden Maschinen, die diese Berechnungsmodelle definieren, unterscheiden sich erheblich voneinander.

Niel de Beaudrap
quelle
Keine Angst haben zu widersprechen! Ich habe mit Sicherheit einen vereinfachten Ansatz gewählt, um zu verdeutlichen, dass es Unterschiede zwischen den verschiedenen Maschinen gibt. Die einzigen Dinge, die ich zu dem, was Sie gesagt haben, hinzufügen möchte, sind, dass ich immer noch behaupte, dass Zufälligkeit nicht dasselbe ist wie Nichtdeterminismus - Sie können (zum Beispiel) BPP mit Nichtdeterminismus definieren, aber auch mit sehr spezifischen Bedingungen und Sie können es leicht definieren im selben Sinne wie bei deterministischen Maschinen (etwas, das Sie für NP, NEXP usw. nicht tun können, müssen Sie dafür auf Verifikation und nicht auf Berechnung umstellen).
Luke Mathieson
1
Der zweite Teil ist, dass ich die Vorstellung von Nichtdeterminismus als Parallelismus irreführend finde (obwohl ich es früher auch so gesehen habe). Es ist eine gute Vorstellung, solange Sie bedenken, dass es sich nicht wirklich um "echte" Parallelität handelt. Eine einfache nicht deterministische Maschine kann effektiv eine exponentielle Anzahl deterministischer Maschinen simulieren (solange Sie nur die richtige Antwort erhalten möchten, nicht alle Berechnungspfade betrachten und der Unterschied zwischen NP und #P ziemlich groß ist). Die Idee, dass alle Pfade gleichzeitig überprüft werden, deckt die Dinge ab.
Luke Mathieson
Hoffentlich sind Sie glücklich, die angemessenen Details dort auszufüllen, diese Kommentare sind zu kurz! ;)
Luke Mathieson
@LukeMathieson: Ich bin mir eigentlich nicht sicher, worauf Sie mit Ihren Kommentaren hinauslaufen, da ich die Unterscheidung zwischen „rechnerischem Nichtdeterminismus“ und Zufälligkeit betone und klar beschreibe, welche grobe Art von paralleler Erforschung eine NP- Maschine sein kann sagte zu tun, und so weiter. Können Sie klarstellen, was Ihrer Meinung nach hinzugefügt werden sollte?
Niel de Beaudrap
Oh, ich glaube nicht, dass etwas an dem, was du gesagt hast, geändert werden muss. Ich habe nur versucht (versagt?;)), Einen Kommentar hinzuzufügen, der helfen könnte, einige interessante Aspekte des Nichtdeterminismus und seine Beziehungen zu anderen rechnerischen Ideen herauszustellen.
Luke Mathieson