⚛️ quantum physics

Evaluating QAOA expectation values can be as hard as counting optimal solutions

Questo articolo stabilisce che valutare i valori attesi esatti o esponenzialmente precisi del QAOA per il problema MaxCut a profondità $p \geq 2$ è #P-difficile, dimostrando che la difficoltà computazionale transita dalla trattabilità al conteggio delle soluzioni ottimali piuttosto che alla mera ottimizzazione.

Autori originali: Stuart Hadfield

Pubblicato 2026-08-13

📖 7 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Stuart Hadfield

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immaginate un mondo in cui i computer non si limitano a elaborare numeri, ma danzano con le probabilità. Questo è il regno del calcolo quantistico, un campo che promette di risolvere problemi così intricati e complessi che i supercomputer odierni impiegherebbero più tempo dell'età dell'universo per risolverli. Al cuore di questa danza c'è una celebre routine chiamata Quantum Approximate Optimization Algorithm, o QAOA. Pensate al QAOA come a una caccia al tesoro ad alta tecnologia. Avete una mappa (un problema) con molti percorsi possibili, e volete trovare l'unico percorso che conduce alla maggior quantità d'oro (la soluzione migliore). Il computer quantistico prepara uno stato speciale di "sovrapposizione" — un mix magico di tutti i percorsi possibili contemporaneamente — e poi, attraverso una serie di passaggi chiamati "layer" o "profondità", cerca di inclinare le probabilità in modo che il percorso migliore risplenda più intensamente quando finalmente lo guardate.

Per sapere se la caccia al tesoro sta procedendo bene, gli scienziati devono controllare il "valore di aspettativa". In parole povere, è come dare un'occhiata veloce alla danza del computer quantistico per vedere quanto sia vicino a trovare l'oro, senza effettivamente fermare la danza per contare ogni singola moneta. Per molto tempo, i ricercatori hanno saputo che se la danza aveva un solo passo (profondità $p=1$ ), controllare questo punteggio era facile, come leggere una ricetta semplice. Ma cosa succede quando la danza diventa più complicata, con due o più passi? Uno studio recente di Wang e colleghi ha dimostrato che controllare il punteggio per queste danze più profonde è incredibilmente difficile — così difficile da essere paragonabile alla risoluzione della caccia al tesoro originale stessa. Ma è solo altrettanto difficile trovare un buon percorso, o è anche più difficile?

Questo articolo, scritto da Stuart Hadfield, approfondisce proprio questa domanda. L'autore dimostra che per il QAOA con due o più layer, controllare il punteggio non è solo difficile come trovare una singola soluzione ottimale; è difficile quanto contare ogni singola soluzione ottimale esistente. Nel mondo dell'informatica, trovare una soluzione è una sfida dura, ma contarle tutte è un mostro di dimensioni diverse, spesso considerato ancora più impossibile da gestire per i computer classici. Hadfield mostra che questo "mostro del conteggio" appare non appena si aggiunge un secondo layer all'algoritmo. L'articolo non si limita a suggerirlo; fornisce una prova matematica rigorosa, costruendo un tipo specifico di grafo del problema che costringe qualsiasi computer che cerchi di calcolare il punteggio QAOA a risolvere essenzialmente il problema impossibile del conteggio. Ciò significa che per questi algoritmi quantistici più profondi, l'atto stesso di controllare quanto stiano andando bene è, nel caso peggiore, un compito che potrebbe essere fondamentalmente fuori dalla portata dei computer classici, anche se possediamo una macchina quantistica perfetta per eseguire la danza.

La Caccia al Tesoro si Complica

Analizziamo il trucco magico. L'algoritomo QAOA è progettato per risolvere il problema del "MaxCut". Immaginate un gruppo di amici a una festa, e volete dividerli in due squadre (Squadra Rossa e Squadra Blu) per giocare a un gioco. L'obiettivo è organizzare le squadre in modo che il maggior numero possibile di amicizie sia interrotto tra i due lati. Questo è il "MaxCut". Alcune disposizioni sono migliori di altre, e trovare la disposizione assoluta migliore è un classico enigma che diventa più difficile man mano che si aggiungono amici.

