⚛️ quantum physics

A competitive NISQ and qubit-efficient solver for the LABS problem

Diese Arbeit zeigt, dass das Pauli Correlation Encoding (PCE)-Framework, ein qubit-effizienter variationaler Ansatz, das Problem der Low Autocorrelation Binary Sequences (LABS) effektiv löst, indem es eine verbesserte Skalierung und Rauschresistenz aufweist und dabei aktuelle klassische Heuristiken übertrifft, während es signifikant weniger Quantenressourcen benötigt.

Ursprüngliche Autoren: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Veröffentlicht 2026-01-27

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, eine lange Reihe von Menschen anzuordnen, wobei jeder Mensch entweder eine rote Fahne (+1) oder eine blaue Fahne (-1) hält. Ihr Ziel ist es, die Menschen so anzuordnen, dass die Muster aus roten und blauen Fahnen nicht versehentlich auf eine verwirrende Weise aufeinander abgestimmt sind, wenn man die Reihe aus verschiedenen Blickwinkeln betrachtet. In der wissenschaftlichen Welt wird dies als das Low Autocorrelation Binary Sequences (LABS) Problem bezeichnet. Es ist ein notorisch schwieriges Rätsel, das dazu verwendet wird, zu testen, wie gut Computer bei der Lösung schwieriger Optimierungsprobleme sind.

Diese Arbeit stellt einen neuen, cleveren Weg vor, wie Quantencomputer (speziell die derzeitigen, verrauschten Arten, die als NISQ bekannt sind) dieses Rätsel besser lösen können als viele traditionelle Methoden. Hier ist die Aufschlüsselung ihres Ansatzes:

1. Das Problem: Ein „Golfplatz“ voller Fehler

Stellen Sie sich die Suche nach der perfekten Anordnung der Fahnen wie den Versuch vor, den tiefsten Punkt in einer riesigen, nebligen Landschaft zu finden.

Die Landschaft: Meistens wandert man auf einer flachen Ebene mit vielen kleinen Senken (lokale Minima). Diese sehen aus wie der Boden eines Tals, sind aber nicht das echte Tal.
Das Ziel: Die wahre Lösung ist ein einzelnes, winziges, tiefes Loch in der Mitte der Ebene (das globale Minimum).
Die Schwierigkeit: Da es so viele falsche „Böden“ gibt, bleiben Standard-Computerprogramme oft in einem davon stecken und geben auf, in dem Glauben, sie hätten die beste Antwort gefunden, obwohl sie das nicht getan haben.

2. Die Lösung: Eine „komprimierte“ Karte (Pauli Correlation Encoding)

Normalerweise benötigt ein Quantencomputer, um ein Problem mit $N$ Variablen (wie 45 Fahnen) zu lösen, 45 Quantenbits (Qubits). Aber heutige Quantencomputer sind klein und zerbrechlich; sie können noch nicht so viele Bits verarbeiten.

Die Autoren nutzen einen Trick namens Pauli Correlation Encoding (PCE).

Die Analogie: Stellen Sie sich vor, Sie haben eine riesige Bibliothek von Büchern (die 45 Fahnen), aber Sie haben nur ein kleines Notizbuch (4 Qubits). Anstatt jedes einzelne Buch aufzuschreiben, verwenden Sie einen speziellen Code. Sie schreiben die Beziehungen zwischen den Büchern auf.
Wie es funktioniert: Sie bilden die 45 Fahnen auf nur 4 Qubits ab. Es ist, als würde man einen hochauflösenden Film in eine winzige Dateigröße komprimieren, ohne die Handlung zu verlieren. Dies ermöglicht es ihnen, riesige Probleme (bis zu 45 Fahnen in ihrer Simulation und sogar 120 in einem echten Experiment) mit sehr wenigen Quantenressourcen anzugehen.

3. Die Strategie: Die richtigen „Fragen“ stellen

Um das meiste aus diesen 4 Qubits herauszuholen, musste das Team entscheiden, wie man dem Quantencomputer Fragen stellt.

Der kommutierende Satz: Fragen zu stellen, die sich nicht gegenseitig stören (wie das Fragen nach dem Wetter und der Uhrzeit).
Der nicht-kommutierende Satz: Fragen zu stellen, die sich gegenseitig beeinflussen (wie der Versuch, gleichzeitig die Position und die Geschwindigkeit einer rotierenden Münze zu messen).
Das Ergebnis: Sie fanden heraus, dass die „störenden“ Fragen (nicht-kommutierend) viel besser waren. Es ist, als würde man ein Glas voller Murmeln schütteln, um das ganze Bild zu sehen, anstatt nur auf eine Seite zu schauen. Diese Methode lieferte die besten Ergebnisse.

4. Die Leistung: Schneller und intelligenter

Sie haben ihre neue Methode gegen die besten klassischen (regulären) Computerprogramme und andere Quantenmethoden getestet.

