Ein Begriff von monotonen Quantenschaltungen

27

In der Rechenkomplexität gibt es einen wichtigen Unterschied zwischen monotonen und allgemeinen Berechnungen, und ein berühmter Satz von Rasborow besagt, dass 3-SAT und sogar MATCHING im monotonen Booleschen Schaltungsmodell nicht polynomisch sind.

Meine Frage ist einfach: Gibt es ein Quantenanalog für monotone Schaltungen (oder mehr als eine)? Gibt es ein Quanten-Razborov-Theorem?

Gil Kalai
quelle
10
Hier sind meine zwei Cent: Der Sprung von klassischen Schaltungen zu Quantenschaltungen kann in zwei Schritte unterteilt werden, indem klassische umschaltbare Schaltungen in der Mitte hinzugefügt werden. Klassische umschaltbare Schaltungen sind solche, bei denen nur umschaltbare Gatter zulässig sind. Zum Beispiel ist das Toffoli-Tor ein universelles Tor für reversible Berechnungen. Ich weiß nicht, wie ich den Begriff Monoton für diese Schaltkreise definieren soll. Die Definition monotoner klassischer reversibler Schaltkreise scheint mir eine Voraussetzung für die Definition monotoner Quantenschaltungen zu sein.
Robin Kothari
6
(1) Eine (klassische) umschaltbare Schaltung implementiert eine Bijektion auf {0,1} ^ n, und die einzige monotone Bijektion ist eindeutig die Identitätsabbildung. Ich halte es daher nicht für sinnvoll, „monotone reversible Schaltkreise“ auf nichttriviale Weise zu definieren.
Tsuyoshi Ito
3
(2) Ich bin mir über den Quantenfall nicht sicher. Wenn wir "monotone Quantenkanäle" definieren können, ist es selbstverständlich, "monotone Quantenkreise" als Quantenkreise zu definieren, deren Gate-Set aus monotonen Quantenkanälen ausgewählt wird, genauso wie monotone klassische Schaltkreise Schaltkreise sind, deren Gate-Set aus monotonen Funktionen ausgewählt wird .
Tsuyoshi Ito
2
@RobinKothari, TsuyoshiIto: Die Bedeutung der Reversibilität für die Quantenberechnung ergibt sich genau aus dem Sonderfall der Schrödinger-Evolution eines geschlossenen Systems. Wenn wir jedoch von UND- und ODER-Gattern sprechen, betrachten wir ein abstraktes physikalisches System, das eine Karikatur der Logikgatter ist, die sich in Computern befinden. Und diese Tore funktionieren genau deshalb, weil sie keine geschlossenen Systeme sind. Wenn wir uns erlauben, von UND- und ODER-Gattern per se zu sprechen, halte ich es für vernünftig, die Konvention aufzuheben, geschlossene Systeme auch für die Quantenrechenfrage zu berücksichtigen.
Niel de Beaudrap
3
@Niel, Tsuyoshi: Ich glaube, ich dachte, dass ein monotoner Quantenschaltkreis immer noch ein Quantenschaltkreis im herkömmlichen Sinne ist (dh Unitaries, gefolgt von einer Messung). Nach Niels Argumentation ist es jedoch sinnvoll, diese Einschränkung aufzuheben. Mein vorheriger Kommentar trifft also nicht wirklich zu.
Robin Kothari

Antworten:

17

Sie stellen wirklich zwei verschiedene Fragen und hoffen, dass es eine einzige Antwort gibt, die beide beantwortet: (1) Welche natürlichen Vorstellungen von quantenmonotonen Schaltkreisen gibt es? (2) Wie würde ein gitterbasiertes Quantenergebnis im Razborov-Stil aussehen?

