Press "Enter" to skip to content

Russische Wissenschaftler brechen Googles Quantenalgorithmus

Quantenalgorithmus-Konzeptdesign

Wissenschaftler des Skolkovo-Instituts für Wissenschaft und Technologie (Skoltech), eines privaten Forschungsinstituts für Hochschulabsolventen in Moskau, Russland, entdeckten und quantifizierten, was eine grundlegende Einschränkung des von Google initiierten wild angenommenen Quantenansatzes zu sein scheint.

Google ist bestrebt, quantenverbesserte Prozessoren zu entwickeln, die quantenmechanische Effekte nutzen, um die Geschwindigkeit, mit der Daten verarbeitet werden können, eines Tages drastisch zu erhöhen.

Kurzfristig hat Google neue quantenverbesserte Algorithmen entwickelt, die bei realistischem Rauschen funktionieren. Der sogenannte quantennäherungsoptimierungsalgorithmus, kurz QAOA, ist der Eckpfeiler eines modernen Strebens nach rauschtoleranter quantenverstärkter Algorithmusentwicklung.

Der gefeierte Ansatz von Google in der QAOA hat großes kommerzielles Interesse geweckt und eine globale Forschungsgemeinschaft dazu veranlasst, neuartige Anwendungen zu untersuchen. Über die endgültigen Leistungsbeschränkungen des QAOA-Algorithmus von Google ist jedoch noch wenig bekannt.

Ein Team von Wissenschaftlern aus dem Deep Quantum Laboratory von Skoltech nahm diese zeitgemäße Herausforderung an. Das von Prof. Jacob Biamonte geleitete All-Skoltech-Team entdeckte und quantifizierte eine grundlegende Einschränkung des von Google initiierten Ansatzes.

Leistung von QAOA-Schaltkreisen mit fester Tiefe

Das Diagramm zeigt die Leistung (Differenz zwischen QAOA-Optima und exakten Optima) von QAOA-Schaltkreisen mit fester Tiefe auf zufällig generierten MAX-SAT-Instanzen mit zunehmender Problemdichte. Versionen mit höherer Tiefe erzielen zwar bessere Leistungen, weisen jedoch immer noch Erreichbarkeitsdefizite auf. Gutschrift: Physical Review Letters

Berichterstattung Briefe zur körperlichen ÜberprüfungDie Autoren beschreiben detailliert die Entdeckung sogenannter Erreichbarkeitsdefizite – die Autoren zeigen, wie diese Defizite die Fähigkeit von QAOA, eine Lösung für eine Probleminstanz überhaupt zu approximieren, grundlegend einschränken.

Die Ergebnisse des Skoltech-Teams zeigen eine klare Einschränkung des variierenden QAOA-Quantenalgorithmus. QAOA und andere Variationsquantenalgorithmen haben sich aufgrund eines internen Quanten-zu-Klassik-Rückkopplungsprozesses als äußerst schwierig mit bekannten mathematischen Techniken zu analysieren erwiesen. Eine gegebene Quantenberechnung kann nämlich nur für eine feste Zeitspanne ausgeführt werden. Innerhalb dieser festen Zeit kann eine feste Anzahl von Quantenoperationen ausgeführt werden. QAOA versucht, diese Quantenoperationen iterativ zu nutzen, indem eine Folge von zunehmend optimalen Approximationen gebildet wird, um eine Zielfunktion zu minimieren. Die Studie setzt diesem Prozess neue Grenzen.

Die Autoren entdeckten, dass die Fähigkeit von QAOA, optimale Lösungen für jeden Quantenkreis mit fester Tiefe zu approximieren, im Wesentlichen von den Problemen „Dichte“ abhängt. Im Fall des als MAX-SAT bezeichneten Problems kann die sogenannte Dichte als das Verhältnis der Problembeschränkungen zur Variablenanzahl definiert werden. Dies wird manchmal als Klauseldichte bezeichnet.

Die Autoren entdeckten Problemfälle mit hoher Dichte, deren optimale Lösungen unabhängig von der Laufzeit der Algorithmen nicht mit garantiertem Erfolg angenähert werden können.

Referenz: “Erreichbarkeitsdefizite bei der Quantennäherungsoptimierung” von V. Akshay, H. Philathong, M.E.S. Morales und J.D. Biamonte, 5. März 2020, Physik-Review-Briefe.
DOI: 10.1103 / PhysRevLett.124.090504