Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes

Probleemstelling

Klassieke foutcorrigerende codes (zoals lineaire blokcodes en convolutiecodes) zijn essentieel voor betrouwbare communicatie en dataopslag. Het decoderen van deze codes, specifiek het vinden van het meest waarschijnlijke verzonden codewoord uit een ontvangen, door ruis verstoord signaal, is een complex probleem.

• Maximum Likelihood (ML) Decoding: De standaardmethode is ML-decoding, maar deze heeft een exponentiële tijdscomplexiteit van $O(2^n)$ en is NP-hard voor algemene lineaire codes.
• Viterbi Decoding: Een veelgebruikte aanpak is de Viterbi-decoder, die een trellis-structuur gebruikt om het pad met de minimale Hamming-afstand (het kortste pad) te vinden. Hoewel dit efficiënter is dan brute-force ML voor sommige codes, blijft het een zware berekening.
• Quantum Uitdagingen: Bestaande quantum-algoritmen voor dit probleem, zoals die gebaseerd op Grover's zoekalgoritme of Iteratieve Amplitude Amplification (IAA), hebben vaak een hoge circuitdiepte. Dit maakt ze onpraktisch voor huidige "Noisy Intermediate-Scale Quantum" (NISQ) apparaten, die beperkt zijn in qubit-kwaliteit en coherentie-tijd. Daarnaast lijden variational quantum algoritmen vaak aan "barren plateaus" (vlakke optimalisatielandschappen), waardoor het vinden van goede parameters voor diepe circuits extreem moeilijk wordt.

Methodologie

De auteurs stellen een hybride quantum-klassieke decoder voor die het Viterbi-decoderingsprobleem vertaalt naar een optimalisatieprobleem opgelost met het Quantum Approximate Optimization Algorithm (QAOA).

1. Mapping naar QAOA:

   • Kostfunctie (Cost Hamiltonian $H_f$): De Hamming-afstand tussen het ontvangen vector $y$ en een mogelijke codewoord $c$ wordt gemodelleerd als een diagonale Hamilton-operator. De eigenwaarden van deze operator corresponderen met de kosten (de afstand).
   • Mixer Hamiltonian ($H_m$): Een cruciale innovatie is de constructie van een mixer die de zoekruimte beperkt tot de geldige codespace $\mathcal{C}$. Volgens Stelling 1 wordt de mixer Hamiltonian samengesteld uit de som van $d$-lokale Pauli-X operatoren, waarbij $d$ de minimale Hamming-afstand van de code is. Dit zorgt ervoor dat de quantum-superpositie alleen evolueert binnen de geldige codewoorden en niet naar ongeldige toestanden.
   • Circuit Architectuur: De auteurs bouwen een Parameterized Quantum Circuit (PQC) dat bestaat uit lagen van de kost-unitary ($e^{-i\gamma H_f}$) en de mixer-unitary ($e^{-i\beta H_m}$). De initiële toestand is een uniforme superpositie van alle geldige codewoorden.

2. Uniforme Parameter Optimalisatie (UPO):

   • Een groot obstakel bij QAOA is het vinden van de optimale parameters ($\gamma$ en $\beta$) voor de PQC, vooral bij diepe circuits.
   • De auteurs introduceren een strategie genaamd Uniform Parameter Optimization (UPO). In plaats van elke laag in het circuit een unieke set parameters te geven, worden alle $\gamma$-parameters gelijkgesteld aan één waarde ($\gamma_0$) en alle $\beta$-parameters aan één waarde ($\beta_0$).
   • Dit reduceert het aantal te optimaliseren parameters drastisch en voorkomt de "barren plateaus" die vaak optreden bij willekeurige initialisatie of per-laag optimalisatie (Fixed Parameter Optimization - FPO).

Belangrijkste Bijdragen

• Generalisatie van Viterbi naar QAOA: De paper biedt een algemene methode om het Viterbi-decoderingsprobleem voor elke klassieke lineaire blokcodering te mappen naar een QAOA-probleem, inclusief de constructie van de specifieke mixer Hamiltonian gebaseerd op de code-structuur.
• UPO Strategie: De introductie van de Uniform Parameter Optimization strategie. Dit is een heuristiek die bewezen effectiever is dan willekeurige initialisatie en bestaande methoden zoals FPO (Fixed Parameter Optimization) voor het vinden van goede parameters in ondiepe circuits.
• Efficiëntie voor NISQ: Het ontwerp resulteert in lage diepte circuits, wat het toepasbaar maakt voor huidige quantum hardware, in tegenstelling tot eerdere quantum-Viterbi pogingen die te veel resources vereisten.

Resultaten

De auteurs hebben hun algoritme gesimuleerd met behulp van de Qiskit-simulator van IBM Quantum Experience voor verschillende codes, waaronder:

• $[6, 3, 3]$ Code: Bij ontvangst van een verstoord vector $y = 111011$, vond de hybride decoder met UPO het codewoord $011011$ met de hoogste waarschijnlijkheid. Dit pad had de minimale Hamming-afstand (1) tot het ontvangen signaal.
• $[9, 4, 4]$ en $[3, 2, 1]$ Codes: De methode slaagde erin om de juiste paden te identificeren, inclusief gevallen waar meerdere paden dezelfde minimale afstand hadden (in het geval van de $[3,2,1]$ code werden twee oplossingen met gelijke waarschijnlijkheid gevonden, wat theoretisch correct is).
• Vergelijking UPO vs. FPO: Grafieken tonen aan dat UPO leidt tot een veel regelmatiger en hoger versterkt waarschijnlijkheidsprofiel voor de oplossing dan FPO. FPO toonde willekeurige resultaten en faalde vaak om de juiste parameters te vinden.
• Vergelijking met Belangrijke Propagatie: Bij het benchmarken tegen een klassieke "min-sum belief propagation" decoder voor repetitiecodes, vertoonde de hybride quantum-classieke decoder een vergelijkbare woordfoutratio (WER), wat aantoont dat het een actieve en betrouwbare decoder is.

Betekenis en Toekomstperspectief

• Efficiëntere Quantum Decodering: Dit werk toont aan dat variational quantum algoritmen (QAOA) een haalbaar alternatief kunnen zijn voor klassieke decoderingsproblemen, mits de circuitdiepte laag wordt gehouden en slimme optimalisatiestrategieën (zoals UPO) worden gebruikt.
• Overbrugging van NISQ-beperkingen: Door de afhankelijkheid van de circuitdiepte te koppelen aan de code-structuur en de parameters te uniformeren, maakt dit de weg vrij voor implementatie op huidige quantum-processors.
• Toekomstige Werkzaamheden: De auteurs wijzen erop dat voor grotere codes de complexiteit van de mixer Hamiltonian toeneemt, wat extra quantum-error-correctie zal vereisen voor praktische implementatie. Verder onderzoek zal zich richten op het testen van grotere codes en het uitbreiden van de methode naar andere inferentieproblemen buiten codering.

Samenvattend biedt dit artikel een robuust kader voor het gebruik van quantum computing voor klassieke foutcorrectie, waarbij de combinatie van een zorgvuldig ontworpen mixer Hamiltonian en een efficiënte parameter-optimalisatiestrategie (UPO) de barrières van huidige quantum hardware overbrugt.