Es ist nicht offensichtlich, wie beides gleichzeitig erreicht werden kann, daher beschreibe ich, was für mich eine vernünftige Vorstellung von monotonen Quantenschaltungen ist (ohne anzugeben, ob es ein entsprechendes Razborov-Ergebnis gibt oder nicht), und eine völlig andere Vorstellung von wie eine "natürliche" Quanten-Razborov-Vermutung aussehen würde (ohne anzugeben, ob es wahrscheinlich wahr ist).

Was wir von Quanten wollen

Wie ich in den Kommentaren bemerkte, denke ich, dass es nicht notwendig ist, den Begriff der monotonen Schaltkreise in eine Form der Einheitlichkeit zu bringen. Ob es nun darum geht, dass die zeitliche Entwicklung nicht die Standardbasis bewahren muss oder dass es mehrere Messgrundlagen gibt, in die die Ergebnisse verwickelt sein können, ich denke, die unabdingbare Voraussetzung für die Quantenberechnung ist die Tatsache, dass die Standardbasis ist nicht die einzige Basis. Sogar unter den Produktzuständen wird es in einigen Implementierungen nur durch eine Wahl des Bezugsrahmens definiert.

Was wir tun müssen, ist, die Dinge so zu betrachten, dass die Standardbasis von ihrem traditionellen privilegierten Platz entfernt wird - oder in diesem Fall so weit wie möglich, während ein bedeutungsvoller Begriff von Monotonie beibehalten wird.

Ein einfaches Modell von monotonen Quantenschaltungen

Betrachten Sie ein Schaltungsmodell, das in Tsuyoshi Itos Kommentar über "monotone Quantenkanäle" impliziert ist (und das so ziemlich das ist, was man tun muss, wenn man einen Begriff von "einer Schaltung" haben möchte, der nicht auf die einheitliche Evolution beschränkt ist).

Sei der Raum der Hermitianischen Operatoren auf (so dass er alle Dichteoperatoren auf einem Qubit enthält). Wie definieren wir ein Quantenmonoton-Gatter von zwei Eingangs-Qubits bis zu einem Ausgangs-Qubit , so dass es kein klassisches ist monotones Tor? Ich denke, es ist einfach zu sagen, dass die Ausgabe nicht aufoderoder Mischungen davon; Wenn dies "monoton" sein soll, sollten wir dies als fordern und C 2 G : H aH bH c a , b c | 0 HC2G:HaHbHca,bc| 1 |00|1 ||11|1|1|Tra(ρab)|11| G(ρ a b )| 1G1|Trb(ρab)|1 erhöhe den Wert von darf nicht abnehmen. Für ein Qubit-Gatter mit zwei Eingängen bedeutet dies, dass im Prinzip wie implementierbar sein muss1|G(ρab)|1G

  1. Durchführen einer Zwei-Qubit-Messung in Bezug auf eine orthonormale Basis , wobei überspanne den Unterraum von Hamminggewicht 1 und| & mgr; , | & ngr; {|00,|μ,|ν,|11}|μ,|ν

  2. Als Ausgabe wird ein Zustand , der dem gemessenen Ergebnis entspricht, wobei für jedes .ρ{ρ00,ρμ,ρν,ρ11}1|ρ00|11|ρλ|11|ρ11|1λ{μ,ν}

Die Schaltkreise sind sinnvollerweise nur Kompositionen davon. Wir könnten auch Fan-Out in Form von Schaltkreisen zulassen, die einheitlich und einbetten ; Wir sollten diese Maps zumindest am Eingang zulassen, damit jedes (nominell klassische) Eingabebit kopiert werden kann.|0|000|1|111

Es erscheint vernünftig, entweder das gesamte Kontinuum solcher Tore zu betrachten oder sich auf eine begrenzte Sammlung solcher Tore zu beschränken. Jede Wahl führt zu einer anderen "Quantenmonoton-Gate-Basis" für die Schaltungen; man kann überlegen, welche Eigenschaften verschiedene monotone Basen haben. Die Zustände können unter Berücksichtigung der Monotoniebedingung völlig unabhängig voneinander ausgewählt werden. Es wäre zweifellos interessant (und wahrscheinlich praktisch, Fehler zu binden),und, obwohl ich keinen Grund sehe, dies in der Theorie zu fordern. Offensichtlich sind AND und OR Tore dieses Typs, bei denenundρ00,ρμ,ρν,ρ11ρ00=|00|ρ11=|11|ρμ=ρν=|00|ρμ=ρν=|11|jeweils, was auch immer man wählt, um oder zu sein.|μ|ν