Das Rennen: Sie haben die „Time-to-Solution“ (die Zeit bis zur Lösung) gemessen (wie lange es dauert, die perfekte Antwort zu finden).
Das Ergebnis: Ihre Quantenmethode war schneller als die besten klassischen „Heuristiken“ (ein intelligenter Ratgealgorithmus namens Tabu-Suche) für die getesteten Größen.
Die Skalierbarkeit: Während andere Quantenmethoden massive, perfekte Computer benötigen würden, die es noch gar nicht gibt, funktioniert diese Methode auf kleinen, aktuellen Geräten. Sie skaliert besser, was bedeutet, dass ihre Methode, wenn das Problem größer wird, länger wettbewerbsfähig bleibt als die anderen.

5. Der Realwelt-Test: Der „verrauschte“ Spielplatz

Die Autoren haben ihren Algorithmus nicht nur in Simulationen laufen lassen; sie haben ihn tatsächlich auf einem echten Quantencomputer von IonQ (genannt der Forte-Prozessor) ausgeführt.

Die Herausforderung: Reale Quantencomputer sind „verrauscht“. Es ist, als versuche man, ein Flüstern in einem Hurrikan zu hören. Die Hardware macht Fehler.
Das Ergebnis: Sie haben erfolgreich ein Problem mit 120 Fahnen gelöst (die größte Anzahl, die jemals auf Quantenhardware für dieses spezifische Problem gezeigt wurde).
Resilienz: Selbst mit dem „Hurrikan“ des Rauschens war die endgültige Antwort immer noch gut. Sie fanden heraus, dass sie nicht Millionen von Versuchen (Shots) brauchten, um eine brauchbare Antwort zu erhalten; ein paar tausend waren ausreichend. Der Lärm machte die endgültige Antwort jedoch etwas weniger perfekt als eine ideale Simulation.

Zusammenfassung

Das Paper behauptet, dass sie durch eine clevere „Komprimierungstechnik“ (PCE) und das Stellen der richtigen Arten von Fragen (nicht-kommutierende Operatoren) ein sehr schwieriges mathematisches Rätsel (LABS) auf kleinen, unvollkommenen Quantencomputern lösen können. Ihre Methode ist schneller als die besten aktuellen klassischen Ratge-Algorithmen für die getesteten Größen und ist robust genug, um heute auf echter, verrauschter Hardware zu funktionieren. Sie legen nahe, dass dies bereits jetzt ein leistungsstarkes Werkzeug zur Lösung schwieriger Probleme sein kann, noch bevor wir perfekte, fehlerfreie Quantencomputer besitzen.

Technisches Resümee: Ein kompetitiver NISQ- und qubiteneffizienter Solver für das LABS-Problem

