Reduzierung des Protokollbereichs von Parity-L zu CNOT-Schaltkreisen?

14

Frage.

In ihrer Arbeit Verbesserte Simulation von Stabilisatorschaltungen behaupten Aaronson und Gottesman, dass die Simulation einer CNOT-Schaltung ⊕L- vollständig ist (unter logspace Reductions). Es ist klar, dass es in ⊕L enthalten ist ; Wie hält das Härteergebnis?

Äquivalent: Gibt es eine logarithmische Reduktion von iterierten Matrixprodukten modulo 2 zu iterierten Produkten von Elementarmatrizen (den invertierbaren Matrizen, die Zeilentransformationen realisieren) mod 2?

Einzelheiten

Eine Controlled-NOT- Operation (oder CNOT- Operation) ist eine reversible Boolesche Operation der Form wobei nur dasj- te Bit geändert wird und dieses Bit durch Addieren von x h modulo 2 für beliebige unterschiedliche Positionenhundjgeändert wird. Es ist nicht schwer zu erkennen, ob wir x = ( x 1 interpretieren

CNOTh,j(x1,…,xh,…,xj,…,xn)=(x1,…,xh,…,xj⊕xh,…,xn)
xh als Vektor über ℤ / 2ℤ, dh dies entspricht einer elementaren Zeilentransformation modulo 2, die wir durch eine Matrix mit 1s auf der Diagonale und einer einzelnen nichtdiagonalen Position darstellen können. EineCNOT-Schaltungist dann ein Matrixprodukt, das aus einem Produkt einiger elementarer Matrizen dieses Typs besteht.x=(x1,…,xn)

Die oben erwähnte Arbeit von Aaronson und Gottesman (die im Übrigen zu dieser Frage eine Klasse von Quantenschaltungen betrifft , die in ⊕L simuliert werden können ) enthält einen Abschnitt über die Komplexität von Berechnungen. Zu Beginn dieses Abschnitts beschreiben sie ⊕L wie folgt:

⊕L [ist] die Klasse aller Probleme, die durch eine nicht deterministische logarithmische Raum-Turing-Maschine lösbar sind, die genau dann akzeptiert, wenn die Gesamtzahl der akzeptierenden Pfade ungerade ist. Es gibt jedoch eine alternative Definition, die für Nicht-Informatiker wahrscheinlich intuitiver ist. Dies ist, dass & Dgr ; L die Klasse von Problemen ist, die sich auf die Simulation einer polynomgroßen CNOT-Schaltung reduzieren, dh  einer Schaltung, die vollständig aus NOT- und CNOT-Gattern besteht und auf den Anfangszustand | 0 ... 0 & Dgr; einwirkt. (Es ist leicht zu zeigen, dass die beiden Definitionen gleichwertig sind, aber dazu müssten wir zunächst erklären, was die übliche Definition bedeutet!)

Die Zielgruppe des Artikels umfasste eine beträchtliche Anzahl von Nicht-Informatikern, so dass der Wunsch, sich zu entledigen, nicht unzumutbar ist. Ich hoffe, jemand kann klären, wie diese Äquivalenz gilt.

Es ist klar, dass die Simulation eines Produkts solcher Matrizen in ⊕L als Spezialfall für die Bewertung von Koeffizienten iterierter Matrixprodukte (mod 2) durchgeführt werden kann, was für ⊕L ein vollständiges Problem darstellt (unter logspace reductions) . Da die CNOT-Matrizen nur Elementarzeilenoperationen ausführen, kann darüber hinaus jede invertierbare Matrix als Produkt von CNOT-Matrizen zerlegt werden. Allerdings: Es ist mir nicht klar, wie man selbst eine invertierbare Matrix mod 2 durch eine logspace-Reduktion in ein Produkt von CNOT-Matrizen zerlegt . (Wie Emil Jeřábek in den Kommentaren bemerkte, reicht die Gaußsche Eliminierung aus, um die Determinanten mod 2 zu berechnen, was ein ⊕L- vollständiges Problem ist: also ein direkter Angriff durch Zersetzung von z invertierbare Matrizen als Produkte von Elementarmatrizen scheinen im logarithmischen Raum nur dann realisierbar zu sein, wenn L  =  ⊕L .) Ganz zu schweigen von Matrixprodukten, die nicht invertierbar sind. Es scheint also eine klügere Reduzierung erforderlich zu sein.

Ich hoffe, jemand kann eine Skizze dieser Reduktion oder einen Verweis liefern ( z. B.  einen Text, für den dies eine Übung ist, wenn es einfach ist).

cc.complexity-theory counting-complexity linear-algebra logspace Niel de Beaudrap
quelle
2
Ich nehme an, dass die Berechnung der Determinanten mod ebenfalls ⊕L-vollständig ist, daher ist die Gaußsche Eliminierung mod 2 ⊕L-hart. 22
Emil Jeřábek unterstützt Monica
1
@ EmilJeřábek: Ich denke über Ihre Bemerkung nach und versuche zu sehen, ob dies sofort impliziert, dass die Simulation von CNOT-Schaltkreisen für ⊕L nicht abgeschlossen ist, es sei denn, L = ⊕L . (Betrachten Sie ein Produkt einer Matrix oder ein Produkt einer einzelnen Matrix mit der Identitätsmatrix!) Dies scheint fast zu einfach; Vermisse ich etwas? Ich nehme an, dass es nur viele-zu-eins-Reduzierungen ausschließt.
Niel de Beaudrap
1
Ich denke nicht, dass es so einfach ist. ⊕L ist eine Klasse von Entscheidungsproblemen, während die Matrixmultiplikation über F_2 ein Funktionsproblem ist. Die ⊕L-Version der Matrixmultiplikation fordert ein bestimmtes Bit des Ergebnisses an (z. B. den linken oberen Eintrag der Matrix). Kann es einen Logspace-Algorithmus geben, der eine Folge von Matrizen nimmt und eine Folge von Elementarmatrizen erzeugt, so dass die Produkte beider Folgen das gleiche Element oben links haben? Dies ist viel schwächer als eine echte Gaußsche Eliminierung. Eigentlich klingt die Behauptung von Aaronson und Gottesman für mich plausibel, obwohl ich nicht sicher bin, wie ich es beweisen soll.
Emil Jeřábek unterstützt Monica
1
@ EmilJeřábek: Ich denke darüber nach, wie die meisten ⊕L- Entscheidungsprobleme auf der Überprüfung einzelner Problemkoeffizienten beruhen, die für DET natürlich sind (es ist üblich, Funktionsprobleme als asL- vollständig zu bezeichnen, jedoch als Missbrauch von ofL Terminologie das ist); und meine Intuition für Matrixprodukte ist, dass es so kompliziert ist, dass es schwierig ist, für einen einzelnen Koeffizienten ad-hoc zu arrangieren , dass zwei Matrixprodukte für diesen Koeffizienten so gleich sein sollten, dass Sie nicht ganz sicher sein können dass auch alle anderen Koeffizienten übereinstimmen.
Niel de Beaudrap
2
Ich habe es verstanden: Das Zählen der akzeptierten Pfade einer Logspace-Maschine entspricht dem Zählen der Pfade in einem azyklischen Graphen, der durch Multiplikation der oberen dreieckigen Matrizen mit 1 auf der Diagonale dargestellt werden kann. Letztere lassen sich ohne Gaußsche Eliminierung leicht explizit als Produkt elementarer Matrizen ausdrücken.
Emil Jeřábek unterstützt Monica

Antworten:

9

Beginnen wir mit dem -kompletten Problem des Zählens von mod 2 der Anzahl der Pfade der Länge n vom Scheitelpunkt s zum Scheitelpunkt t in einem gerichteten Graphen G = ( V , E ) . Wir wenden einige logspace Verkleinerungen wie folgt an.⊕L2nstG=(V,E)

Sei der Graph, so dass V ' = V × { 0 , … , n } und E ' = { ( ( u , i ) , ( v , i + 1 ) : i < n , ( u , v ) ∈ E } ∪ { (G′=(V′,E′)V′=V×{0,…,n} (dh wir nehmen n + 1 Kopien von Gs Eckpunkten, lassen Kanten von der i- ten Kopie zur ( i + 1 ) -ten Kopie gemäß Gs Kanten gehen, und alle Self-Loops hinzufügen). Dann ist das ursprüngliche Problem gleichbedeutend mit dem Zählen von Pfaden der Länge n von s ' = ( s , 0 ) bis t ' = ( t , n ).E′={((u,i),(v,i+1):i<n,(u,v)∈E}∪{(w,w):w∈V′}n+1Gi(i+1)Gns′=(s,0)t′=(t,n)in .G′

Außerdem ist azyklisch und wir können explizit eine Aufzählung V ' = { w k : k ≤ m } definieren, so dass alle Kanten in G 'mit Ausnahme der Selbstschleifen für einige k < l von w k nach w l gehen . Ohne Verlust der Allgemeinheit gilt w 0 = s ' und w m = t ' . Sei M die Adjazenzmatrix von G 'G′V′={wk:k≤m}G′wkwlk<lw0=s′wm=t′MG′Beziehen Sie sich auf die angegebene Aufzählung. Dann ist eine obere dreieckige Ganzzahlmatrix mit 1 auf der Diagonale, und die Anzahl der Pfade der Länge n von s ' bis t ' ist gleich dem oberen rechten Element von M n .M1ns′t′Mn

Es ist leicht zu sehen , dass wobei E i , j ( a ) ist die Elementarmatrix , deren einzigen nicht diagonalen Eintrag ist ein in reihe i und spalte j . Auf diese Weise haben wir das ursprüngliche Problem auf die Berechnung des oberen rechten Elements eines Produkts von Elementarmatrizen reduziert. In der ⊕ L

M=∏j=m1∏i=0j−1Ei,j(Mi,j),
Ei,j(a)aij⊕LIn diesem Fall ist die Berechnung Modulo , dh wir betrachten die Matrizen über F 2 . (In diesem Fall können die Elementarmatrizen nur E i , j ( 0 ) = I sein , die wir ignorieren können, und E i , j ( 1 ) , die von einem einzelnen CNOT-Gatter simuliert werden können, wie in der Frage erwähnt .) Wenn wir sie als ganzzahlige Matrizen betrachten, erhalten wir ein # L- vollständiges Problem, und wenn wir sie als modulo k betrachten , erhalten wir ein M o d k L- vollständiges Problem.2F2Ei,j(0)=IEi,j(1)#LkModkL
Emil Jeřábek unterstützt Monica
quelle
1
Ich meine, es ist -komplett für Elementarmatrizen mit nichtnegativen ganzzahligen Koeffizienten. Mit beliebigen ganzen Zahlen ist es DET-vollständig. #L
Emil Jeřábek unterstützt Monica
Das Folgende ist wahrscheinlich Standard, aber ich hatte es vorher nicht explizit gesehen: Um zu zeigen, dass das Finden der Anzahl der Pfade mit der Länge n in einem (möglicherweise zyklischen) Digraphen ⊕L- vollständig ist, ist zu beachten, dass es sich um Berechnungskoeffizienten von einigen handelt Leistung einer beliebigen Matrix über , das ist ⊕L -komplette. Diese Antwort ist dann im wesentlichen eine Reduktion von der Matrixversorgung (unter Verwendung einer Standardkonstruktion von M als Blockmatrix, die nur aus Kopien der willkürlichen Adjazenzmatrix von G in den oberen nicht diagonalen Blöcken und 1 in der Diagonale besteht) zu CNOT-Schaltungen . Gute Antwort! F2
Niel de Beaudrap
Sie müssen kein Matrix-Powering durchlaufen, dessen ⊕L-Vollständigkeit schwerer zu beweisen ist. ⊕L wird durch Zählen von mod 2 der akzeptierenden Pfade eines nichtdeterministischen Lograums definiert machine (es ist einfach zu arrangieren, dass alle Pfade in der gleichen Konfiguration enden und dass die Pfade die gleiche Länge haben, indem die Maschine in eine Schleife geschaltet wird, bis ihre Uhr abläuft, und dann in einen festen Akzeptanzzustand übergeht).
Emil Jeřábek unterstützt Monica
Ich nehme an, dass durch die Fokussierung auf die Ideen in der Arbeit Struktur und Bedeutung der Logspace-MOD-Klassen von Buntrock et al. Ich habe mich viel mehr daran gewöhnt, in einem azyklischen Digraphen über die Anzahl der Pfade beliebiger Länge und die damit natürlich verbundenen DET- ähnlichen Probleme wie Matrixprodukte und Potenzen nachzudenken .
Niel de Beaudrap