Für jede Konstante k könnte man auch Gate-Basen in Betracht ziehen, einschließlich k- Input-One-Output-Gates. Der einfachste Ansatz in diesem Fall wäre wahrscheinlich, Gates zuzulassen, was wie oben implementiert werden kann, was jede Zerlegung der Teilräume jedes Hamming-Gewichts , und zu fordern, dass für jedenG:HkHVwH2k0wk

max|ψVw1|G(|ψψ|)|1min|ψVw+11|G(|ψψ|)|1
0w<k . Es ist nicht klar, wie viel zusätzliche Rechenleistung Ihnen dies geben würde (auch nicht im klassischen Fall).

Ich weiß nicht, ob es etwas Interessantes gibt, über solche Schaltkreise jenseits des klassischen Falls zu sagen, aber dies scheint mir die vielversprechendste Kandidatendefinition eines "Quantenmonoton-Schaltkreises" zu sein.

Eine Quantenvariante von Rasborows Ergebnis

Betrachten Sie die Darstellung der Ergebnisse von Alon & Boppana (1987), Combinatorica 7, S. 1–22 durch Tim Gowers , die Razborovs Ergebnisse für die monotone Komplexität von CLIQUE stärken (und einige seiner Techniken explizit machen). Gowers stellt dies in Form einer rekursiven Konstruktion einer , die aus den "Halbräumen" des Booleschen Würfels für jedes . Wenn wir die privilegierte Position der Standardbasis in den Basissätzen entfernen , können wir in Analogie zum Quantum Lovász Local Lemma einen Unterraum von

Ej={x{0,1}n:xj=1}
1jnH2neinem binären Satz zu entsprechen (ob ein Zustand zum Unterraum gehört oder stattdessen orthogonal dazu ist), der sich aus der Messung ergeben könnte. Zum Beispiel können wir Teilräume die durch Wir erlauben die quantenlogischen Analoga der Konjunktion und Disjunktion von Subspaces: nAjH2n
Aj=UjEj, for each 1jnwhere Ej:={|x:xEj};Uj:H2nH2n a unitary of bounded complexity.
AB=AB;AB=A+B={a+b:aA,bB}.
Wir fragen dann, wie lange eine rekursive Konstruktion von Konjunktionen und Disjunktionen von Räumen erforderlich ist, um einen Raum , so dass sich der Projektor auf nur geringfügig vom Projektor auf den durch die Indikatorfunktionen von Graphen mit Cliquen der Größe aufgespannten Raum ; zum Beispiel, damitCΠCCΠK(r)rΠCΠK(r)<1/poly(n). Der monotone Teil ist an den quantenlogischen Operationen beteiligt, und die primitiven Aussagen über die Eingabe sind ebenfalls Quanten.

Im allgemeinen Fall besteht ein Problem darin, dies als Rechenproblem zu behandeln: Die Disjunktion entspricht keinem Wissen, das mit Sicherheit durch Messungen an einer begrenzten Anzahl von Kopien unter Verwendung von Black-Box-Messungen für und allein, es sei denn, es handelt sich um Bilder von Pendelprojektoren. Dieses allgemeine Problem kann immer noch als interessantes Ergebnis der geometrisch-kombinatorischen Komplexität betrachtet werden und kann zu Ergebnissen führen, die mit frustrierten lokalen Hamiltioniern zusammenhängen. Es könnte jedoch natürlicher sein, nur die SubspacesABAjentstehen durch Pendeln von Projektoren. In diesem Fall ist die Disjunktion nur der klassische ODER der Messergebnisse dieser Projektoren. Dann können wir verlangen, dass die Unitaries alle gleich sind, und dies wird zu einem Problem in eine Unitary Circuit (die die "primitiven Ereignisse" hervorruft) mit monotoner klassischer Nachbearbeitung (die die logischen Operationen für diese Ereignisse ausführt).Uj

