Einheitliche Methode zur Quantifizierung von „Verzweigungen“ bei nichtdeterministischen, probabilistischen und Quantenberechnungen?

10

Die Berechnung einer nichtdeterministischen Turing-Maschine (NTM) ist bekanntermaßen als ein Baum von Konfigurationen darstellbar, der auf der Startkonfiguration basiert. Jeder Übergang im Programm wird durch einen Vater-Kind-Link in diesem Baum dargestellt.

Ähnliche Bäume können auch zur Visualisierung der Berechnungen von Wahrscheinlichkeits- und Quantenmaschinen konstruiert werden. (Beachten Sie, dass es für einige Zwecke besser ist, den zugehörigen Graphen für Quantenberechnungen nicht als Baum anzuzeigen, da sich zwei Knoten, die identische Konfigurationen auf derselben Ebene des Baums darstellen, aufgrund von Quanteninterferenz gegenseitig "aufheben" können hat mit der vorliegenden Frage nichts zu tun.)

Natürlich sind deterministische Berechnungen nicht so; Für jeden Lauf einer deterministischen Maschine gibt es im entsprechenden "Baum" einen einzelnen "Zweig".

In allen drei oben genannten Fällen ist es für deterministische Computer manchmal nicht wirklich "schwierig", diese Berechnungen "schwierig" zu machen, sondern es geht darum, wie viel Verzweigung im Baum vorhanden ist. Beispielsweise kann eine nichtdeterministische Turing-Maschine mit Polynomzeit, die garantiert Rechenbäume erzeugt, deren "Breiten" (dh Anzahl der Knoten in der am stärksten überfüllten Ebene) ebenfalls durch eine Polynomfunktion der Eingabegröße begrenzt sind, durch ein Polynom simuliert werden -zeitdeterministisches TM. (Beachten Sie, dass diese Bedingung der "Polynombreite" der Einschränkung des NTM entspricht, höchstens eine logarithmisch begrenzte Anzahl nichtdeterministischer Vermutungen anzustellen.) Dasselbe gilt, wenn wir probabilistische und Quantenberechnungen mit ähnlichen Breitengrenzen versehen.

Ich weiß, dass dieses Problem für nicht deterministische Berechnungen eingehend untersucht wurde. Siehe zum Beispiel die Umfrage " Limited Nondeterminism " von Goldsmith, Levy und Mundhenk. Meine Frage ist, wurde dieses Phänomen der "begrenzten Verzweigung" oder "begrenzten Breite" in einem gemeinsamen Rahmen untersucht, der alle nichtdeterministischen, probabilistischen und Quantenmodelle umfasst? Wenn ja, wie lautet der Standardname dafür? Alle Links zu Ressourcen werden geschätzt.

cc.complexity-theory quantum-computing randomness derandomization nondeterminism Cem Say
quelle

Antworten:

11

Lx∈Lt(|x|)http://www.wisdom.weizmann.ac.il/~oded/p_laconic.html

P=BPP

Oder Meir
quelle
Vielen Dank! Das fragliche Phänomen entspricht also im ersten Fall dem "Lesen eines Beweissymbols" und im zweiten dem "Werfen einer Münze". Aber was ist mit dem dritten Fall, dh Quanten? Ich würde es wirklich begrüßen, wenn jemand, der diese Dinge versteht, erklären würde, was der wichtige Unterschied zwischen einem Quantenübergang, dessen Amplitude Modul 1 hat (dh einem "nicht verzweigten" Übergang), und einem verzweigten ist. Ist die Implementierung von Quantenverzweigungen schwieriger, kostspieliger usw. als beispielsweise die Implementierung von Quantenverzweigungen?
Cem Say
Ich kann im Moment nichts Rigoroses sagen, aber ich denke, im Quantenfall ist die Menge der Verstrickung in den Konfigurationszustand, in dem sich Ihre Maschine gerade befindet. Wenn es keine Verstrickung gibt, wäre es wie eine probabilistische Maschine. Anstatt den Verzweigungsgrad zu zählen, ist es in diesem Fall vielleicht sinnvoller, den Grad der Verschränkung zu zählen, z. B. den Rang des Staates (was Physiker Schmidt-Nummer nennen) oder eine andere Methode zur Messung der Verschränkung zu berechnen. Aber wie gesagt, das ist nur ein Gedanke.
Marcos Villagra