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

1. Il Problema

Il lavoro affronta la sfida del decodifica dei codici correttori di errore classici (come i codici a blocco lineari e i codici convoluzionali) in un contesto di calcolo quantistico, specificamente per i dispositivi NISQ (Noisy Intermediate-Scale Quantum).

• Contesto: La decodifica a massima verosimiglianza (ML) è un problema NP-difficile per una classe generale di codici lineari. L'approccio classico esaustivo ha una complessità temporale esponenziale $O(2^n)$.
• Limiti delle soluzioni precedenti: Gli algoritmi quantistici basati su Grover offrono un vantaggio quadratico, ma richiedono profondità di circuito elevate e sono vulnerabili al rumore dei dispositivi NISQ. Algoritmi precedenti basati sull'amplificazione iterativa delle ampiezze (IAA) per la decodifica di Viterbi quantistica soffrono di un'overhead di profondità che li rende inefficienti per l'hardware attuale.
• Obiettivo: Sviluppare un decodificatore Viterbi ibrido quantistico-classico che sia efficiente, a bassa profondità e adatto ai dispositivi NISQ, utilizzando l'algoritmo di ottimizzazione quantistica approssimata (QAOA).

2. Metodologia

Gli autori propongono una mappatura del problema di decodifica Viterbi basato su trellis in un problema di ottimizzazione combinatoria risolvibile tramite QAOA.

A. Mappatura del Problema

• Funzione di Costo: Il problema di trovare il percorso nel trellis con la minima distanza di Hamming rispetto al vettore ricevuto errato $y$ è formulato come la minimizzazione di una funzione di costo pseudo-booleana: $f(c) = \sum (c_i \oplus y_i)$.
• Hamiltoniana di Costo ($H_f$): Questa funzione è mappata in un'Hamiltoniana diagonale composta da operatori di Pauli-Z. L'Hamiltoniana agisce su due registri: uno per il codeword candidato ($x$) e uno per il vettore ricevuto ($r$), inizializzato secondo gli errori osservati.

B. Costruzione dell'Hamiltoniana del Mixer ($H_m$)

Un aspetto cruciale è la conservazione dello spazio di ricerca (lo spazio dei codeword validi $C$).

• Teorema 1: Gli autori dimostrano che per preservare lo spazio dei codici, l'Hamiltoniana del mixer deve essere costruita come somma di operatori di Pauli-X locali di grado $d$, dove $d$ è la distanza di Hamming minima del codice.
• Questo garantisce che l'evoluzione temporale non porti lo stato fuori dallo spazio dei codici validi, mantenendo la coerenza del problema di decodifica.

C. Circuito Quantistico Parametrizzato (PQC)

Il circuito QAOA è composto da strati alternati di unitari di costo $U_f(\gamma)$ e mixer $U_m(\beta)$.

• Lo stato iniziale è una sovrapposizione uniforme di tutti i codeword validi, generata tramite un operatore di codifica $U_g$ basato sulla matrice generatrice del codice.
• La profondità del circuito dipende dalla struttura del codice classico (in particolare da $d$ e dal numero di codeword a peso minimo).

D. Strategia di Ottimizzazione Uniforme (UPO)

Per superare il problema dei "barren plateaus" (piani sterili) e la difficoltà di ottimizzare i parametri in circuiti profondi, gli autori introducono una strategia innovativa:

• Uniform Parameter Optimization (UPO): Invece di ottimizzare ogni parametro $\gamma_i$ e $\beta_i$ individualmente (come nel Fixing Parameter Optimization - FPO) o di usare inizializzazioni casuali, l'UPO impone che tutti i parametri di costo siano uguali ($\gamma_1 = ... = \gamma_p = \gamma_0$) e tutti i parametri del mixer siano uguali ($\beta_1 = ... = \beta_p = \beta_0$).
• Questo riduce drasticamente il numero di parametri da ottimizzare e semplifica il paesaggio di ottimizzazione, rendendo il circuito più "addestrabile" anche a basse profondità.

3. Contributi Chiave

1. Mappatura Generale QAOA-Viterbi: Sviluppo di un metodo generalizzato per mappare il problema di decodifica Viterbi per qualsiasi codice a blocco lineare in un circuito QAOA, definendo esplicitamente le Hamiltoniane di costo e mixer.
2. Teorema sul Mixer Hamiltoniano: Dimostrazione formale che il mixer deve essere composto da operatori $d$-locali (dove $d$ è la distanza minima del codice) per garantire la conservazione dello spazio dei codici.
3. Strategia UPO: Proposta e validazione della strategia di ottimizzazione dei parametri uniformi, che si dimostra superiore alle tecniche di inizializzazione casuale e di fissaggio dei parametri (FPO) nella ricerca di soluzioni ottimali.
4. Efficienza NISQ: Dimostrazione che l'approccio ibrido produce circuiti a bassa profondità, rendendolo fattibile per l'hardware quantistico attuale, a differenza di algoritmi basati su Grover o IAA.

4. Risultati Sperimentali

Le simulazioni sono state eseguite utilizzando il framework Qiskit e il simulatore QASM di IBM Quantum Experience su diversi codici lineari:

• Codice [6, 3, 3]: Il decodificatore ibrido ha identificato con alta probabilità il percorso con la minima distanza di Hamming per vettori ricevuti errati. La strategia UPO ha mostrato un'ampificazione del stato soluzione nettamente superiore rispetto all'FPO, con un paesaggio di ottimizzazione non piatto.
• Codice [9, 4, 4] e [3, 2, 1]: L'algoritmo ha correttamente identificato i percorsi ottimali. Nel caso del codice [3, 2, 1], il sistema ha correttamente restituito due stati con probabilità elevata quando esistevano due percorsi con metrica minima equivalente, allineandosi alla teoria.
• Confronto con Decodificatori Classici: Il decodificatore ibrido è stato confrontato con un decodificatore a propagazione della credibilità (belief propagation) basato su codici di ripetizione. I tassi di errore di parola (WER) sono risultati quasi identici, confermando l'accuratezza del metodo ibrido.
• Superiorità dell'UPO: I grafici delle probabilità di occorrenza mostrano che l'UPO è più robusto e regolare nell'amplificare lo stato soluzione rispetto all'FPO, che mostra risultati più casuali e fallimenti in alcune istanze di training.

5. Significato e Implicazioni

• Vantaggio Quantistico Pratico: Il lavoro dimostra che l'approccio QAOA, combinato con l'ottimizzazione uniforme, può offrire un'alternativa efficiente ai metodi classici per la decodifica, evitando la complessità esponenziale dei metodi ML classici e la profondità eccessiva degli algoritmi quantistici puri.
• Adattabilità ai Dispositivi NISQ: La capacità di funzionare con circuiti a bassa profondità e di gestire il rumore attraverso l'ibridazione quantistico-classica rende questa soluzione promettente per l'implementazione immediata.
• Scalabilità e Futuro: Sebbene la profondità del circuito dipenda dalla struttura del codice (potenzialmente limitante per codici molto grandi), l'approccio apre la strada a problemi di inferenza più ampi oltre alla semplice decodifica. Gli autori notano che per codici molto grandi potrebbe essere necessaria l'integrazione con codici di correzione d'errore quantistici (QECC) per gestire il rumore.

In sintesi, il paper presenta un avanzamento significativo nell'uso di algoritmi variazionali per problemi di comunicazione classica, offrendo una strategia concreta (UPO) per rendere il QAOA praticabile su hardware reale per la decodifica di errori.