Automatische Kompilierung von Quantenschaltungen

12

Eine kürzlich gestellte Frage stellte die Frage, wie das 4-Qubit-Gatter CCCZ (Controlled Controlled Controlled Z) in einfache 1-Qubit- und 2-Qubit-Gatter kompiliert werden kann. Die einzige Antwort, die bisher gegeben wurde, erfordert 63 Gatter !

Der erste Schritt war die Verwendung der C n U-Konstruktion von Nielsen & Chuang:n

Mit n=3 bedeutet dies 4 CCNOT-Gatter und 3 einfache Gatter (1 CNOT und 2 Hadamards reichen aus, um die endgültige CZ auf dem Ziel-Qubit und dem letzten Arbeits-Qubit durchzuführen).

Satz 1 dieser Arbeit besagt, dass das CCNOT im Allgemeinen 9 Ein-Qubit- und 6 Zwei-Qubit-Gatter (insgesamt 15) benötigt:

Bildbeschreibung hier eingeben


Das heisst:

(4 CCNOTs) x (15 Tore pro CCNOT) + (1 CNOT) + (2 Hadamards) = 63 Gesamttore .

In einem Kommentar wurde vorgeschlagen, dass die 63 Tore dann unter Verwendung eines "automatischen Verfahrens", beispielsweise aus der Theorie der automatischen Gruppen, weiter kompiliert werden können .

Wie kann diese "automatische Kompilierung" durchgeführt werden, und um wie viel würde sich in diesem Fall die Anzahl der 1-Qubit- und 2-Qubit-Gatter verringern?

user1271772
quelle
1
Ich bin mitten in ein paar Dingen, habe aber Ihre Frage entdeckt. Globale Mølmer-Sørensen-Gatter sind 2-Qubit-Gatter, und die Veröffentlichung Verwendung globaler Wechselwirkungen in effizienten Quantenschaltungskonstruktionen beschreibt: "Optimierte Implementierung des CCCZ-Gatters mit drei GMS-Gattern", siehe Abbildung 9. Sie können die Antwort gerne schreiben, wenn dies der Fall ist hilfreich.
Rob
Die Darstellung im Bild erfordert nur 4 CCNOTs und damit 63 Tore anstelle von 93.
Dyon J Don Kiwi van Vreumingen
@ DonKiwi, zur Kenntnis genommen! 4 CCNOTs statt 6. Ich aktualisiere es jetzt.
User1271772
1
@Rob: Sie scheinen vorzuschlagen, das X in CCCX mit zwei Hadamards zu konjugieren. Dann kann der CCCX genau wie in der obigen Nielsen & Chaung-Schaltung zerlegt werden. Ist das korrekt? In meiner zweiten Antwort auf DonKiwis Frage habe ich so etwas gemacht. Es scheint, dass Ihr Kommentar genau während der Eingabe dieser Antwort kam, da sie 5 Minuten voneinander entfernt sind (und es mehr als 5 Minuten gedauert hat, bis ich sie eingetippt habe). Diese Frage zum "automatischen Kompilieren" bleibt jedoch bestehen, da es schön wäre, eine Schaltung auf "offensichtliche Weise" zu konstruieren und dann automatisch zu etwas Effizienterem zu kompilieren.
User1271772
1
@ user1271772 - Jedes (qu) Bit hilft.
Rob

Antworten:

6

Sei g1gM das Grundgatter, das Sie benutzen dürfen. Für die Zwecke dieses CNOT12 und CNOT13 usw. als getrennt behandelt. So M ist polynomiell abhängig von n , der Anzahl von Qubits. Die genaue Abhängigkeit beinhaltet Details der Art der von Ihnen verwendeten Gatter und wie k lokal sie sind. Wenn es zum Beispiel x einzelne Qubit-Gatter und y 2-Qubit-Gatter gibt, die nicht von der Ordnung wie CZ abhängen, dann ist M=xn+(n2)y.

Eine Schaltung ist dann ein Produkt dieser Generatoren in einer bestimmten Reihenfolge. Es gibt jedoch mehrere Schaltkreise, die nichts bewirken. Wie CNOT12CNOT12=Id . Also geben diese Beziehungen auf die Gruppe. Das heißt es ist eine Gruppenpräsentation g1gMR1 , wo es viele Beziehungendie wir nicht wissen.

Das Problem, das wir lösen möchten, erhält ein Wort in dieser Gruppe, das kürzeste Wort, das dasselbe Element darstellt. Für allgemeine Gruppenpräsentationen ist dies hoffnungslos. Die Art der Gruppenpräsentation, auf die dieses Problem zugegriffen werden kann, wird als automatisch bezeichnet.

