Resource-Efficient Digitized Adiabatic Quantum Factorization

Technische Zusammenfassung: Ressourceneffiziente digitalisierte adiabatische Quantenfaktorisierung

Problemstellung
Die vorliegende Arbeit befasst sich mit der Herausforderung, effiziente adiabatische Quantenfaktorisierung auf digitalisierten (gate-basierten) Quantencomputern zu implementieren. Standardansätze, wie die von Peng et al. [1] vorgeschlagene Methode, formulieren die Ganzahlfaktorisierung als Grundzustandssuche für einen Problem-Hamiltonoperator, der aus einer polynomischen unbeschränkten binären Optimierungsfunktion (PUBO) abgeleitet wird. Diese Formulierung führt zu einem Hamiltonoperator, der nicht-lokale Drei- und Vier-Qubit-Wechselwirkungen ($Z^3$ und $Z^4$) enthält. Auf digitalisierten Geräten erfordern diese hochgradigen Wechselwirkungen die Zerlegung in mehrere native Zwei-Qubit-Gatter (z. B. CNOTs), was zu tiefen Schaltkreisen mit hohen Gatteranzahlen führt. Diese Komplexität begrenzt die Fidelität und Skalierbarkeit des Algorithmus erheblich, wobei die Erfolgswahrscheinlichkeiten selbst bei Anwendung von Techniken des maschinellen Lernens für Zahlen größer als 91 drastisch sinken.

Methodik
Die Autoren schlagen einen neuartigen digitalisierten adiabatischen Algorithmus vor, der das Faktorisierungsproblem unter Verwendung eines quadratischen unbeschränkten binären Optimierungsrahmens (QUBO) neu formuliert. Der methodische Kernwechsel umfasst zwei wesentliche Änderungen:

1. Kernel-Subraum-Kodierung: Anstatt die Lösung als Grundzustand (Energie-Minimum Null) einer quadrierten Funktion $F^2$ zu kodieren, definieren die Autoren den Problem-Hamiltonoperator $\hat{H}_{LP}$ als die lineare Funktion $F(N, \hat{p}', \hat{q}')$ selbst. In dieser Formulierung entspricht die Lösung dem Null-Energie-Eigenzustand (dem Kernel-Subraum) des Hamiltonoperators, welcher ein angeregter Zustand relativ zum globalen Spektrum ist, anstatt des Grundzustands.
2. QUBO-Formulierung: Durch die Nutzung der linearen Funktion enthält der resultierende Hamiltonoperator nur Zwei-Körper-Wechselwirkungen, wodurch das Problem als QUBO klassifiziert wird. Dies eliminiert die Notwendigkeit für NP-schwere polynomische Reduktionen und Hilfsvariablen, die typischerweise zur Abbildung von PUBO-Problemen auf QUBO erforderlich sind.

Der Algorithmus wird mittels eines variativen Quantenalgorithmus (speziell QAOA) implementiert. Das Protokoll initialisiert das System in einem Gleichverteilungszustand (speziell $|+\rangle|-\rangle\dots$, um mit dem Null-Subraum von $\hat{H}_{LP}$ zu korrespondieren) und entwickelt es unter Verwendung alternierender Unitaris, die aus dem Kosten-Hamiltonoperator ($\hat{H}_{LP}$) und einem Misch-Hamiltonoperator ($\hat{H}_M$) abgeleitet sind. Die durch klassische Optimierer minimierte Kostenfunktion ist definiert als der Erwartungswert des Absolutbetrags des Hamiltonoperators, $C_{LP} = \langle |\hat{H}_{LP}| \rangle$, um die Konvergenz gegen die Null-Eigenwert-Lösung sicherzustellen.

Wesentliche Beiträge

