Grundlegendes zum Optimierungsalgorithmus für Gruppenleiter

8

Kontext:

Ich habe versucht, den genetischen Algorithmus zu verstehen, der in der Arbeit Zerlegung einheitlicher Matrizen zum Auffinden von Quantenschaltungen diskutiert wurde : Anwendung auf molekulare Hamiltonianer (Daskin & Kais, 2011) (PDF hier ) und Optimierungsalgorithmus für Gruppenleiter (Daskin & Kais, 2010) . Ich werde versuchen, zusammenzufassen, was ich bisher verstanden habe, und dann meine Fragen stellen.

Betrachten wir das Beispiel des Toffoli-Tors in Abschnitt III-A im ersten Artikel. Aus anderen Quellen wie dieser wissen wir , dass etwa 5 Zwei-Qubit-Quantentore benötigt werden, um das Toffoli-Gate zu simulieren. Wir wählen also willkürlich eine Reihe von Toren wie {V,Z,S,V} . Wir beschränken uns auf maximal 5 Tore und erlauben uns, nur die Tore aus der Tormenge {V,Z,S,V} . Jetzt generieren wir 25 Gruppen von 15 zufälligen Zeichenfolgen wie:

1 3 2 0,0; 2 3 1 0,0; 3 2 1 0,0; 4 3 2 0,0; 2 1 3 0.0

In der obigen Zahlenfolge sind die ersten fettgedruckten Zahlen die Indexnummer der Tore (dh V=1,Z=2,S=3,Z=4 ), die letzten Zahlen sind die Werte der Winkel in [0,2π] und die mittleren ganzen Zahlen sind das Ziel-Qubit bzw. das Kontroll-Qubit. Es würde 374 solcher anderen zufällig erzeugten Zeichenketten geben.

Geben Sie hier die Bildbeschreibung ein

Unsere Gruppen sehen jetzt so aus (im Bild oben) mit n=25 und p=15 . Die Fitness jeder Saite ist proportional zur Spurentreue F=1N|Tr(UaUt)|Dabei istUadie einheitliche Matrixdarstellung, die einem von uns erzeugten String entspricht, undUtdie einheitliche Matrixdarstellung des 3-Qubit-Toffoli-Gatters. Der Gruppenleiter in einer Gruppe ist derjenige mit dem Maximalwert vonF .

Sobald wir die Gruppen haben, folgen wir dem Algorithmus:

Geben Sie hier die Bildbeschreibung ein

Die Gl. (4) im Bild erwähnt ist im Grunde:

new string[i]=r1×old string[i]+r2×leader string[i]+r3×random string[i]
(wobei1i20 ) str1+r2+r3=1 . Das[i] repräsentiert diei te Zahl in der Zeichenfolge, zum Beispiel in1 3 2 0.0; 2 3 1 0.0; 3 2 1 0.0; 4 3 2 0.0; 2 1 3 0.0ist das 6 Element 3. In diesem Zusammenhang nehmen wir r1=0.8 und r2,r3=0.2 . Das heißt, in jeder Iteration werden alle 375 Zeichenfolgen gemäß der Regel mutiert: Für jede Zeichenfolge in jeder Gruppe werden die einzelnen Elemente (Zahlen) in der Zeichenfolge gemäß Gl. (4).

Außerdem,

Zusätzlich zur Mutation wird in jeder Iteration für jede Gruppe der Population eine Einwegkreuzung (auch als Parameterübertragung bezeichnet) zwischen einem ausgewählten zufälligen Mitglied aus der Gruppe und einem zufälligen Mitglied aus einer anderen zufälligen Gruppe durchgeführt. Diese Operation ersetzt hauptsächlich einen zufälligen Teil eines Mitglieds durch den äquivalenten Teil eines zufälligen Mitglieds aus einer anderen Gruppe. Der Betrag der Übertragungsoperation für jede Gruppe wird durch einen Parameter definiert, der als Übertragungsrate bezeichnet wird und hier als

4×maxgates21
wobei der Zähler die Anzahl der Variablen ist, die bei der Optimierung eine numerische Zeichenfolge bilden.

Fragen:

  1. Woher wissen wir, wenn wir diesen Algorithmus anwenden, um die Zerlegung eines zufälligen Gates zu finden, wie viele und welche Art von elementaren Gates wir in unserem Gate-Set aufnehmen müssen? Im obigen Beispiel haben sie {V,Z,S,V} . Aber ich vermute, dass diese Wahl nicht völlig willkürlich war (?) Oder hätten wir auch etwas Zufälliges wie {X,Z,Rx,Rzz,V} wählen können ? Auch die Tatsache, dass sie nur verwendet520

  2. Ist meine Erklärung / mein Verständnis (ab Absatz 3) des Algorithmus nach dem Teil (in "Kontext"), in dem die Auswahl des Gate-Satzes und die Anzahl der Gates besprochen wurden, korrekt?

  3. 4×maxgates2maxgates520

  4. 0.99

