Dokument: Complexity of Variational Quantum Algorithms
| Titel: | Complexity of Variational Quantum Algorithms | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=64171 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20231212-111542-0 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Bittel, Lennart [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Kliesch, Martin [Gutachter] Prof. Dr. Bruß, Dagmar [Gutachter] | |||||||
| Stichwörter: | VQA, Complexity, NP, QCMA | |||||||
| Dewey Dezimal-Klassifikation: | 500 Naturwissenschaften und Mathematik » 530 Physik | |||||||
| Beschreibungen: | Da die Entwicklung von Quantencomputern rasch voranschreitet und immer größere
Systeme verfügbar werden, besteht ein wichtiger nächster Schritt darin, ihren Nutzen zu demonstrieren. Leider arbeiten die derzeitigen Implementierungen unterhalb der Fehlerkorrekturschwelle, was bedeutet, dass mögliche Algorithmen durch kurze Gattersequenzen begrenzt sind. Etablierte Algorithmen wie der Shor-Algorithmus können daher noch nicht implementiert werden. Als Forscher sind wir an einem sinnvollen Quantenvorteil interessiert, d.h. an der Lösung eines Problems auf einem Quantengerät, für das die besten bekannten klassischen Algorithmen unaus- führbar lange Laufzeiten hätten. Ein Kandidat hierfür sind Variationsquantenalgo- rithmen (VQAs), die einen hybriden quanten-klassischen Ansatz zur Lösung eines Optimierungsproblems darstellen. Ein klassischer Computer kann Parameter eines Quantenschaltkreises wählen, die einen Variationszustand erzeugen um damit den Erwartungswert einer Observablen zu minimieren. VQAs können sowohl für klassis- che Optimierungsprobleme als auch die Schätzung der Grundzustandsenergie eines Quanten-Hamiltonoperators verwendet werden. In dieser Arbeit analysieren wir einige Herausforderungen, die VQAs überwinden müssen, um ein nützliches Werkzeug zu werden. Ein Problem ist, dass die Opti- mierung zu suboptimalen lokalen Minima der Kostenfunktion konvergieren kann. Wir zeigen, dass das klassische Training von VQAs NP-schwer ist. Dies impliziert, dass kein Polynomialzeitalgorithmus immer gegen globale Minima konvergieren kann (unter der Annahme, dass P̸ = NP). Für VQAs ist es auch wichtig, kurze Quantenschaltkreise zu finden, damit ihre Imple- mentierung auf zeitnah verfügbarer Hardware möglich wird. Dies bedeutet, dass der VQA-Ansatz in der Lage sein muss die Grundzustandsenergie zu approximieren, aber gleichzeitig eine geringe Komplexität aufweisen muss. Wir zeigen, dass es QCMA- schwer ist, eine Implementierung mit der geringsten Schaltkreistiefe zu finden, selbst wenn man sie nur bis auf einen multiplikativen Faktor finden möchte. Schließlich gibt es noch das Problem des Messaufwands, der für VQA Optimierungen erforderlich ist. Die Schätzung des Gradienten in Abhängigkeit von den Parametern kann sehr zeitaufwendig sein, auch weil aufgrund der Messstatistik mehrere Messrunden pro Messeinsteillung erforderlich sind. Um den Messaufwand zu reduzieren, entwickeln wir eine Gradientenschätzungsroutine, die auf einem Bayes’schen Rahmenwerk basiert. Wir motivieren und zeigen numerisch, dass diese Strategie die Anzahl der Messrunden bei gleichbleibender Gradientenqualität erheblich reduzieren kann.As the development of quantum computers progresses rapidly and larger physical chips become available, an important next step is to demonstrate their usefulness as computational devices. Unfortunately, current implementations operate below the error-correction threshold, which means that algorithms are limited to short gate sequences due to the gate noise. Established algorithms such as Shor’s algorithm are therefore not yet implementable. As researchers, we are interested in a meaningful quantum advantage, i.e. performing a computational task on a quantum device for which the best known classical algorithms have infeasibly long runtimes. Prominent candidates are variational quantum algorithms (VQAs), which are a hybrid quantum- classical approach of solving an optimization problem. Here, a classical computer can choose tunable parameters of a quantum circuit which creates a variational state in order to minimize the expectation value of some cost observable. VQAs can be used for both classical optimization problems as well as finding the ground state energy of some quantum Hamiltonian. In this thesis, we outline some challenges that VQAs must overcome to become a viable tool. Namely, there is the problem that the optimization converges to suboptimal local minima of the cost function. In our work, we show that the classical training of VQAs is NP-hard. This implies that, at least for some cases, no polynomial- time algorithm can converge to the global minima (assuming P̸ = NP). For VQAs, it is also important to find short circuit implementations to suppress the physical noise in the system and make their implementation feasible on near- term hardware. This means that the VQA ansatz must be expressive enough to approximate the ground-state energy while still maintaining low complexity. In our work, we show that finding the shortest circuit depth implementation is QCMA-hard, even if one only wants to get close within multiplicative factor scaling with the input size. Finally, there is the problem of the measurement effort required for VQAs. Here, the estimation of the gradient with respect to the tunable parameters can act as a bottleneck, mainly because the shot-noise statistics require multiple rounds of measurement. To alleviate this problem, we propose a gradient estimation routine based on a Bayesian framework to reduce the overall measurement effort. We motivate and numerically show that, for well-studied VQA proposals, the strategy can significantly reduce the number of measurement rounds while maintaining the same gradient quality. | |||||||
| Lizenz: |  Dieses Werk ist lizenziert unter einer Creative Commons Namensnennung 4.0 International Lizenz | |||||||
| Bezug: | 01.09.2018-30.05.2023 | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Physik » Theoretische Physik | |||||||
| Dokument erstellt am: | 12.12.2023 | |||||||
| Dateien geändert am: | 12.12.2023 | |||||||
| Promotionsantrag am: | 19.04.2023 | |||||||
| Datum der Promotion: | 30.05.2023 |