Beachten Sie auch, dass, wenn wir keine weiteren Einschränkungen für die Leerzeichen , dies ein Unterraum mit sehr großer Überlappung mit einigen Leerzeichen , die von den Standardbasiszuständen werden. Welches sind die binären Zeichenfolgen, in denen .AjEkxE¯kxk=0

  • Wenn diese Möglichkeit macht squeamish, kann man immer , dass erfordern hat einen Winkel von Trennung von jedem mindestens (damit unsere primitiven Unterräume im schlimmsten Fall in etwa unabhängig von den Unterräumen sind, in denen eines der Bits auf 1 gesetzt ist).AjEkπ21/poly(n)

  • Wenn wir keine solche Einschränkung auferlegen, scheint es mir ohnehin ein Hindernis für die Annäherung an CLIQUE (r) zu sein, wenn Subspaces mit hoher Überlappung mit werden; Entweder wären wir mehr oder weniger darauf beschränkt, das Fehlen einer bestimmten Kante (und nicht deren Vorhandensein) zu berücksichtigen , oder wir wären gezwungen, eine der Kanten insgesamt zu ignorieren. Daher halte ich es nicht für furchtbar wichtig, irgendwelche Einschränkungen , außer möglicherweise, dass sie alle die Bilder eines pendelnden Satzes von Projektoren sind, wenn man , wie man CLIQUE aus einfachen Quantensätzen monoton auswertet ". Im schlimmsten Fall würde dies klassisch bedeuten, NICHT-Gatter am Eingang zuzulassen (und alle Fan-Outs nach der Negation zuzulassen).EkAj

Auch hier ist mir nicht klar, ob das Ersetzen der Basismengen durch beliebige Unterräume von zu einem interessanteren Problem führt als nur die Verwendung der Unterräume ; Wenn wir uns jedoch auf den Fall von CNF-Formeln beschränken (entweder im Fall des Pendelns oder im Fall des Nicht-Pendelns), würden die Ergebnisse einer Vorstellung von der Komplexität eines frustrationsfreien Hamiltonianers entsprechen, dessen Grundzustandsvielfalt aus einer Standardbasis bestand Staaten, die Cliquen vertreten.H2nEj

Niel de Beaudrap
quelle
Ihre Skizze lässt mich wundern. Gibt es ein Konzept der Monotonie für komplexe Werte? vielleicht werden die reellen Rechenschaltungen noch etwas genauer studiert. könnte es etwas Einfaches sein wie<? oder für ein komplexes Gatter mit zwei Eingängen und als Eingaben, Ausgabe,und? |x||y|x1x2y|y|>|x1||y|>|x2|
vzn
Hoppla, ich habe einen Fehler gemacht ... Ich wollte Niel das Kopfgeld geben, habe aber auf die falsche Stelle geklickt. Ich schulde dir 200 Ruf Niel :).
Gil Kalai
Kann ich es auf irgendeine Weise an Niel weitergeben?
Joe Fitzsimons
@Joe, du kannst der Frage ein neues Kopfgeld geben und sie Niel zuweisen.
Kaveh
@ Kaveh: Okay, werde tun. Ich kann es nicht für 24 Stunden vergeben, werde es dann aber vergeben.
Joe Fitzsimons
7

Wie aus den Kommentaren von Robin und Tsuyoshi hervorgeht, scheint der Begriff monotone Schaltkreise leicht auf Quantenschaltungen erweiterbar zu sein.

