The Signal
Un preprint non prevede un’accelerazione esponenziale della DQI con decoder locali
Uno studio teorico collega i limiti dei decoder quantistici locali per l’interferometria quantistica con decodifica a una soglia della fisica statistica. Gli autori non si aspettano un’accelerazione esponenziale del campionamento per le istanze studiate, ma precisano che il confronto dipende da una previsione sul campionamento classico.

Secondo un nuovo studio teorico, i decoder quantistici locali presentano un limite che rende improbabile un’accelerazione esponenziale del campionamento per una classe di problemi di interferometria quantistica con decodifica. Gli autori non si aspettano che lo stesso approccio offra vantaggi nell’ottimizzazione approssimata alle condizioni sulle funzioni di ampiezza da loro studiate, anche se il confronto con il campionamento classico si basa su una previsione anziché su una dimostrazione.
Fonte arxiv.org
Il preprint teorico è stato inviato ad arXiv il 9 novembre. Gli autori lavorano presso Global Technology Applied Research di JPMorganChase. Il risultato riguarda istanze sparse, casuali e regolari con k almeno pari a 3, non tutti i problemi che l’interferometria quantistica con decodifica potrebbe affrontare.
Una soglia di decodifica
L’interferometria quantistica con decodifica, o DQI, riformula l’ottimizzazione di problemi con vincoli lineari sparsi e il campionamento dalle loro misure di Gibbs come un problema di decodifica di un codice lineare a partire da uno stato quantistico. Il compito del decoder è recuperare una parola di codice dai qudit; le sue prestazioni sono uno dei fattori che determinano le prestazioni della DQI.
Lo studio si concentra sulle funzioni di ampiezza che dipendono da una soluzione attraverso il suo costo totale. Per il problema Max-XORSAT, tale costo è il numero di equazioni violate. I decoder locali stimano un simbolo della parola di codice utilizzando i qudit in un intorno limitato del simbolo stesso.
Gli autori affermano di aver dimostrato che, oltre un punto chiamato soglia di ricostruzione dell’albero, nessun decoder locale può recuperare l’intera parola di codice con alta probabilità nel contesto studiato. L’ostacolo riguarda le informazioni disponibili localmente, piuttosto che la complessità computazionale di una particolare misurazione.
Il team ha inoltre scoperto che un decoder basato sulla propagazione delle credenze con messaggi quantistici, o BPQM, raggiunge la soglia. Il decoder misura opportuni intorni locali e recupera poi i simboli rimanenti risolvendo congruenze lineari.
Il punto sul confronto con il campionamento classico
Il confronto con il campionamento classico è condizionato. Un metodo della fisica statistica noto come metodo delle cavità prevede che le catene di Markov locali raggiungano rapidamente l’equilibrio fino alla stessa soglia, ma l’articolo indica come problema aperto l’individuazione di un algoritmo classico di campionamento in tempo polinomiale valido nell’intera regione al di sotto di tale soglia.
Per l’ottimizzazione approssimata, gli autori non si aspettano alcun vantaggio con i decoder locali quando le funzioni di ampiezza dipendono soltanto dal numero di vincoli violati. I loro limiti generali di approssimazione presuppongono funzioni di ampiezza simmetriche che non dipendono dall’offset, nonché un recupero affidabile della parola di codice.
Un decoder più ampio e le questioni aperte
L’articolo esamina anche il decoder ottimale, noto come pretty-good measurement, per il quale non si conosce un’implementazione efficiente. Per le istanze Max-k-XORSAT estratte dal modello di configurazione, gli autori riscontrano che il suo successo è governato da un punto diverso, la soglia di condensazione.
Secondo gli autori, si tratta di un limite più stringente di quello precedentemente ricavato dal limite di Holevo. Resta aperta la questione se un decoder non locale efficiente possa funzionare tra la soglia locale e quella di condensazione e consentire alla DQI di superare i migliori valori classici.
Gli autori lasciano aperta anche la questione se la BPQM senza limiti di profondità su grafi finiti con cicli possa funzionare oltre la soglia locale. Le funzioni di ampiezza che non sono né simmetriche né della forma a blocchi esaminata nell’articolo esulano dai suoi risultati.
Fonti
Notizie correlate
- Uno studio sostiene di aver dimostrato un vantaggio nell’apprendimento per i circuiti quantistici a bassa profondità
- Un preprint testa un circuito guidato dal disordine su un modello a 49 qubit di IQM
- Stony Brook dimostra che gli algoritmi quantistici richiedono un numero esponenziale di interrogazioni per trovare un percorso negli alberi saldati
- Uno studio riporta rapporti Max-Cut simulati più elevati con QAOA su qubit cat
- Ricercatori del DLR riportano circuiti meno profondi per il caricamento di dati quantistici