-normkonservierende Turingmaschinen

Wenn ich einige aktuelle Threads zum Thema Quantencomputer ( hier , hier und hier ) lese, erinnere ich mich an eine interessante Frage zur Leistungsfähigkeit einer Art -norm preserving machine.$\ell_p$

Für Leute, die sich mit Komplexitätstheorie und Quantenkomplexität beschäftigen, ist Fortnows Artikel ein großartiger Einführungstext, der von Joshua Grochow hier veröffentlicht wurde . In dieser Arbeit wird die Quanten-Turing-Maschine als generalisierte probabilistische Turing-Maschine vorgestellt. Grundsätzlich hat die Wahrscheinlichkeitsmaschine einen unter der orm 1 -Norm normierten Zustand , dh ∥ s ∥ 1 = 1 . Die zeitliche Entwicklung der Maschine ist durch Aufbringen einer stochastischen Matrix P gegeben, so dass ∥ P s ∥ 1 = 1 ist , dh P das bewahrt$s$$\ell_1$$\parallel s\parallel_1=1$$P$$\parallel Ps\parallel_1=1$$P$ -norm. Der Zustand zum Zeitpunkt t ist also P t s (die Notation ist möglicherweise nicht genau, da die linke oder rechte Multiplikation von P davon abhängt, ob s ein Zeilen- oder Spaltenvektor ist oder die Zeilen oder Spalten von P die Unterabschnitte sind, die die Norm bewahren). So in diesem Sinnedie probabilistische Turingmaschine ist eine l 1 -Norm Konservierungsmaschine bezeichnete M l 1 .$\ell_1$$t$$P^ts$$P$$s$$P$$\ell_1$$M^{\ell_1}$

Dann kann eine Quantenturing-Maschine mit einem Zustand mit state s ∥ 2 = 1 und einer einheitlichen Matrix P (die ℓ 2 -Normale beibehält) betrachtet werden, so dass P t s der Zustand zum Zeitpunkt t ist, in dem ∥ P t s ∥ 2 ist = 1 . Dies ist eine l 2 -Norm Konservierungsmaschine bezeichnete M l 2 .$s$$\parallel s\parallel_2=1$$P$$\ell_2$$P^ts$$t$$\parallel P^ts\parallel_2=1$$\ell_2$$M^{\ell_2}$

Lassen Sie in der Regel eines -Norm Erhaltung Maschine bezeichnet M l p .$\ell_p$$M^{\ell_p}$

Meine Fragen sind also:

(1) Was ist die Kraft von -Normkonservierungsmaschinen für endliches p ? Genauer gesagt, können wir beweisen, dass für jedes gegebene p und q , wenn q > p , eine Sprache L und eine Maschine M ℓ q existiert, so dass M ℓ q L effizient entscheidet und es keine Maschine M ℓ p gibt , die L effizient entscheidet . Dies könnte beispielsweise eine Verallgemeinerung der Frage sein, ob N P ⊆ B Q P ?$\ell_p$$p$$p$$q$$q>p$$L$$M^{\ell_q}$$M^{\ell_q}$$L$$M^{\ell_p}$$L$$NP \subseteq BQP$

(2) Was ist mit ? Hier ist der Maximalwert der Komponenten des Zustandsvektors 1.$p=\infty$

(3) Diese Fragen gehen über die Einheitlichkeit hinaus, sodass keine Übereinstimmung mit der Quantenmechanik zu erwarten ist. Was passiert im Allgemeinen mit der Berechnung, wenn Sie die Einschränkung der Einheitlichkeit für Operationen lockern? Es gibt Arbeiten zum Zulassen von nichtlinearen Operatoren (siehe Aaronson 2005 ).

(4) Vielleicht das Wichtigste, ist es universell? Ich denke, das ist klar, weil es für bestimmte Fälle universell ist. Aber was passiert mit der Universalität, wenn ?$p=\infty$

Dies ist keine vollständige Antwort auf die Fragen, aber es ist zu lang, um einen Kommentar abzugeben. Es erweitert meinen vorherigen Kommentar.

Die Frage „Was passiert mit der Berechnung, wenn die Axiome der Quantenmechanik ein wenig verändert werden?“ Wird in einem lustigen Artikel [Aar04] von Scott Aaronson ausführlich behandelt. Ich glaube, dass Ihre Fragen im Wesentlichen in der ersten Hälfte von Abschnitt 2 von [Aar04] beantwortet werden.

Aaronson zeigt, dass, wenn p> 0 und p norm 2, eine Matrix, die die p-Norm für alle Vektoren beibehält, notwendigerweise eine verallgemeinerte Permutationsmatrix ist (ein Produkt einer Permutationsmatrix und einer Diagonalmatrix). Dasselbe gilt für den Fall p = ∞. All dies gilt sowohl für über ℝ als auch für über ℂ. Beachten Sie, dass dies auch den Fall von p = 1 einschließt: Stochastische Matrizen behalten die 1-Norm für nichtnegative Vektoren bei, jedoch nicht für alle Vektoren im Allgemeinen.

Ich vermute, dass eine wie in [For00] verallgemeinerte probabilistische Turing-Maschine nur dann eine verallgemeinerte Permutationsmatrix als globale Übergangsmatrix hat, wenn es sich um eine deterministische Turing-Maschine handelt, aber ich habe keinen Beweis zur Hand.

Aaronson diskutiert auch einige andere Modifikationen der Axiome der Quantenmechanik in der Arbeit. Ändern wir beispielsweise die Messregel (anstelle der Menge der erlaubten Tore), so dass das Ergebnis x mit der Wahrscheinlichkeit | α _x | auftritt ^p / ∑ _y | α _y | ^p , wobei α _y die Amplitude von | y⟩ ist, dann kann dieser "Quantencomputer" alle Probleme in PP (einschließlich NP-vollständiger Probleme) in der Polynomzeit lösen, es sei denn, p = 2 (Satz 5).

Verweise

[Aar04] Scott Aaronson. Ist die Quantenmechanik eine Insel im theoretischen Raum? In Proceedings of the Växjö Conference, „Quantentheorie: Überprüfung der Grundlagen“, 2004. arXiv: quant-ph / 0401062 v2.

[For00] Lance Fortnow. Die Sichtweise eines Komplexitätstheoretikers auf das Quantencomputing. In Computing: das Australasian Theory Symposium (CATS 2000), S. 58–72, Januar 2000. http://dx.doi.org/10.1016/S1571-0661(05)80330-5

$p \not\in \{1,2\}$$\ell_p$$\left| \psi_i \right|^p$

$\ell_p$$\ell_1$$\ell_2$$\Omega(N^{1/p})$$\ell_\infty$$\ell_p$$\ell_q$$1/p+1/q=1$$\ell_p$$p$