Um eine aussagekräftige Definition der Quantenmonotonschaltung zu erhalten, müssen wir eine Reihenfolge der Quantenzustände auswählen, für die die Monotonie definiert ist. Klassisch eine vernünftige Option (und eine, die zum normalen Begriff der monotonen Schaltkreise führt), ist das Hamming-Gewicht, aber lassen Sie uns eine durch eine beliebige Funktion gegebene Reihenfolge .f

Da die Entwicklung eines geschlossenen Quantensystems einheitlich ist (was wir durch annehmen können ), gilt für jeden Zustand so dass Es gibt einen alternativen Zustand so dass aber für den , und daher ist die Evolution nicht monoton.U|ψf(U|ψ)>f(|ψ)|ϕf(|ϕ)>f(|ψ)f(U|ψ)>f(U|ϕ)U

Somit sind die einzigen Schaltkreise, die in Bezug auf monoton sind, diejenigen, bei denen für alle . Somit setzt sich jede Tormenge, die in Bezug auf monoton ist, aus Toren zusammen, die mit pendeln .ff(U|ψ)=f(|ψ)|ψff

Offensichtlich hängen die Sätze von Toren, die dies erfüllen können, von der Definition von . Wenn konstant ist, sind alle Torsätze in Bezug darauf monoton. Wenn wir jedoch als Hamming-Gewicht von Zuständen in der Berechnungsbasis wählen (eine etwas natürliche Erweiterung des im klassischen Fall verwendeten ), erhalten wir eine interessante Struktur. Die auferlegte Beschränkung erfordert, dass das Hamming-Gewicht unverändert bleibt. Die Operationen, bei denen dies beibehalten wird, sind entweder diagonale Operationen oder partielle SWAPs oder Kombinationen davon. Diese Struktur kommt in der Physik ziemlich häufig vor (in engen Bindungsmodellen usw.) und ähnelt dem von Aaronson und Arkhipov untersuchten Problem der Bosonenstreuungffff, obwohl nicht identisch (es ist ein etwas anderes Streuproblem). Außerdem enthält es Schaltkreise für IQP und sollte daher klassisch nicht effizient simulierbar sein.

Joe Fitzsimons
quelle
1
(1) Ich glaube nicht, dass Ihr Begriff "Quantenmonoton" eine Verallgemeinerung des Begriffs der Monotonie für klassische Boolesche Funktionen ist. Beispielsweise ist das UND-Gatter monoton, weil x_1 ≤ y_1 und x_2 ≤ y_2 AND (x_1, x_2) ≤ AND (y_1, y_2) implizieren, wobei x_1, x_2, y_1, y_2 ≤ {0,1}. Beachten Sie, dass der Vergleich zwischen zwei Eingaben oder zwischen zwei Ausgaben und nicht zwischen Eingabe und Ausgabe erfolgt.
Tsuyoshi Ito
(2) Nur für den Fall, ich habe nicht gesagt, dass sich der Begriff monotone Schaltkreise nicht leicht auf Quantenschaltungen erstreckt (und ich habe auch nicht gesagt, dass dies der Fall ist). Ich habe gerade gesagt, dass im Vergleich zu reversiblen Schaltungen, bei denen der Begriff monotone Schaltungen uninteressant ist, der Fall von Quantenschaltungen unklar ist.
Tsuyoshi Ito
1
@JoeFitzsimons: Ich denke, das Hamming-Gewicht passt ziemlich gut zur Monotonie-Anforderung, oder (genauer), dass die Eigenschaft, nicht abzunehmen, wenn Sie Bits von Null auf Eins "einschalten", genau der Begriff ist, den Informatiker interessieren wenn sie sich auf monotone Schaltkreise beziehen. Sie können Variationen in Betracht ziehen, bei denen die berechnete Funktion eine nicht abnehmende Funktion einiger reeller Funktionen der Bitfolgen ist, z. B. Ihr Vorschlag zur Neuindizierung. Dies ist jedoch auch eine signifikante Abweichung von dem, woran Informatiker interessiert sind, mit Ausnahme stark motivierter Fälle.
Niel de Beaudrap
1
Die übliche Teilreihenfolge von Bit-Strings (der elementweise Vergleich) sieht für mich viel natürlicher aus als der Vergleich anhand ihrer Hamming-Gewichte. Wenn Sie jedoch der Meinung sind, dass das Hamming-Gewicht natürlich ist, werde ich nicht argumentieren. Was den dritten Absatz betrifft, habe ich immer noch Schwierigkeiten, Ihrem Argument zu folgen, aber ich vermisse etwas Einfaches, und ich brauche nur etwas Zeit und einen neuen Blick darauf.
Tsuyoshi Ito
1
@NieldeBeaudrap: Ich stimme zu. Ich wollte nicht vorschlagen, dass ich etwas anderes dachte.
Joe Fitzsimons
-6