• Schaltkreisvereinfachung: Der vorgeschlagene QUBO-Ansatz reduziert den Problem-Hamiltonoperator auf Zwei-Körper-Wechselwirkungen. Dies macht die Zerlegung komplexer Multi-Qubit-Gatter überflüssig und reduziert die Tiefe der Schaltkreise signifikant.
• Neue Kodierungsstrategie: Die Arbeit zeigt, dass adiabatische Faktorisierung erfolgreich durchgeführt werden kann, indem man den Kernel-Subraum (den angeregten Zustand der Null-Energie) statt des Grundzustands ansteuert und so die Einschränkungen von PUBO-Formulierungen umgeht.
• Robustheitsanalyse: Die Autoren analysieren die Spektraldichte der Hamiltonoperatoren und zeigen, dass die QUBO-Formulierung eine dünnere Zustandsdichte um den Lösungs-Subraum aufweist als die PUBO-Formulierung, was hilft, lokale Minima und Barren Plateaus während der Optimierung zu vermeiden.

Ergebnisse
Die Autoren haben ihren QUBO-basierten Algorithmus gegen den Standard-PUBO-Ansatz zur Faktorisierung von ganzen Zahlen bis zu 8 Bit (speziell $N=25, 119, 143$) getestet.

• Gatterkomplexität: Für eine einzelne Schicht des QAOA-Schaltkreises benötigt der QUBO-Ansatz signifikant weniger CNOT-Gatter. Beispielsweise erfordert die Faktorisierung von $N=25$ acht CNOT-Gatter pro Schicht für die QUBO-Methode, im Vergleich zu 34 CNOT-Gattern für die PUBO-Methode (nach Zerlegung der Drei- und Vier-Qubit-Gatter).
• Fidelität und Konfidenz: Der QUBO-Algorithmus weist eine wesentlich höhere Fidelität bei der Identifizierung der korrekten Faktoren auf. Für größere Zahlen wie $N=119$ und $N=143$ versagt der PUBO-Ansatz darin, die Wahrscheinlichkeitsamplitude auf die korrekte Lösung zu konzentrieren, was zu niedrigen Konfidenzwerten und hoher Shannon-Entropie führt. Im Gegensatz dazu besetzt der QUBO-Ansatz die korrekten Lösungszustände erfolgreich.
• Konvergenz der Kostenfunktion: Der QUBO-Algorithmus erreicht eine tiefere Reduktion der Kostenfunktion (bis zu 3 Größenordnungen für $N=143$) im Vergleich zum PUBO-Ansatz (bis zu 2 Größenordnungen), was auf eine effektivere Optimierung hindeutet.
• Spektralanalyse: Die Analyse der Energiespektren zeigt, dass der PUBO-Hamiltonoperator eine hohe Zustandsdichte nahe der Lösung besitzt, was eine „flache“ Landschaft erzeugt, die klassische Optimierer behindert. Der QUBO-Hamiltonoperator weist ein breiter gestreutes Spektrum mit größeren Energielücken nahe dem Kernel-Subraum auf, was die Zustandspräparation erleichtert.

Bedeutung und Ansprüche
Die Arbeit behauptet, dass diese Untersuchung einen ressourceneffizienten Weg für die digitalisierte adiabatische Quantenfaktorisierung bietet. Die primäre Bedeutung liegt in der erheblichen Reduktion der Schaltkreiskomplexität und der damit einhergehenden Steigerung der algorithmischen Fidelität, was die Faktorisierung größerer ganzer Zahlen auf Geräten der nächsten Generation (near-term devices) ermöglicht.

Die Autoren betonen, dass das Ansteuern eines angeregten Zustands (des Kernels) zwar für Quanten-Annealer aufgrund des Fehlens von Grundzustand-Dekohärenzschutz schwierig ist, jedoch für digitalisierte Quanten-Annealer vorteilhaft ist. In Gate-basierten Systemen, in denen Dekohärenz oft durch lokale Einzel-Qubit-Zerfallsprozesse bestimmt wird, minimiert die reduzierte Gatteranzahl des QUBO-Ansatzes die Gesamtlaufzeit und die Expositionszeit gegenüber Fehlern. Die Ergebnisse legen nahe, dass QUBO-basierte Formulierungen in der QAOA-basierten Optimierung besser abschneiden können als PUBO-basierte Formulierungen, was der bisherigen Literatur widerspricht, die davon ausging, dass PUBO für bestimmte Problemstrukturen notwendig oder überlegen sei. Die Arbeit motiviert zur weiteren Erforschung digitalisierter adiabatischer Protokolle für breitere zahlentheoretische Probleme und komplexe Hamiltonoperatoren.