Sanchayan Dutta
quelle
Ich implementiere den gleichen Algorithmus in Python. Haben Sie es vollständig implementiert? Ich stecke irgendwann fest, was ich in meinem Beitrag erklärt habe .
Santa
@ Santa Nein, aber jemand anderes hier könnte haben. Sie können diese Frage zum Stapelüberlauf auf Quantum Computing migrieren . Markieren Sie es für einen Moderator, der das Problem erwähnt.
Sanchayan Dutta
1
@Santa Eine Implementierung einer modifizierten Version des GLOA-Algorithmus finden Sie hier . Bitte beachten Sie Folgendes: 1. Dies ist eine modifizierte Version des ursprünglichen Algorithmus (ich habe versucht, ihn flexibler zu gestalten), 2. Der Code ist recht allgemein und verwendet viel Datenstruktur, die mit anderen Algorithmen geteilt wird, und 3. die Lizenz ist keine GPL. Sehen Sie sich diese an, wenn Sie eine (möglicherweise geänderte) Version des Codes freigeben möchten.
Nelimee

Antworten:

2

Ich schlage vor, zu untersuchen, wie ein genetischer Algorithmus in einem Kontext diskreter Variablen funktioniert, um ihn zu verstehen. Sie bieten eine Methodik, Sie können jedoch auch andere Mutations- / Crossover-Techniken anwenden.


Kurz gesagt, in einem einfachen Optimierungsproblem, bei dem die Variablen diskret sind, können wir heuristisch mit genetischen Algorithmen (die zu den klassenevolutionären Algorithmen gehören) lösen. Wir generieren eine Population von Kandidaten (zufällig) und ändern die Kandidaten bei jeder Iteration, um eine gute Lösung zu finden, die eine objektive Funktion (Fitness genannt) minimiert / maximiert. Sie können die Kandidaten durch eine Reihe von Werten darstellen (im Allgemeinen als Chromosomen bezeichnet). Wenn Sie diese Wertefolge in die Zielfunktion eingeben, bewerten Sie den Kandidaten oder weisen ihm eine Fitness zu. Crossover- / Mutationsoperationen sollen Kandidaten verändern und hoffen, unser Ziel in einer Weise zu erreichen, die mit dem zusammenhängt, was genetisch geschieht.

Die GLOA ist nur ein weiterer genetischer Algorithmus, jedoch mit dem Unterschied, dass unterschiedliche Bevölkerungsgruppen ein lokales Optimum (Leader als bester Kandidat, wenn Sie dies bevorzugen) für jede und natürlich eine leicht unterschiedliche Strategie für Mutation / Crossover aufweisen. Normalerweise haben wir eine Gruppe von Kandidaten mit einem besten Kandidaten bei jeder Iteration.

Nun zu Ihren Fragen:

1. Sie können einen beliebigen Satz von Toren auswählen (wie Ihr Beispiel für einen Satz). Dies gilt auch für die maximale Anzahl von Gate-Operationen, die Sie Ihre Zerlegung einschränken möchten. Dies sind nur Parameter für den Algorithmus. Ich würde sagen, dass dies völlig willkürlich ist (nicht so viel Logik, notwendigerweise nur heuristisch), aber vielleicht war das, was sie gewählt haben, besser an ihr Beispiel oder ihren Arbeitsaufbau angepasst. In der Praxis müssten Sie viele Parameter ausprobieren.

2. Sie wiederholen die ursprünglichen Erklärungen und insbesondere das Diagramm, also denke ich, dass Sie gut zusammenfassen.

Geben Sie hier die Bildbeschreibung ein

t14×maxgates52080

Schauen Sie sich für Ihre Visualisierung die Beispielzeichenfolge an, die Sie angeben:

1 3 2 0,0; 2 3 1 0,0; 3 2 1 0,0; 4 3 2 0,0; 2 1 3 0.0

maxgates55245×4=20

1 3 2 0.0V320.0V

4. Dies ist auch beliebig, je nachdem, was Sie wollen. Dies kann eine feste Anzahl von Iterationen sein oder bis Sie einen Schwellenwert / ein Konvergenzkriterium erreichen.

cnada
quelle
1
Danke für die Antwort! Ich habe eine Momentaufnahme des Pseudocodes in Abbildung 2 hinzugefügt, um es klarer zu machen. Sie können es jedoch jederzeit entfernen, wenn Sie möchten. :)
Sanchayan Dutta
1
Über Nummer 1 werden die „Parameter“ können spezifische Einschränkungen (Beispiel: WahlH.H.