From Ground States to Certification: Quantum Advantages in Hybrid Algorithms and Promise Problems

This thesis investigates the emergence of quantum advantages from several perspectives. First, we study the variational quantum eigensolver (VQE), a hybrid algorithm suitable for noisy intermediate-scale quantum devices. We propose a deterministic formulation of measurement-based quantum computing that offers inherent trade-offs between qubit count and circuit depth compared to conventional gate-based approaches, avoiding the exponential sampling complexity of previously proposed formulations. We evaluate VQE in two use cases. For quantum chemistry, we employ VQE ground state approximations as trial wavefunctions for quantum Monte Carlo calculations to estimate more accurate ground states. While achieving higher accuracies, we demonstrate that transferring quantum data to classical computers introduces an overhead scaling as high as N⁹ in the system size N, raising questions about the practicality for system sizes where a quantum computer shall be employed. The second use case explores machine learning tasks with classical data in natural language processing and computer vision. We propose a physics-inspired data encoding method that shifts encoding from upload in a quantum circuit to measurements, thereby reducing the circuit depth for state preparation. While its performance matches that of alternative quantum machine learning models, it does not surpass classical approaches, highlighting performance gaps that require future work. Finally, we examine theoretically proven quantum advantages in promise problems for language recognition using deterministic state automata. Building on known exponential advantages, we propose a scheme to identify new promise problems with quantum advantages and discuss frameworks leveraging this advantage for sound certification of quantum models, including necessary arguments for quantum models that can be certified within this framework. This leads to a better understanding of the first complete, sound, and state-preparation and measurement error-free semi-device-independent certification, opening new research directions.

In dieser Arbeit untersuchen wir das Auftreten von Quantenvorteilen aus verschiedenen Perspektiven. Zunächst analysieren wir den Variational Quantum Eigensolver (VQE), einen hybriden Algorithmus für verrauschte Quantencomputer mittlerer Skalierung. Wir entwickeln eine deterministische Formulierung des VQE für das messungsbasierte Quantenrechnen. Dieses ermöglicht im Vergleich zu konventionellen gatterbasierten Verfahren Kompromisse zwischen der Qubit-Anzahl und der Schaltkreistiefe und weist dabei eine exponentiell geringere Sampling-Komplexität als ein vorheriger Entwurf auf. VQE wird in zwei Anwendungsgebieten evaluiert. In der Quantenchemie nutzen wir Grundzustandsapproximationen aus einer VQE-Rechnung als Testwellenfunktionen für Quanten-Monte-Carlo-Rechnungen, um genauere Grundzustände zu bestimmen. Trotz der höheren Genauigkeit zeigen wir, dass die Datenübertragung vom Quantencomputer zum klassischen Rechner einen klassischen Mehraufwand von bis zu N⁹ in der Systemgröße N verursacht. Dies stellt die Praktikabilität für Systemgrößen infrage, bei denen Quantencomputer zum Einsatz kommen sollen. Das zweite Anwendungsgebiet umfasst maschinelles Lernen mit klassischen Daten aus der Sprachverarbeitung und Computer Vision. Wir stellen eine physikalisch motivierte Datenkodierungsmethode vor. Diese verlagert die Kodierung von der Schaltkreisimplementierung auf Messungen und reduziert dadurch die Schaltkreistiefe für die Zustandspräparation. Obwohl die Leistung mit anderen quantenmaschinellen Lernmodellen vergleichbar ist, werden klassische Verfahren nicht übertroffen, was bestehende Defizite verdeutlicht. Abschließend betrachten wir theoretisch bewiesene Quantenvorteile bei sogenannten Promise-Problemen der Spracherkennung mit deterministischen Zustandsautomaten. Aufbauend auf bekannten exponentiellen Vorteilen entwickeln wir ein Verfahren zur Identifikation neuer Promise-Probleme mit Quantenvorteilen und erörtern, wie sich dieser Vorteil für eine verlässliche Zertifizierung von Quantenmodellen nutzen lässt. Dies führt zu einem besseren Verständnis der ersten vollständigen, korrekten und SPAM-Fehler freien semi-geräteunabhängigen Zertifizierung und eröffnet somit neue Forschungsrichtungen.