Decodifica esatta a massima verosimiglianza oltre la larghezza degli alberi tramite programmazione dinamica su decomposizioni di rango

Abstract degli autori

La decodifica a massima verosimiglianza offre una strategia di decodifica ottimale per la correzione degli errori quantistici in presenza di rumore di Pauli stocastico. Tuttavia, calcolare le probabilità delle classi logiche è difficile e la principale contrazione esatta di reti tensoriali richiede un tempo esponenziale nella larghezza degli alberi. In questo lavoro presentiamo un nuovo algoritmo di decodifica basato sulla programmazione dinamica su decomposizioni di rango (Rank DP). Esprimiamo le funzioni di partizione della decodifica con fattori locali di guasto indipendenti come somme quadratiche di potenze e applichiamo Rank DP. Il valutatore esatto così ottenuto ha una complessità aritmetica polinomiale nella dimensione dell’input ed esponenziale nella larghezza di rango del grafo di Tanner rispetto alla partizione dei guasti, compresa la costruzione della decomposizione. Dopo l’eliminazione gaussiana, consente di decodificare in tempo polinomiale codici di Reed-Muller punteggiati e una famiglia concatenata con il codice di Steane, la cui distanza cresce, in presenza di rumore di Pauli indipendente sui singoli qubit. La contrazione standard delle reti tensoriali corrispondenti richiede un tempo superpolinomiale. Una realizzazione non negativa fornisce limiti all’errore relativo in virgola mobile sotto ipotesi aritmetiche esplicite. Gli esperimenti numerici dimostrano vantaggi nei tempi di esecuzione rispetto alle implementazioni di reti tensoriali testate, su istanze selezionate a capacità del codice e a livello di circuito, con una valutazione completa delle verosimiglianze per codici di Reed-Muller fino a $1{,}023$ qubit. Usiamo inoltre queste verosimiglianze per apprendere i parametri del rumore di circuito a partire dai sindromi, valutare probabilità rare di postselezione e quantificare i divari di ottimalità del decodificatore. Il nostro lavoro apre nuove strade per sfruttare la struttura algebrica nella decodifica quantistica e nella caratterizzazione del rumore.