L'algoritmo QAOA cerca di trovare questa migliore disposizione facendo ruotare una moneta quantistica. Inizia con tutti in una sovrapposizione (sia Rossi che Blu contemporaneamente) e poi applica una serie di "torsioni" (i layer). Più torsioni aggiungete, più la danza diventa sofisticata. Per vedere se la danza funziona, gli scienziati calcolano un "valore di aspettativa". Pensate a questo come a un "punteggio" che vi dice, in media, quante amicizie sono state interrotte nella danza quantistica.

Per una singola torsione ( $p=1$ ), calcolare questo punteggio è facile. Potete scriverlo su un tovagliolo. Ma quando aggiungete una seconda torsione ( $p=2$ ), le cose si fanno strane. Ricerche precedenti hanno dimostrato che calcolare questo punteggio era "NP-hard", ovvero era difficile quanto trovare la singola migliore disposizione delle squadre. Ma l'articolo di Hadfield dice: "Aspetta, è in realtà peggio di così".

Il Mostro del Conteggio

La scoperta principale di Hadfield è un netto aggiornamento della nostra comprensza della difficoltà. Egli dimostra che calcolare il punteggio per $p \ge 2$ non è solo "NP-hard" (trovare una soluzione); è #P-hard.

Per capire la differenza, immaginate di essere un detective.

NP-hard è come se vi venisse chiesto: "Puoi trovare un sospettato che ha commesso il crimine?" È difficile, ma se siete fortunati o ci provate abbastanza duramente, potreste trovarne uno.
#P-hard è come se vi venisse chiesto: "Quanti sospettati in totale hanno commesso il crimine?" Dovete trovarli tutti e contarli.

Nel mondo dell'informatica, contare è generalmente considerato molto più difficile che trovare semplicemente uno. Hadfield mostra che per il QAOA con due o più layer, la matematica necessaria per calcolare il punteggio vi costringe a contare il numero di soluzioni perfette.

Il Gadget Magico

Come ha dimostrato questo? Hadfield ha costruito un "gadget" astuto, che è come una trappola progettata per catturare il computer. Ha preso un problema MaxCut standard e ha costruito un grafo gigante e complesso attorno ad esso. Questo grafo ha punti di "ancoraggio" speciali e blocchi "variabili".

Il trucco sta nel design. Quando il computer quantistico esegue la sua danza su questo grafo specifico, il punteggio finale (il valore di aspettativa) si trasforma in una gigantesca espressione matematica chiamata "polinomio di Laurent". Questa espressione è come una lunga stringa di termini, ciascuno con una diversa potenza di una variabile (come $z^1, z^2, z^3...$ ).

Hadfield ha dimostrato che la potenza più alta in questa stringa (il "coefficiente estremo") nasconde un segreto. Se potete calcolare il punteggio perfettamente, potete estrarre questa potenza massima. Ed ecco il colpo di scena: la dimensione di quel numero specifico è direttamente proporzionale al numero totale di soluzioni perfette al problema originale.

Quindi, se poteste calcolare facilmente il punteggio QAOA per questo grafo, sapreste istantaneamente la risposta al problema del "mostro del conteggio". Poiché si ritiene che il conteggio sia impossibile da gestire in modo efficiente per i computer classici, anche calcolare il punteggio QAOA deve essere impossibile per loro.

La Sorpresa del "Singolo Bordo"

L'articolo diventa ancora più sorprendente. Potreste pensare: "Ok, calcolare il punteggio totale è difficile, ma forse calcolare il punteo per un solo specifico legame (un singolo bordo) è facile?"

Hadfield dice di no. Dimostra che anche se chiedete al computer quantistico di dirvi solo la correlazione tra due persone specifiche (un "correlatore a due qubit" come $\langle Z_r Z_s \rangle$ ), il problema rimane #P-hard. La difficoltà non è solo nel quadro generale; è impressa nei minimi dettagli dell'algoritmo.

Cosa Significa per il Futuro

L'articolo traccia una linea netta nella sabbia:

Profondità $p=1$ : Facile. Possiamo calcolare il punteggio in modo efficiente.
Profondità $p \ge 2$ : Difficile. Calcolare il punteggio è difficile quanto contare tutte le soluzioni ottimali.

Ciò ha enormi implicazioni. Molti algoritmi moderni usano il QAOA per l'addestramento, regolando le "torsioni" (parametri) per ottenere un punteggio migliore. Se calcolare il punteggio è così difficile, allora l'addestramento di questi algoritmi su un computer classico (per vedere come sta procedendo la macchina quantistica) potrebbe essere impossibile per circuiti profondi.