Aber wir können ein einfacheres Problem betrachten. Wenn wir einen Teil von gi wegwerfen, erhalten die Wörter von vorher die Form w1gi1w2gi2wk wobei jedes der wi nur Wörter in den verbleibenden Buchstaben sind. Wenn wir es geschafft haben, sie mit den Relationen zu verkürzen, an denen das gi nicht beteiligt ist , haben wir den gesamten Kreislauf verkürzt. Dies ist vergleichbar mit der Optimierung der CNOTs in der jeweils anderen Antwort.

Wenn es zum Beispiel sind drei Generatoren und das Wort ist aababbacbbaba , aber wir wollen nicht behandeln c , werden wir stattdessen verkürzen w1=aababba und w2=bbaba bis w 1 und w 2 . Wir stellen sie dann wieder zusammen als w 1 cw^1w^2w^1cw^2 , und das ist eine Verkürzung des ursprünglichen Wortes.

So WLOG (ohne Beschränkung der Allgemeinheit), nehmen wir an , wir in diesem Problem sind bereits g1gMR1 , wo wir jetzt alle Tore angegeben verwenden. Auch dies ist wahrscheinlich keine automatische Gruppe. Aber was ist, wenn wir einige der Beziehungen verwerfen? Dann werden wir eine weitere Gruppe haben, die eine Quotientenkarte hat, die derjenigen entspricht, die wir wirklich wollen.

Die Gruppe g1g2 keine Beziehungen sind einefreie Gruppe, aber dannwenn Sie setzeng12=id als eine Beziehung, erhalten Sie daskostenlose Produkt Z2Z und es ist ein Quotient Karte aus dem ehemaligen zum späteren Reduzieren der Anzahl vong1 's in jedem Segment modulo2 .

Die Beziehungen, die wir herauswerfen, werden so sein, dass diejenige im Obergeschoss (die Quelle der Quotientenkarte) von Natur aus automatisch ist. Wenn wir nur die verbleibenden Relationen verwenden und das Wort verkürzen, wird es immer noch ein kürzeres Wort für die Quotientengruppe sein. Es ist einfach nicht optimal für die Quotientengruppe (das Ziel der Quotientenkarte), aber es hat die Länge der Länge, mit der es begonnen hat.

Das war die allgemeine Idee, wie können wir daraus einen bestimmten Algorithmus machen?

Wie wählen wir das gi und die Relationen aus, die verworfen werden sollen, um eine automatische Gruppe zu erhalten? Hier kommt das Wissen über die Arten von Elementartoren ins Spiel, die wir normalerweise verwenden. Es gibt viele Beteiligungen, also behalte nur diese. Achten Sie sorgfältig darauf, dass dies nur die elementaren Verschiebungen sind. Wenn Ihre Hardware Probleme hat, Qubits zu tauschen, die auf Ihrem Chip stark voneinander getrennt sind, bedeutet dies, dass Sie sie nur in diejenigen schreiben, die Sie leicht tun können, und dieses Wort auf diese reduzieren so kurz wie möglich sein.

Angenommen, Sie haben die IBM Konfiguration . Dann sind s01,s02,s12,s23,s24,s34 die erlaubten Tore. Wenn Sie eine allgemeine Permutation durchführen möchten, zerlegen Sie sie insi,i+1 Faktoren. Das ist ein Wort in der Gruppes01,s02,s12,s23,s24,s34R1 das wir kürzen möchten.

Beachten Sie, dass dies nicht die Standard-Involutionen sein müssen. Sie können beispielsweise zusätzlich zu X auch R(θ)XR(θ)1 einwerfen . Denken Sie an dieX Gottesman-Knill-Theorem , aber auf abstrakte Weise bedeutet dies, dass es einfacher ist, es zu verallgemeinern. Verwenden Sie beispielsweise die Eigenschaft, dass Sie unter kurzen exakten Sequenzen, wenn Sie über endliche vollständige Umschreibungssysteme für beide Seiten verfügen, eines für die mittlere Gruppe erhalten. Dieser Kommentar ist für den Rest der Antwort nicht erforderlich, zeigt jedoch, wie Sie aus den in dieser Antwort enthaltenen Beispielen allgemeinere Beispiele erstellen können.

