Quantum Optimization (with IBM Quantum)

1. 00:00Willkommen zurück zum Quantenoptimierungskurs.
2. 00:03In diesem Video sprechen wir über die Optimierung mit der Grover-Suche.
3. 00:08In den vorangegangenen Vorträgen,
4. 00:09haben Sie viel über die Variation aller Ansätze zur Lösung von Optimierungsproblemen gehört. Dort
5. 00:14war die Idee immer, dass wir einen Hamiltonian haben, normalerweise einen Ising-Hamiltonian und ein Quantenmodell.
6. 00:20Und dann wollen wir die Energie dieses Ising-Hamiltonianers minimieren.
7. 00:26Wir verwenden den Quantencomputer, um die Energie zu ermitteln, und dann den klassischen Computer für die Rückkopplungsschleife, die die
8. 00:33die Parameterwerte. Dieser Ansatz ist zwar für einige Geräte in naher Zukunft großartig, weil wir den Quantenschaltkreis so anpassen können, dass er
9. 00:40auf die uns zur Verfügung stehenden Ressourcen abstimmen können, sind die westlichen Probleme, auf die wir gestoßen sind.
10. 00:45Erstens ist es schwierig, das Modell zu wählen.
11. 00:49Wählen Sie etwas sehr Allgemeines, das schwer zu trainieren ist, oder haben Sie eine intrinsische Motivation, die Sie nutzen können?
12. 00:55Zweitens: Es gibt keine allgemeine Konvergenzgarantie
13. 01:00In diesem Video werfen wir einen Blick auf modellfreie Ansätze wie den adaptiven Suchalgorithmus von Grover.
14. 01:10Die Idee dabei ist, dass wir nicht ein Variationsmodell haben, das wir optimieren, sondern von einem Quantenzustand ausgehen, der einige
15. 01:16Überschneidungen mit der Lösung hat, und dann verbessern wir die Lösung allmählich, bis wir den optimalen Quantenzustand erreicht haben.
16. 01:25Das Thema dieses Videos ist die adaptive Suche von Grovet.
17. 01:28Und um zu verstehen, wie das funktioniert, müssen wir zunächst wissen, was die Grover-Suche ist.
18. 01:33Es ist einer der berühmtesten Quantenalgorithmen und sicherlich haben viele von Ihnen schon davon gehört, aber um es kurz zu machen
19. 01:40und um sicherzustellen, dass alle auf der gleichen Basis sind,
20. 01:42lassen Sie uns einen Blick darauf werfen, was es ist.
21. 01:45Nehmen wir an, wir haben einen Datensatz mit unstrukturierten Daten.
22. 01:49Dies ist wichtig.
23. 01:51Das bedeutet, dass wir zum Beispiel, wie auf der Folie zu sehen, einen Satz von N Datenpunkten haben und einen davon finden wollen
24. 01:57der die Lösung ist.
25. 01:59Ich habe Zugriff auf eine Funktion, die uns sagt, ob ein bestimmtes Element eine gute Lösung ist, wenn es mit einem
26. 02:05eine Eins oder eine schlechte Lösung mit der Bezeichnung Null.
27. 02:09Hier sind also zum Beispiel die Elemente eins und zwei schlecht.
28. 02:11Wir erhalten also eine Null zurück, aber das Element X Stern ist eine gute Lösung und wir erhalten eine Eins zurück.
29. 02:18Auf einem klassischen Computer, da es keinerlei Struktur gibt,
30. 02:22können Sie nur die Elemente nach dem Zufallsprinzip überprüfen, und das ergibt im Durchschnitt eine Laufzeit von N über zwei
31. 02:28wobei N die Anzahl der Elemente in Ihrem Datensatz ist.
32. 02:32Ein Quantencomputer,
33. 02:33kann dagegen die Grover-Suche verwenden. Intuitiv können Sie sich vorstellen, dass eine der Lösungen, während der Lösungsvektor
34. 02:41ein Vektor in diesem großdimensionalen Hilbert-Raum ist.
35. 02:44Wenn wir mit einem Zustand beginnen, einem anderen Vektor im Hilbert-Raum, der eine gewisse Überschneidung mit dem Endzustand hat, nennen wir ihn
36. 02:52den Anfangszustand als Null.
37. 02:54Dann sagt uns der Grover-Algorithmus, dass wir den Vektor iterativ verbessern können, bis wir den gewünschten Zustand erreichen.
38. 03:02Wichtig ist, dass dies nur etwa das Quadrat von N Iterationen erfordert. Das ist ein quadratischer Geschwindigkeitsgewinn im Vergleich zur klassischen Suche.
39. 03:10Wenn Sie jedoch bei der klassischen Suche nur nach einem Element in der Grover-Suche suchen müssen, verwenden Sie eine Quantenressource.
40. 03:18Wir werden nicht näher auf die Grover-Suche eingehen, weil sie für das Verständnis des restlichen Vortrags nicht wichtig ist.
41. 03:23Aber wenn Sie sich mehr Details ansehen möchten, können Sie sich das Qiskit-Lehrbuch unter dem unten stehenden Link ansehen.
42. 03:30Mit der Grover-Suche können wir nun einen Algorithmus namens Grover adaptive search verwenden, um das Minimum einer Funktion zu finden.
43. 03:38In unserem Fall, der Optimierung, haben wir dieses QUBO-Ziel.
44. 03:41Wir haben also einen binären Vektor X, die QUBO-Matrix Q und den QUBO-Vektor mu.
45. 03:48Die Idee, die hinter der Suche steckt, ist intuitiv, dass wir einen Schwellenwert wählen und mit der Grover-Suche alle Elemente auswählen, die
46. 03:56unter diesem Schwellenwert liegen.
47. 03:57Dann senken wir den Schwellenwert und suchen nach neuen Elementen.
48. 04:01Das machen wir so lange, bis nur noch eine Lösung übrig ist.
49. 04:04Und das wird das Minimum der Funktion sein.
50. 04:08Konkret beginnen wir mit der Auswahl eines zufälligen Schwellenwerts T. Auf dieser Grundlage finden wir ein globales Orakel, das uns einen Wert zurückgibt, wenn
51. 04:17die Kostenfunktion unterhalb des Schwellenwerts liegt und null, wenn sie oberhalb des Schwellenwerts liegt.
52. 04:22Nachdem wir die Grover-Suche angewendet haben, setzen wir den Schwellenwert auf die Kosten einer zufälligen Lösung, die wir als Stichprobe genommen haben.
53. 04:29Dann wiederholen wir einfach die Schritte zwei und drei, bis wir konvergiert haben und nur noch eine Lösung übrig ist.
54. 04:35Um dies etwas deutlicher zu visualisieren,
55. 04:37hier ist ein Beispiel. Nehmen wir noch einmal an, wir haben eine Menge, die andere Menge haben wir der Einfachheit halber aufgetragen, die Kosten für jeden dieser Werte.
56. 04:47In der Praxis haben Sie keinen Zugang zu jedem dieser Werte, denn das würde bedeuten, dass Sie alle Werte bewerten müssten.
57. 04:52Aber wir wollen nicht alle Elemente durchgehen.
58. 04:54Dies dient also nur zur Veranschaulichung. Nehmen wir an, wir wählen ein zufälliges Element aus der Menge aus und setzen dann einen Schwellenwert auf den Wert
59. 05:02dieses Element.
60. 05:04Wenn Sie die Grover-Suche anwenden, erhalten Sie alle Elemente, die mindestens diesen Schwellenwert erreichen, d.h. diese Elemente.
61. 05:11Dann wählen wir ein zufälliges Element davon aus, aktualisieren den Schwellenwertm
62. 05:16und wieder: angewandte Forschung. Jetzt sind nur noch drei Elemente übrig.
63. 05:20Danach wählen wir wieder ein Element aus und setzen einen Schwellenwert auf diesen Wert.
64. 05:25Starten Sie die Grover-Suche und wir sehen, dass nur noch ein Element übrig ist.
65. 05:28Und dies ist tatsächlich das Minimum unserer Funktion.
66. 05:33Nun, da Sie die Variationsalgorithmen und den nicht variablen Algorithmus Grover adaptive search kennen,
67. 05:39lassen Sie uns diese beiden vergleichen.
68. 05:42Variationsmethoden sind, wie wir bereits gesagt haben, großartig, weil sie hardwareeffiziente Schaltungen ermöglichen.
69. 05:49Wenn ich also Hardware zur Verfügung habe, kann ich den Ansatz über diese Hardware gezielt anpassen und dann den Algorithmus ausführen
70. 05:56und auf das Beste hoffen.
71. 05:58Allerdings sind Variationsmethoden im Allgemeinen schwer zu trainieren und es gibt keine allgemeine Geschwindigkeitsgarantie.
72. 06:06Grover adaptive Suche,
73. 06:07nutzt andererseits die wirtschaftliche Beschleunigung der Grover-Suche aus.
74. 06:10Es gibt also eine klare Motivation, warum dieser Algorithmus besser als ein klassischer Algorithmus sein sollte.
75. 06:15Außerdem gibt es kein Problem mit der Modellauswahl, da wir die Qualität der Lösung iterativ steigern.
76. 06:22Allerdings, und das ist im Moment ein großer Nachteil der adaptiven Grover-Suche, führt sie zu enormen Schaltkreisen.
77. 06:30Wenn Sie sich also an die Grover-Suche und die dahinter stehende Intuition erinnern, vom ersten Lösungsvektor zur zweiten Lösung zu gelangen
78. 06:37Vektor zu gelangen, muss eine Operation Q durchgeführt werden.
79. 06:41Diese Operation Q wird auf einem Quantencomputer als eine globale Operation implementiert
80. 06:45die Cubits insgesamt. Zuerst müssen wir eine Schicht von Hadamard-Gattern anwenden, dann eine Reflexion über den Null-Zustand, wieder die Schicht
81. 06:53von Hadamard-Gattern.
82. 06:54Und schließlich kennzeichnen wir alle guten Zustände.
83. 06:58Das ist unglaublich ineffizient, wenn man es auf kurzfristigen Geräten implementiert, weil alle Cubits vollständig miteinander verbunden sind.
84. 07:04Und in der Praxis führt dies zu unerschwinglich tiefen Schaltkreisen.
85. 07:08Solange wir also noch Computer in naher Zukunft haben, sind Variationsmethoden wahrscheinlich der richtige Weg.
86. 07:13Aber wenn wir in Zukunft fehlertolerante Quantencomputer haben werden, dann gibt es eine sehr gute Motivation, warum Grover adaptive
87. 07:21Suche ein guter Kandidat für die Quantenoptimierung wäre.
88. 07:26Wenn Sie sehen wollen, wie wir die adaptive Grover-Suche mit Qiskit implementieren und ein praktisches Problem damit lösen können,
89. 07:31bleiben Sie dran für das nächste Video.

To enable the transcript, please select a language in the video player settings menu.