L'autore nota anche che questo non significa che i computer quantistici siano inutili. In effetti, potrebbe significare che sono più utili. Se un computer classico non riesce nemmeno a controllare il punteggio, forse il computer quantistico è l'unico in grado di farlo. Tuttavia, l'articolo avverte anche che questa "difficoltà" è uno scenario del caso peggiore. Non significa che ogni grafo sia impossibile da risolvere; significa solo che esistono grafi specifici e ostici dove la matematica si interrompe per i computer classici.

In Sintesi

L'articolo di Stuart Hadfield è un campanello d'allarme per la comunità quantistica. Ci dice che, man mano che rendiamo il QAOA più potente aggiungendo più layer, non stiamo solo rendendo il problema più difficile da risolvere; stiamo rendendo il problema di controllare il nostro lavoro esponenzialmente più difficile. Siamo passati da un mondo in cui potevamo facilmente verificare la danza quantistica a un mondo in cui verificare la danza richiede la risoluzione di un puzzle di conteggio che potrebbe essere la cosa più difficile dell'informatica. È un promemoria del fatto che nel regno quantistico, più si va in profondità, più la matematica diventa misteriosa.

Sintesi Tecnica: La valutazione dei valori di aspettazione del QAOA è #P-hard

Definizione del Problema
Il documento affronta la complessità computazionale della valutazione dei valori di aspettazione per l'Algoritmo di Ottimizzazione Approssimata Quantistica (QAOA) applicato al problema del MaxCut. Sebbene la valutazione del valore di aspettazione del costo $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ sia nota per essere computabilmente efficiente per una profondità $p=1$ su grafi arbitrari, studi recenti hanno stabilito che la valutazione esatta diventa NP-hard per qualsiasi profondità fissa $p \ge 2$ . La questione centrale indagata qui è se la difficoltà per $p \ge 2$ sia limitata all'ottimizzazione (trovare una soluzione) o se si estenda al conteggio (determinare il numero di soluzioni ottimali). Nello specifico, l'autore si chiede se il calcolo di questi valori di aspettazione sia #P-hard, una classe di complessità generalmente ritenuta più difficile di NP, corrispondente alla difficoltà di contare il numero di soluzioni di un problema di soddisfacimento di vincoli.

Metodologia
L'autore perfeziona il meccanismo di prova della durezza introdotto da Wang et al. [5], che utilizzava polinomi di Laurent per recuperare il valore del taglio massimo dal più grande esponente. L'approccio dell'autore prevede i seguenti passaggi:

Costruzione del Grafo (Gadget di Conteggio Bilanciato): Invece dei gadget asimmetrici utilizzati nei lavori precedenti, l'autore costruisce un grafo specifico $G(H)$ a partire da un grafo di input $H$ . Questa costruzione impiega:
- Gadget di Variabili: Per ogni vertice in $H$ , viene creato un grafo bipartito completo bilanciato $K_{L,L}$ , dove $L = O(n)$ .
- Edge Sincroni: Edges che collegano i vertici corrispondenti nei gadget $K_{L,L}$ di vertici adiacenti in $H$ per preservare la struttura originale del grafo.
- Vertici Ancora: Due vertici universali, $r$ e $s$ , connessi a ogni vertice nei gadget delle variabili e tra di loro.
  Questa costruzione assicura che il grafo $G(H)$ abbia un diametro di 2 e che i suoi tagli massimi siano rigidamente vincolati: i gadget $K_{L,L}$ devono essere tagliati completamente, e gli ancori devono trovarsi su lati opposti.
