Was ist die mathematische Rechtfertigung für die „Universalität“ der universellen Menge von Quantentoren (CNOT, H, Z, X und π / 8)?

In dieser Antwort erwähnte ich, dass die CNOT-, H-, X-, Z- und Gatter eine universelle Menge von Gattern bilden, die bei einer ausreichenden Anzahl von Gattern der Replikation eines einheitlichen Quantentors willkürlich nahe kommen können (ich habe davon erfahren) Tatsache aus Professor Umesh Vaziranis EdX-Vorlesungen). Aber gibt es dafür eine mathematische Rechtfertigung? Es sollte geben! Ich habe versucht, nach relevanten Artikeln zu suchen, konnte aber nicht viel finden. $\pi/8$

quantum-gate universal-gates gate-synthesis Sanchayan Dutta
quelle

Antworten:

Die Antwort, die Sie erwähnen, bezieht sich auf das Buch von Michael Nielsen und Isaac Chuang, Quantenberechnung und Quanteninformation (Cambridge University Press), das einen Beweis für die Universalität dieser Tore enthält. (In meiner Ausgabe von 2000 finden Sie dies auf S. 194.) Die wichtigste Erkenntnis ist, dass das Gate (oder Gate) zusammen mit dem Gate zwei verschiedene Rotationen auf der Bloch-Kugel mit Winkeln erzeugt, die gleich sind irrationale Vielfache von . Dies ermöglicht Kombinationen von $T$ $\pi/8$ $H$ $2\pi$ und Gattern, die Oberfläche der Bloch-Kugel dicht auszufüllen und dadurch einen etwaigen ein-Qubit-Einheitsoperator zu approximieren. $T$ $H$

Dass dies effizient durchgeführt werden kann, zeigt der Satz von Solovay-Kitaev . Hier bedeutet "effizient" Polynom in $\log(1/\epsilon)$ , wobei die gewünschte Genauigkeit ist. Dies beweist auch das Buch von Nielsen und Chuang (Anhang 3 in der Ausgabe 2000). Eine explizite Konstruktion finden Sie unter https://arxiv.org/abs/quant-ph/0505030 . $\epsilon$

Die Kombination von CNOT-Gattern ermöglicht die Approximation beliebiger Multi-Qubit-Unitaries, wie von Barenco et al. in Phys. Rev. A 52, 3457 (1995). (Ein Preprint dieses Papiers ist unter https://arxiv.org/abs/quant-ph/9503016 zu finden .) Dies wird auch in Nielsen und Chuang (S. 191 in der Ausgabe 2000) erörtert.

Brian R. La Cour
quelle

Mit Kliuchnikov, Maslov und Mosca kann man ein noch stärkeres Ergebnis erzielen Giles Selinger .

AHusain

Sie brauchen noch nicht einmal und . , $Z$ $X$
$\rm{CNOT}$ $H$ und sind ausreichend. $T=\pi/8$

1) und reichen aus, um eine einheitliche Transformation auf einem Qubit zu ermöglichen. 2) Wenn Sie addieren , können Sie eine allgemeine unitäre Transformation innerhalb eines Fehlers nur mit Gattern synthetisieren . $H$ $T$
$\rm{CNOT}$ $\epsilon>0$ $\mathcal{O}(\log^2(1/\epsilon))$

Wenn Sie möchten, dass der Fehler und Sie nur das Phasentor hinzufügen möchten $\epsilon=0$ $\pi/2$ $\frac{a+ib}{2^n} + \frac{c+id}{2^{n+1/2}}$

$\{{\rm{CCNOT}},H\}$ ${D(\theta)}$

user1271772
quelle

CCNOT + H ist jedoch in einem anderen Sinne universell: Es ist rechnerisch universell, kann aber kein Tor realisieren.

Norbert Schuch

ϵ > 0

$\epsilon>0$

ϵ > 0

$\epsilon>0$

Nee. Es kann aus offensichtlichen Gründen kein Gatter mit komplexen (= nicht reellen) Koeffizienten realisieren. Es ist rechnerisch universell, dh es kann jedes q ausgeführt werden. Berechnung, aber dies geschieht nicht durch Eins-zu-Eins-Implementierung der Gatter, sondern durch eine äquivalente Realisierung. Wenn Sie also Unitaries realisieren möchten (was der springende Punkt zu sein scheint), handelt es sich nicht um ein universelles Gate-Set.

Norbert Schuch

@ NorbertSchuch: Ein Beispiel für eine Quantenberechnung ist die Simulation einer komplexen Einheit. Wenn CCNOT + H also ein beliebiges q kann. Berechnung, kann es nicht beliebig nahe kommen, eine einheitliche zu simulieren?

user1271772

Sowohl CCNOT als auch H haben nur echte Einträge. Es gibt KEINE MÖGLICHKEIT, ein Tor mit komplexen Einträgen zu erhalten. --- Allgemeiner gibt es (mindestens) 3 Begriffe von "Simulation": Holen Sie sich eine beliebige Einheit, holen Sie sich die Messstatistik eines Quantencomputers oder lösen Sie ein BQP-Problem. CCNOT + H ist universell im 2. (und 3.) Sinne, aber nicht im ersten.

Norbert Schuch