Geometrisches Bild hinter Quantenexpandern

17

(auch hier gefragt , keine Antworten)

Ein -Quantenexpander ist eine Verteilung über die Einheitsgruppe mit der Eigenschaft, dass: a) , b) , wobei \ mu_H das Haar-Maß ist. Wenn wir anstelle von Verteilungen über Unitaries Verteilungen über Permutationsmatrizen betrachten, ist es nicht schwer zu erkennen, dass wir die übliche Definition eines d- regulären Expandergraphen wiederfinden. Weitere Hintergrundinformationen finden Sie unter anderem unter Efficient Quantum Tensor Product Expanders und k-designs von Harrow and Low.(d,λ)νU(d)|supp ν|=dEUνUUEUμHUUλμHd

Meine Frage ist - lassen Quantenexpander eine Art geometrische Interpretation zu, die klassischen Expandern ähnelt (wo spektrale Lücke isoperimetry / Expansion des zugrunde liegenden Graphen)? Ich definiere "geometrische Realisierung" formal nicht, aber konzeptionell könnte man hoffen, dass rein spektrale Kriterien in ein geometrisches Bild übersetzt werden können (das im klassischen Fall die Quelle des mathematischen Reichtums ist, den Expander genießen; mathematische Struktur des Quantums) Expander scheinen viel begrenzter zu sein).

Marcin Kotowski
quelle
8
Vielleicht lauert darunter eine einfachere Frage? Mit dem Laplace-Wert eines Graphen ist ein natürlicher Zufallslauf verbunden, und die Eigenwerte des letzteren geben Aufschluss über die Vermischung des ersteren. Es ist diese "geometrische" Ansicht von zufälligen Wanderungen (in Bezug auf die Wärmediffusion), die uns hilft, Expander im klassischen Fall zu interpretieren. Gibt es einen ähnlichen Zusammenhang zwischen zufälligen Quantenläufen und Eigenschaften assoziierter Hadamard-Matrizen?
Suresh Venkat

Antworten:

7

[Diese Antwort wurde von meiner Antwort auf der jetzt nicht mehr existierenden theoretischen Physikstapel-Austauschstelle kopiert.] Für klassische Expander kann die Spektraldefinition als zweitkleinster Eigenwert des Laplace-Graphen ausgedrückt werden, der als Minimum von angenommen werden kann eine quadratische Form über alle Einheitsvektoren, die orthogonal zum Einsenvektor sind. Beschränkt man diese Minimierung auf Vektoren der Form (a, a, ..., a, b, b, ..b), so ergibt sich die Kantenexpansion des Graphen. Hier ist eine Diskussion. Die grobe Äquivalenz dieser beiden Definitionen ist als Cheeger-Ungleichung bekannt .

Dies legt nahe, dass wir für den Quantenfall die Wirkung des Kanals (gebildet durch Anwenden einer zufälligen Einheit vom Expander) auf Projektoren betrachten sollten. Ein zu Cheegers Ungleichung analoges Ergebnis wird in Anhang A von arXiv: 0706.0556 abgeleitet .

Obwohl dies mathematisch analog ist, kennen wir andererseits noch viel weniger Anwendungen von Quantenexpandern, als für klassische Expander bekannt sind.

Aram Harrow
quelle
Bitte nehmen Sie meine Einladung an: quantumcomputing.stackexchange.com .
Rob