Ein Quantencomputer kann Optimierungsprobleme schneller lösen als klassische Supercomputer, ein Prozess, der als „Quantenvorteil“ bekannt ist und von einem USC-Forscher nachgewiesen wurde. Die Studie zeigt, wie Quantenglühen, eine spezielle Form des Quantencomputers, die besten derzeitigen klassischen Algorithmen bei der Suche nach nahezu optimalen Lösungen für komplexe Probleme übertrifft.
„Die Art und Weise, wie Quantenglühen funktioniert, besteht darin, in Quantensystemen Zustände mit niedriger Energie zu finden, die optimalen oder nahezu optimalen Lösungen für die zu lösenden Probleme entsprechen“, sagte Daniel Lidar, korrespondierender Autor der Studie und Professor für Elektrotechnik und Computertechnik, Chemie sowie Physik und Astronomie an der USC Viterbi School of Engineering und dem USC Dornsife College of Letters, Arts and Sciences.
Ungefähre Optimierung
Wissenschaftler bemühen sich seit Jahren um den Nachweis eines Quantenskalierungsvorteils (bei dem der Quantenvorteil mit zunehmender Problemgröße wächst) durch den Einsatz eines Quantenglühverfahrens. Es wird seit langem vermutet, dass Quantenglühen rechnerische Vorteile für die Optimierung bietet, aber der endgültige Nachweis von Skalierungsvorteilen gegenüber klassischen Methoden ist schwer zu führen. Diese Studie verlagert den Schwerpunkt von der exakten Optimierung (bei der der Quantenvorteil noch nicht bewiesen ist) auf die approximative Optimierung, ein Gebiet mit breiter Anwendbarkeit in Industrie und Wissenschaft.
Quantenglühen ist eine spezielle Art des Quantencomputers, der die Prinzipien der Quantenphysik nutzen kann, um hochwertige Lösungen für schwierige Optimierungsprobleme zu finden. Anstatt exakte optimale Lösungen zu verlangen, konzentrierte sich die Studie darauf, Lösungen zu finden, die innerhalb eines bestimmten Prozentsatzes (≥ 1 Prozent) vom optimalen Wert liegen. Viele reale Probleme erfordern keine exakten Lösungen, was diesen Ansatz praktisch relevant macht. Bei der Entscheidung, welche Aktien in einen Investmentfonds aufgenommen werden sollen, reicht es beispielsweise oft aus, einen führenden Marktindex zu schlagen, anstatt jedes andere Aktienportfolio zu übertreffen.
Um den algorithmischen Quantenskalierungsvorteil zu demonstrieren, verwendeten die Forscher einen D-Wave Advantage Quantenglühprozessor, eine spezielle Art von Quantencomputer, der am USC Information Sciences Institute installiert ist. Wie bei allen aktuellen Quantencomputern spielt das Rauschen eine wichtige Rolle, wenn es darum geht, den Quantenvorteil bei der Quantenglühung zunichte zu machen.
Um dieses Problem zu überwinden, implementierte das Team auf dem D-Wave-Prozessor eine Technik namens Quantum Annealing Correction (QAC), mit der über 1.300 fehlerunterdrückte logische Qubits erzeugt werden. Diese Fehlerunterdrückung war der Schlüssel zur Erzielung des Vorteils gegenüber der parallelen Temperierung mit isoenergetischen Clusterbewegungen (PT-ICM), dem derzeit effizientesten klassischen Algorithmus für vergleichbare Probleme.
„Zeit-zu-Epsilon“-Leistung
Die Studie demonstrierte den Quantenvorteil durch den Einsatz mehrerer Forschungsmethoden und konzentrierte sich auf eine Familie von zweidimensionalen Spin-Glass-Problemen mit hochpräzisen Wechselwirkungen. „Spin-Glas-Probleme sind eine Klasse komplexer Optimierungsaufgaben, die ihren Ursprung in statistischen Physikmodellen ungeordneter magnetischer Systeme haben“, so Lidar. Statt nach exakten Lösungen zu suchen, untersuchten die Forscher die „Time-to-Epsilon“-Leistung und maßen, wie schnell jeder Ansatz Lösungen innerhalb eines bestimmten Prozentsatzes der optimalen Antwort finden konnte.
Die Forscher wollen ihre Ergebnisse auf dichtere, höherdimensionale Probleme ausdehnen und Anwendungen in der realen Welt der Optimierung erforschen. Lidar sagte, dass weitere Verbesserungen bei der Quantenhardware und der Fehlerunterdrückung den beobachteten Vorteil noch verstärken könnten. „Dies eröffnet neue Wege für Quantenalgorithmen bei Optimierungsaufgaben, bei denen nahezu optimale Lösungen ausreichen.“