Sie stellen im Grunde genommen zwei Fragen mit sehr unterschiedlichen Schwierigkeitsgraden an der Grenze zweier großer Felder, nämlich Boolesche Schaltkreise und QM-Berechnung, nach der Möglichkeit, was in der Mathematik manchmal als "Brückentheorem" bezeichnet wird:

  • Quantenanalog von monotonen Schaltungen

  • Quantenanalogon von Razborovs thm

Die kurze offene Antwort ist nein oder noch nicht .

denn (1), eine nicht so schwierige, aber anscheinend selten berücksichtigte Frage, ergab die folgende Bezugnahme, die in der Literatur als verwandter Fall angesehen werden könnte.

Approximationshärte für Quantenprobleme nach Gharibian und Kempe

sie betrachten einige "monotone" Probleme in einem Quantenkontext, zB QMSA, "Quantum Monotone Minimum Satisfying Assignment, QMSA", dh ein SAT-QM-Analogon; (auch ein anderes Problem Quantum Monotone Minimum Weight Word, QMW) und zeigen einige Annäherungsergebnisse der Härte, dh untere Schranken. Sie betrachten keine monotonen Quantenschaltungen an sich, aber eine Idee könnte sein, dass eine Quantenschaltung oder ein Algorithmus, der die monotone Funktion QMSA löst , als QM-Analog genommen werden kann.

Was (2) anbelangt, so wäre es ein sehr fortgeschrittenes Ergebnis, wenn es existiert, was es "bisher" nicht zu sein scheint. Razborovs THM ist im Grunde genommen ein Ergebnis vom Typ "Flaschenhals" mit einer Untergrenze, das als eindeutiger Durchbruch und nahezu konkurrenzloses Ergebnis in der (monotonen) Schaltungstheorie angesehen wird.

Ja, grob gesagt gibt es natürlich einige Engpässe bei der QM-Berechnung, z. B. im Zusammenhang mit direkten Produktsätzen. Für eine Übersicht siehe z

Quantenalgorithmen, untere Schranken und Zeit-Raum-Kompromisse von Spalek

Eine wohl bessere analoge QM-Berechnung würde jedoch die Anzahl der QM- Operationen verringern oder möglicherweise auf "vollständigen" Gattern wie Toffoli-Gattern für eine monotone Funktion basieren. Beweise dieser Art sind mir nicht bekannt.

Ein anderer Ansatz könnte die Analyse auf spezielle UND- und ODER-Gatter mit zusätzlichen "Ancilla" -Bits beschränken, um die Gatter reversibel zu machen.

vzn
quelle
ps es ist auch interessant zu bemerken, dass es sich bei razborovs thm um sogenannte "Approximator" -Schaltungen / Gatter handelt und die Approximationshärte wahrscheinlich / anscheinend mit dem Konzept der Approximatorschaltung / des Gatters auf eine Weise verbunden ist, die nicht abgebildet wurde ....
vzn
6
Anstatt Kommentare hinzuzufügen, würde ich mich um die 7 Ablehnungen kümmern ...
Alessandro Cosentino
2
??? schuldig bis als unschuldig erwiesen? =)
vzn