Komplexität der Optimierung über eine einheitliche Gruppe

Was ist der Rechenaufwand für die Optimierung verschiedener Funktionen über die Einheitsgruppe $\mathcal{U}(n)$ ?

Eine typische Aufgabe, entstehen oft in der Theorie der Quanteninformation, würde eine Menge an Typ sein Maximierung $\mathrm{Tr}AUBU^{\dagger}$ (oder Polynome höherer Ordnung in $U$ ) über alle unitäre Matrizen $U$ . Ist diese Art der Optimierung effizient (vielleicht ungefähr) berechenbar oder ist sie NP-schwer? (Vielleicht ist das bekannt, aber ich konnte keine allgemeinen Referenzen finden.)

cc.complexity-theory reference-request optimization quantum-information Marcin Kotowski
quelle

Können Sie "verschiedene Funktionen" auf "Polynome über die Unitaries" beschränken?

Artem Kaznatcheev

Ich weiß nicht viel darüber, wie diese Probleme entstehen, aber was wäre das natürliche klassische Analogon zu diesem Problem? Kennen Sie die Komplexität dieses Problems?

Robin Kothari

Es gibt eine sehr schöne Arbeit von Roger Brockett aus dem Jahr 1991, die zeigt, wie man Sortierung und lineare Programmierung im Wesentlichen in der von Ihnen beschriebenen Form ausdrückt, jedoch über die orthogonalen Matrizen. Keine Erwähnung der Komplexität, aber die Tatsache, dass zwei sehr unterschiedliche Probleme auf dieselbe Weise ausgedrückt werden können, bedeutet, dass Sie etwas über die Problemstruktur wissen müssen, um eine Komplexitätsbestimmung vorzunehmen

Suresh Venkat

@Artem: Ja, in der Praxis sind Polynome mit niedrigem Grad meiner Meinung nach am relevantesten.

Marcin Kotowski

Es kommt auf die Eigenzerlegungen von

und

im Beispiel Grad 2 an. Für

und

Hermitian kann das einheitliche

verwendet werden, um die Spur zu maximieren, indem die Eigenräume von

mit denen von

; Es genügt dann, das Skalarprodukt der Folgen ihrer Eigenwerte zu maximieren, was trivial ist, wenn

und

positiv semidefinit sind (und ein Fall, auf den wir reduzieren können, indem wir Vielfache der Identität addieren, um Eigenwerte neu zu skalieren). Oder interessieren Sie sich für viel allgemeinere Fälle, die nicht unbedingt durch die Quantenmechanik auf kleindimensionalen Systemen motiviert sind?

A

$A$

B

$B$

A

$A$

B

$B$

U

$U$

U B U^{†}

$U B U^\dagger$

A

$A$

A

$A$

B

$B$

Niel de Beaudrap

Antworten:

Entschuldigung, ich bin zu spät! In der Quantencomputertheorie gibt es viele Beispiele für Optimierungsprobleme über die einheitliche Gruppe, die überraschenderweise (zumindest für mich) in (klassischer) Polynomzeit durch Reduktion auf semidefinite Programmierung lösbar sind.

Hier ein frühes Beispiel: Die Lösung eines meiner Probleme aus dem Jahr 2000, im Jahr 2003 , zeigte Barnum, Saks und Szegedy , dass Q (f) die Komplexität der Quantenabfrage einer Booleschen Funktion f: {0,1} ⁿ → {0,1 ist }, kann als Zeitpolynom in 2 ⁿ berechnet werden (dh die Größe der Wahrheitstabelle von f). Ich hatte darüber nachgedacht, konnte aber nicht sehen, wie es geht, da man die Erfolgswahrscheinlichkeit über alle möglichen Quantenabfragealgorithmen optimieren muss, von denen jeder seinen eigenen Satz von (möglicherweise 2 ^n- großen) Einheitsmatrizen hat. Barnum et al. reduziert auf SDP durch Ausnutzung einer "Dualität" zwischen Einheitsmatrizen und positiven semidefiniten Matrizen, dem sogenannten Choi-Jamiolkowski-Isomorphismus. Für eine neuere und einfachere SDP, die Q (f) charakterisiert, siehe Reichardts Arbeit von 2010, die zeigt, dass die Gegenmethode mit negativem Gewicht optimal ist.

Ein weiterer wichtiger Fall, in dem dieser Trick ausgenutzt wurde, sind quanteninteraktive Beweissysteme. Während es nicht intuitiv offensichtlich ist, haben Kitaev und Watrous im Jahr 2000 bewiesen, dass QIP ⊆ EXP. durch Reduzieren des Problems der Optimierung über die Einheitsmatrizen mit Exponentialgröße, die in einem interaktiven 3-Runden-Quantenbeweissystem entstehen, bis zur Lösung eines SDP mit Einfachexponentialgröße (wieder denke ich, unter Verwendung des Choi-Jamiolkowski-Isomorphismus zwischen gemischten Zuständen und einheitliche Matrizen). Der jüngste Durchbruch bei QIP = PSPACE ist darauf zurückzuführen, dass gezeigt wurde, dass dieser bestimmte SDP in NC (dh durch logarithmische Schaltungen) noch besser gelöst werden kann.

Unabhängig von Ihrem spezifischen Optimierungsproblem, das die einheitliche Gruppe betrifft, kann es vermutlich schneller gelöst werden, als Sie denken - wenn auch nicht auf eine noch einfachere Weise, dann durch Reduzierung auf SDP!

Scott Aaronson
quelle

Lieber Scott! Barnum, Saks und Szegedy erwähnen den Choi-Jamiolkowski-Isomorphismus nicht ausdrücklich, und ich verstehe nicht, wie dies mit ihrer Konstruktion zusammenhängt. Könnten Sie dies bitte näher erläutern? Ich frage, weil ich zu verstehen versuche, ob bei fehlerhaften Orakeln ein ähnliches Ergebnis möglich ist.

Joris

-3

Die Bestimmung, ob zwei Hadamard-Matrizen äquivalent sind, ist ein vollständiges Problem des Graph-Isomorphismus (GI). Brendon McKay hat einen Artikel zu diesem Thema. Siehe BD McKay, Hadamard-Äquivalenz über Graphisomorphismus, Discrete Mathematics, 27 (1979) 213-216.

Dursun
quelle

das steht nicht in der Zeitung. Die Zeitung handelt von "Hadamard-Äquivalenz" von 20.03 Uhr

\pm 1

$\pm 1$