Analisi del Polinomio di Laurent: Il valore di aspettazione del costo (o un correlatore specifico a due qubit $\langle Z_r Z_s \rangle$ ) è espresso come un polinomio di Laurent in una variabile di fase $z = e^{i\phi}$ . L'autore analizza i coefficienti di questo polinomio.
- Identifica un "coefficiente estremo" corrispondente all'esponente di grado massimo $D^*$ .
- Attraverso un'analisi di "somma di cammini ridotta", dimostra che il coefficiente $a_{D^*}$ è non nullo e direttamente proporzionale al numero di tagli massimi del grafo originale $H$ , denotato con $|\# \text{MC}(H)|$ .
- Nello specifico, $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ , dove $\kappa$ è un fattore algebrico noto e non nullo dipendente dagli angoli del mixer e dalla dimensione del grafo.
Riduzione tramite Interpolazione: L'autore dimostra che interrogando l'oracolo del valore di aspettazione QAOA in molti valori di fase distinti (radici dell'unità), è possibile utilizzare la trasformata discreta di Fourier inversa per recuperare esattamente i coefficienti di Laurent. Poiché il coefficiente estremo codifica il conteggio dei tagli massimi, un oracolo capace di valutazione esatta (o con precisione esponenziale) permette il recupero di tale conteggio, stabilendo così una riduzione di Turing deterministica in tempo polinomiale dal problema #P-hard del conteggio dei tagli massimi alla valutazione del valore di aspettazione del QAOA.

Contributi Chiave e Risultati

Dicotomia della Complessità: Il documento stabilisce una netta transizione di complessità per i valori di aspettazione QAOA su grafi semplici non pesati:
- $p=1$ : Il problema è in FP (computabile in tempo polinomiale).
- $p \ge 2$ : Il problema è #P-hard sotto riduzioni di Turing deterministiche in tempo polinomiale.
Conteggio vs. Ottimizzazione: A differenza del precedente risultato di NP-hardness che recuperava il valore del taglio massimo, questo lavoro mostra che la valutazione del valore di aspettazione permette di recuperare il numero di tagli massimi. Ciò eleva la durezza dall'ottimizzazione al conteggio.
Durezza Limitata: La #P-hardness sussiste anche sotto significative restrizioni:
- Si applica alla valutazione di un singolo correlatore a due qubit designato $\langle Z_r Z_s \rangle$ anziché alla funzione di costo globale.
- Si applica a un insieme altamente ristretto di parametri dell'algoritmo (angoli del mixer fissi $\beta_1 = \arctan(1/2)$ , $\beta_2 = \pi/4$ , e angoli di costo legati $\gamma_1 = \gamma_2 = \phi$ ).
- Si applica a grafi con diametro 2 (sebbene questi grafi abbiano un alto grado).
Derivate e Hessiane: L'autore estende questi risultati per mostrare che il calcolo esatto di gradienti e Hessiane della funzione di costo QAOA rispetto ai parametri è anch'esso #P-hard.
Precisione Esponenziale: La durezza si estende al problema dell'approssimazione del valore di aspettazione con errore additivo esponenzialmente piccolo ( $2^{-\alpha N}$ ), poiché tale precisione è sufficiente per distinguere il coefficiente estremo e recuperare il conteggio intero tramite arrotondamento.

Significato e Rivendicazioni
Il documento sostiene di fornire una "classificazione esatta e pulita della complessità" per i valori di aspettazione del QAOA. Il significato primario risiede nel dimostrare che la transizione da $p=1$ a $p=2$ non è solo uno spostamento dalla trattabilità alla durezza di ottimizzazione (NP-hard), ma uno spostamento verso la durezza di conteggio (#P-hard).

L'autore sottolinea che i loro risultati sono affermazioni sul caso peggiore riguardanti specifiche famiglie di grafi ad alto grado e non implicano che la valutazione del QAOA sia difficile per tutti i grafi o per istanze tipiche. Notano che la durezza dipende dalla valutazione esatta o con precisione esponenziale; non affermano la durezza per regimi di errore additivo costante o polinomialmente piccolo, che sono più rilevanti per gli attuali dispositivi quantistici NISQ (Noisy Intermediate-Scale Quantum).

Inoltre, il documento distingue le proprie scoperte dai risultati di supremazia quantistica relativi al campionamento. Mentre il campionamento dagli output del QAOA a $p=1$ è già classicamente difficile in certe condizioni, questo lavoro mostra che valutare il valore di aspettazione a $p=2$ è sufficiente per risolvere problemi di conteggio #P-hard. L'autore conclude che i loro risultati implicano che, se si potesse valutare efficientemente i valori di aspettazione del QAOA con precisione esponenziale, la gerarchia polinomiale collasserebbe al suo livello più basso ($P=PH$). Ciò ha implicazioni per gli algoritaggi ibridi che si affidano all'elaborazione classica dei valori di aspettazione quantistici, suggerendo che tali approcci potrebbero incontrare barriere computazionali fondamentali nel caso peggiore se è richiesta un'alta precisione.