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

Technische Samenvatting: Een Competitieve NISQ- en Qubit-efficiënte Solver voor het LABS-probleem

Probleemdefinitie
Het Low Autocorrelation Binary Sequences (LABS) probleem is een bekende NP-harde combinatorische optimalisatieuitdaging met toepassingen in engineering, communicatie en statistische fysica. Gegeven een geheel getal $N$, is het doel om een binaire sequentie $x \in \{-1, +1\}^N$ te vinden die de zijlobenergie $E(x)$ minimaliseert, gedefinieerd als de som van gekwadrateerde autocorrelaties $C_\ell(x)$ voor $\ell > 0$. Equivalent aan dit doel is het maximaliseren van de merit factor $F(x) = N^2 / 2E(x)$. Het probleem wordt gekenmerkt door een "golfbaan" (golf course) optimalatielandschap met talrijke lokale minima en geïsoleerde globale minima. Terwijl exacte oplossingen bekend zijn voor $N \le 66$, wordt het vinden van optimale of hoogwaardige benaderende oplossingen voor grotere $N$ onhandelbaar voor klassieke brute-force methoden, en zelfs de meest geavanceerde heuristieken zoals Memetic Tabu Search kampen met aanzienlijke schaalingsproblemen.

Methodologie: Pauli Correlation Encoding (PCE)
De auteurs stellen een qubit-efficiënte variationele quantum solver voor op basis van het Pauli Correlation Encoding (PCE) framework. In tegenstelling tot standaard encodings die één qubit per binaire variabele vereisen, comprimeert PCE $N$ binaire variabelen naar $n$ qubits waarbij $N = \text{poly}(n)$, specifiek $n \ll N$.

• Encoding: Binaire variabelen $x_i$ worden gecodeerd als de tekens van de verwachtingswaarden van een set $n$-qubit Pauli-strings $\Pi = \{\Pi_i\}_{i \in [N]}$:
  $$x_i := \text{sgn}(\langle \Pi_i \rangle)$$
  waarbij $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$.
• Optimalisatie: De quantumtoestand $|\Psi\rangle$ wordt gegenereerd door een geparametriseerd brickwork-circuit. De parameters worden klassiek geoptimaliseerd om een niet-lineaire verliesfunctie $L$ te minimaliseren. Om gradiëntgebaseerde optimalisatie te faciliteren, worden de binaire variabelen versoepeld met behulp van een hyperbolische tangensfunctie: $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$. De verliesfunctie bevat een regularisatieterm om te voorkomen dat correlatoren verdwijnen.
• Pauli Set Selectie: De studie evalueert twee verschillende sets voor $\Pi$:
  1. $\Pi(C)$: Een set willekeurig geselecteerde, onderling commuterende Pauli-operatoren.
  2. $\Pi(NC)$: Een set ontworpen om het aantal onderling niet-commuterende Pauli-operatoren te maximaliseren. De auteurs hypothetiseren dat niet-commutativiteit leidt tot onderling ongebalanceerde metingen (mutually unbiased measurements), waardoor de expressiviteit en onafhankelijkheid van de gecodeerde variabelen toenemen.

Belangrijkste Bijdragen en Resultaten

1. Numerieke Simulaties ($N \le 45$):

   • De auteurs simuleerden de PCE-solver met $n=4$ qubits en een circuitdiepte van 15 lagen (30 twee-qubit gates, 150 parameters).
   • De $\Pi(NC)$-variant presteerde consequent beter dan de commuerende variant.
   • Schaalanalyse: De Time-to-Solution (TTS), gedefinieerd als het aantal kostenfunctie-evaluaties dat nodig is om de exacte oplossing te vinden, werd vergeleken met QAOA en Memetic Tabu Search.
     • PCE Schaling: $O(1.330^N)$ voor even instanties en $O(1.326^N)$ voor oneven instanties.
     • Vergelijking: Deze schaling is een verbetering ten opzichte van de QAOA-schaling van $O(1.46^N)$ en is marginaal beter dan de state-of-the-art Tabu Search schaling van $O(1.34^N)$ (voor even instanties) en $O(1.409^N)$ (voor oneven instanties).
     • De resultaten wijzen op een machtswet-voordeel (power-law advantage) van PCE ten opzichte van klassieke baselines binnen het geteste bereik.

2. Experimentele Demonstratie (IonQ Forte):

   • De auteurs voerden een proof-of-principle demonstratie uit op de IonQ Forte quantumprocessor voor een instantiegrootte van $N=120$, de grootste die tot nu toe op quantumhardware is gedemonstreerd.
   • Voor het experiment werd een specifieke hardwarevriendelijke set van $k$-body correlatoren ($k=2$) gebruikt, wat slechts drie meetopstellingen vereiste.
   • Ruisresistentie: De studie toonde aan dat hoewel shot noise een minimale impact had (slechts enkele duizenden shots vereiste), hardware-ruis de kwaliteit van de uiteindelijke oplossing aanzienlijk verslechterde. Echter, het trainingsproces zelf bleef robuust, wat suggereert dat foutcorrectie (error mitigation) of hogere compressieratio's cruciaal zijn voor nabije inzetbaarheid (near-term deployment).

Betekenis en Claims
Het artikel stelt dat PCE-gebaseerde solvers een veelbelovende aanpak vormen voor twee verschillende wegen:

1. Quantum-geïnspireerde Klassieke Heuristieken: Zelfs wanneer ze klassiek worden gesimuleerd, bieden de PCE-framework een competitieve of superieure schaling vergeleken met leidende klassieke heuristieken voor harde problemen zoals LABS, en fungeren ze als een krachtig quantum-geïnspireerd algoritme.
2. NISQ-resource Reductie: Door $N$ variabelen te coderen in een polynomiaal kleiner aantal qubits ($n$), vermindert PCE de qubit-vereisten voor nabije quantum-apparaten drastisch. De auteurs merken op dat $n=8$ qubits theoretisch instanties tot $N=66$ (waar exacte oplossingen bekend zijn) zouden kunnen aanpakken, en $n \le 20$ de grootste instanties die klassiek oplosbaar zijn, zou kunnen uitdagen.

De auteurs hanteren een bescheiden standpunt met betrekking tot "quantum advantage". Ze erkennen dat de overhead van het simuleren van volledige quantum state vectors in klassieke benchmarks het kantelpunt vertraagt waarop een echt quantum runtime-voordeel zichtbaar wordt. Bovendien merken ze op dat hoewel de methode sterke prestaties laat zien, deze momenteel geen prestatiegaranties biedt. Desalniettemin onderstreept het vermogen om $N=120$ instanties op huidige hardware op te lossen met een bescheiden shot-budget, samen met de observatie van ruisresistentie, het potentieel van PCE als een instrument om de resource-vereisten in werkelijke quantumalgoritmen te verminderen.