Problemdefinition
Das Problem der Low Autocorrelation Binary Sequences (LABS) ist eine bekannte NP-schwere kombinatorische Optimierungsherausforderung mit Anwendungen in den Bereichen Ingenieurwesen, Kommunikation und statistische Physik. Gegeben sei eine ganze Zahl $N$ , wobei das Ziel darin besteht, eine binäre Sequenz $x \in \{-1, +1\^N$ zu finden, die die Nebenlobenergie $E(x)$ minimiert, definiert als die Summe der quadrierten Autokorrelationen $C_\ell(x)$ für $\ell > 0$ . Äquivalent ist das Ziel, den Meritfaktor $F(x) = N^2 / 2E(x)$ zu maximieren. Das Problem ist durch eine „Golfplatz“-Optimierungslandschaft (Golf Course Landscape) mit zahlreichen lokalen Minima und isolierten globalen Minima charakterisiert. Während exakte Lösungen für $N \le 66$ bekannt sind, wird das Finden optimaler oder qualitativ hochwertiger Approximationen für größere $N$ durch klassische Brute-Force-Methoden unpraktikabel, und selbst modernste Heuristiken wie die Memetic Tabu Search stehen vor erheblichen Skalierungsproblemen.

Methodik: Pauli Correlation Encoding (PCE)
Die Autoren schlagen einen qubiteneffizienten variativen Quanten-Solver auf Basis des Pauli Correlation Encoding (PCE)-Frameworks vor. Im Gegensatz zu Standard-Encodings, die einen Qubit pro binärer Variable erfordern, komprimiert PCE $N$ binäre Variablen in $n$ Qubits, wobei $N = \text{poly}(n)$ , spezifisch $n \ll N$ .

Encoding: Binäre Variablen $x_i$ werden als Vorzeichen der Erwartungswerte einer Menge von $n$ -Qubit-Pauli-Strings $\Pi = \{\Pi_i\}_{i \in [N]}$ kodiert:
$x_i := \text{sgn}(\langle \Pi_i \rangle)$
wobei $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$ .
Optimierung: Der Quantenzustand $|\Psi\rangle$ wird durch einen parametrisierten Brickwork-Schaltkreis erzeugt. Die Parameter werden klassisch optimiert, um eine nichtlineare Verlustfunktion $L$ zu minimieren. Um die Gradientenbasierte Optimierung zu erleichtern, werden die binären Variablen mittels einer Hyperbeltangens-Funktion relaxiert: $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$ . Die Verlustfunktion enthält einen Regularisierungsterm, um zu verhindern, dass Korrelatoren verschwinden.
Auswahl der Pauli-Menge: Die Studie evaluiert zwei verschiedene Mengen für $\Pi$ $Π$ :
1. $\Pi(C)$ : Eine Menge zufällig ausgewählter, untereinander kommutierender Pauli-Operatoren.
2. $\Pi(NC)$ : Eine Menge, die darauf ausgelegt ist, die Anzahl untereinander nicht-kommutierender Pauli-Operatoren zu maximieren. Die Autoren hypothetisieren, dass Nicht-Kommutativität zu untereinander ungleichgewichtigen Messungen (mutually unbiased measurements) führt, was die Expressivität und Unabhängigkeit der kodierten Variablen erhöht.

Wesentliche Beiträge und Ergebnisse

Numerische Simulationen ( $N \le 45$ ):
- Die Autoren simulierten den PCE-Solver mit $n=4$ Qubits und einer Schaltungstiefe von 15 Layern (30 Zwei-Qubit-Gates, 150 Parameter).
- Die $\Pi(NC)$ -Variante schnitt konsistent besser ab als die kommutierende Variante.
- Skalierungsanalyse: Die Time-to-Solution (TTS), definiert als die Anzahl der Funktionsauswertungen, um die exakte Lösung zu finden, wurde gegen QAOA und Memetic Tabu Search evaluiert.
  - PCE-Skalierung: $O(1.330^N)$ für gerade Instanzen und $O(1.326^N)$ für ungerade Instanzen.
  - Vergleich: Diese Skalierung verbessert die QAOA-Skalierung von $O(1.46^N)$ und ist geringfügig besser als die Skalierung der State-of-the-Art Tabu Search von $O(1.34^N)$ (für gerade Instanzen) und $O(1.409^N)$ (für ungerade Instanzen).
- Die Ergebnisse deuten auf einen Potenzgesetz-Vorteil (Power-Law Advantage) von PCE gegenüber klassischen Baselines innerhalb des getesteten Bereichs hin.
Experimentelle Demonstration (IonQ Forte):
- Die Autoren führten eine Proof-of-Principle-Demonstration auf dem IonQ Forte Quantenprozessor für eine Instanzgröße von $N=120$ durch, der größten bisher auf Hardware demonstrierten Größe.
- Für das Experiment wurde ein spezifischer, hardwarefreundlicher Satz von $k$ -Körper-Korrelatoren ( $k=2$ ) verwendet, der nur drei Messanordnungen erforderte.
- Rauschresistenz: Die Studie stellte fest, dass, während das Schrotrauschen (Shot Noise) nur einen geringen Einfluss hatte (nur wenige tausend Shots erforderlich waren), das Hardware-Rauschen die Qualität der finalen Lösung signifikant verschlechterte. Der Trainingsprozess selbst blieb jedoch robust, was darauf hindeutet, dass Fehlerminimierung (Error Mitigation) oder höhere Kompressionsraten entscheidend für den Einsatz in der Nähe der NISQ-Ära sind.

Bedeutung und Ansprüche
Das Paper behauptet, dass PCE-basierte Solver zwei Wege vielversprechend darstellen:

Quanteninspirierte klassische Heuristiken: Selbst wenn sie klassisch simuliert werden, bietet das PCE-Framework kompetitive oder überlegene Skalierungen im Vergleich zu führenden klassischen Heuristiken für schwierige Probleme wie LABS, und fungiert somit als leistungsfähiger quanteninspirierter Algorithmus.
Reduktion der NISQ-Ressourcen: Durch die Kodierung von $N$ Variablen in eine polynomisch kleinere Anzahl von Qubits ( $n$ ) reduziert PCE den Qubit-Bedarf für Near-Term-Geräte drastisch. Die Autoren merken an, dass $n=8$ Qubits theoretisch Instanzen bis $N=66$ (wo exakte Lösungen bekannt sind) bewältigen könnten, und $n \le 20$ die größten durch klassische Heuristiken lösbaren Instanzen herausfordern könnten.

Die Autoren nehmen eine bescheidene Haltung bezüglich eines „Quantenvorteils“ (Quantum Advantage) ein. Sie räumen ein, dass der Overhead bei der Simulation vollständiger Quantenzustandsvektoren auf klassischen Systemen den Crossover-Punkt verzögert, an dem ein echter Quanten-Laufzeitvorteil ersichtlich wird. Zudem stellen sie fest, dass die Methode zwar eine starke Performance zeigt, aber derzeit keine Leistungsgarantien bietet. Dennoch unterstreicht die Fähigkeit, $N=120$ Instanzen mit moderaten Shot-Budgets auf aktueller Hardware zu lösen, sowie die Beobachtung der Rauschresistenz das Potenzial von PCE als Werkzeug zur Reduktion der Ressourcenanforderungen in tatsächlichen Quantenalgorithmen.