Die Beziehungen, die beibehalten werden, sind nur solche der Form (gigj)mij=1 . Dies ergibt eine Coxeter-Gruppe und es erfolgt automatisch. Tatsächlich müssen wir nicht einmal von vorne anfangen, um den Algorithmus für diese automatische Struktur zu codieren. Es ist bereits in Sage (Python-basiert) für allgemeine Zwecke implementiert . Alles, was Sie tun müssen, ist das mij anzugeben, und die verbleibende Implementierung ist bereits abgeschlossen. Darüber hinaus könnten Sie einige Beschleunigungen durchführen.

mij ist aufgrund der Lokalitätseigenschaften der Tore sehr einfach zu berechnen. Wenn die Tore sind höchstensk -local, danndie Berechnung vonmij kann auf einem geschehen22k1 symmetrisch ist, hat 1 ist auf der Diagonale ( (mij=2mij=2gigjmij1(gigi)1=1(CNOT12H1)CNOT37H3 ohne die Berechnung erneut .

3 oder mehr beteiligt waren, wurden alle verworfen. Wir setzen sie jetzt wieder ein. Nehmen wir an, wir haben das, dann kann man Dehns gierigen Algorithmus mit neuen Relationen ausführen . Wenn es eine Änderung gab, klopfen wir sie zurück, um die Coxeter-Gruppe erneut zu durchlaufen. Dies wiederholt sich, bis keine Änderungen mehr vorgenommen wurden.

Jedes Mal, wenn das Wort kürzer wird oder gleich lang bleibt, verwenden wir nur Algorithmen mit linearem oder quadratischem Verhalten. Dies ist ein ziemlich billiges Verfahren, also sollten Sie es auch tun und sicherstellen, dass Sie nichts Dummes getan haben.

NKm

edge_list=[]
for i1 in range(N):
    for j1 in range(i):
        edge_list.append((j1+1,i1+1,m[i1,j1]))
G3 = Graph(edge_list)
W3 = CoxeterGroup(G3)
s3 = W3.simple_reflections()
word=[choice(list([1,..,N])) for k in range(K)]
print(word)
wTesting=s3[word[0]]
for o in word[1:]:
    wTesting=wTesting*s3[o]
word=wTesting.coset_representative([]).reduced_word()
print(word)

N=28K=20m

[26, 10, 13, 16, 15, 16, 20, 22, 21, 25, 11, 22, 25, 13, 8, 20, 19, 19, 14, 28]

['CNOT_23', 'Y_1', 'Y_4', 'Z_2', 'Z_1', 'Z_2', 'H_1', 'H_3', 'H_2', 'CNOT_12', 'Y_2', 'H_3', 'CNOT_12', 'Y_4', 'X_4', 'H_1', 'Z_5', 'Z_5', 'Y_5', 'CNOT_45']

[14, 8, 28, 26, 21, 10, 15, 20, 25, 11, 25, 20]

['Y_5', 'X_4', 'CNOT_45', 'CNOT_23', 'H_2', 'Y_1', 'Z_1', 'H_1', 'CNOT_12', 'Y_2', 'CNOT_12', 'H_1']

TiTin=1Tiiw1gi1w2gi2wkwiX1T2X1T2X1T2X1

HiHimij1,2

AHusain
quelle
+1 !!! Viel Detail! Ich lese es :)
user1271772
1
@AHussain, ist es möglich, ein Beispiel durchzuarbeiten, in dem dies auf die "naive" CCCZ-Konstruktion in meiner Frage angewendet wird, und am Ende eine geringere Anzahl von Toren zu erhalten? Die ursprüngliche Frage zu CCCZ hat jetzt 6 Antworten, und viele von ihnen haben eine viel geringere Anzahl von Gates. Ich frage mich, was Ihr Ansatz für die Toranzahl geben würde.
user1271772
4

Mit dem in https://arxiv.org/abs/quant-ph/0303063 1 beschriebenen Verfahren kann jedes Diagonalgate - und damit insbesondere das CCCZ-Gate - in CNOTs und Ein-Qubit-Diagonalgates zerlegt werden. Dabei können die CNOTs nach einem klassischen Optimierungsverfahren allein optimiert werden.

Die Referenz liefert eine Schaltung unter Verwendung von 16 CNOTs für beliebige diagonale 4-Qubit-Gatter (Fig. 4).


iIxiI{1,2,3,4}

Beachten Sie auch, dass diese Konstruktion keinesfalls optimal sein muss.


1 Hinweis: Ich bin ein Autor

Norbert Schuch
quelle
Interessant. Trotzdem muss ich die Zeitung lesen, um zu sehen, wie die Prozedur ist. Ich warte auch darauf, dass @AHussain uns sagt, wie es mit der Theorie der automatischen Gruppen gemacht wird.
user1271772