Quantum Approximation Complexity of Classical Optimization Problems

Titolo: Complessità di Approssimazione Quantistica per Problemi di Ottimizzazione Classici
Autore: Stuart Hadfield

Enunciato del Problema

Il documento affronta la mancanza di garanzie rigorose sulle prestazioni nel caso peggiore per gli algoritmi di ottimizzazione quantistica. Sebbene molti metodi quantistici (ad esempio, QAOA, DQI) dimostrino punteggi elevati su istanze specifiche o forniscano limiti sui valori attesi (medie decodificate), essi spesso mancano di algoritmi uniformi che garantiscano un rapporto di approssimazione specifico per ogni input con errore limitato. Il lavoro cerca di definire formalmente gli analoghi quantistici delle classi di complessità di approssimazione classica (APX, PTAS, FPTAS) e di determinare se il calcolo quantistico possa migliorare strettamente gli algoritmi classici randomizzati in termini di qualità della soluzione garantita o del tempo richiesto per raggiungere una determinata accuratezza.

Metodologia

L'autore estende il framework dei problemi di Ottimizzazione NP (NPO) per includere algoritmi quantistici a errore limitato.

1. Definizione di Classi Quantistiche: Il documento definisce le classi BQ-APX, BQ-PTAS e BQ-FPTAS. L'appartenenza a queste classi richiede un algoritmo quantistico uniforme che, su ogni input, restituisca una soluzione classica ammissibile che raggiunga il rapporto di approssimazione dichiarato con una probabilità almeno di $2/3$. Fondamentalmente, il tempo di esecuzione include tutti i passaggi: selezione dei parametri, preparazione dello stato, misurazione, decodifica e ripetizione. Il punteggio della soluzione deve essere efficientemente computabile in modo classico.
2. Trasferimento dalla Media Decodificata all'Output: Uno strumento tecnico chiave è il Lemma 6 e il Corollario 7, che stabiliscono una relazione tra il punteggio atteso di una soluzione decodificata e una garanzia di output classico a errore limitato. Ciò consente la traduzione delle analisi basate sull'aspettativa (comuni nella letteratura quantistica) nelle rigide garanzie di output richieste per l'appartenenza alla classe.
3. Separazioni Condizionali: Il documento costruisce problemi specifici per dimostrare inclusioni strette tra classi quantistiche e classiche sotto ipotesi di complessità standard (ad esempio, $NP \not\subseteq BQP$ e $Factor \notin FBPP$). Queste costruzioni si basano sul "padding di ricerca" (search padding) e sulla durezza crittografica.

Contributi Chiave e Risultati

1. Gerarchia Formale di Classi di Approssimazione Quantistica
Il documento stabilisce una gerarchia stretta per le classi di approssimazione quantistica assumendo che $NP \not\subseteq BQP$:
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
Questa gerarchia è testimoniata da problemi classici:

• Max-E3SAT: Possiede un'approssimazione deterministica a rapporto costante (in APX) ma non un PTAS quantistico.
• Planar Vertex Cover: Possiede un PTAS deterministico ma non un FPTAS quantistico.
  Questi risultati mostrano che le classi quantistiche sono distinte tra loro, sebbene non separino ancora le classi quantistiche da quelle classiche randomizzate per questi specifici problemi.

2. Certified Maximum Order (CMO): Una Forte Separazione Quantistica–Classica
Il documento introduce il problema della Certified Maximum Order (CMO), dove l'obiettivo è trovare l'ordine moltiplicativo di un elemento modulo $N$ che sia certificato da una fattorizzazione primi dell'ordine.

• Risultato Quantistico: Un algoritmo quantistico a errore limitato può trovare l'ottimo esatto (la funzione di Carmichael $\lambda(N)$) in tempo polinomiale utilizzando la fattorizzazione e la ricerca del periodo. Pertanto, $CMO \in BQ\text{-}FPTAS$.
• Barriera Classica: Qualsiasi algoritmo polinomiale in tempo randomizzato che garantisca anche un rapporto di approssimazione di fattore polinomiale per CMO implicherebbe un algoritmo di fattorizzazione in tempo polinomiale randomizzato.
• Conclusione: Assumendo che $Factor \notin FBPP$, $CMo \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$. Ciò stabilisce una separazione condizionale in cui gli algoritmi quantistici forniscono soluzioni esatte mentre gli algoritmi classici randomizzati non possono nemmeno raggiungere approssimazioni a fattore polinomiale.

3. Discrete-Logarithm Fitting (DLog-Fit): Una Separazione di Soglia
Il documento definisce DLog-Fit, un problema che consiste nel predire le etichette su un campione basandosi sui logaritmi discreti.

• Base Classica: Un algoritmo deterministico ottiene un'approssimazione di $1/2$ (predicendo l'etichetta di maggioranza).
• Vantaggio Quantistico: Un algoritmo quantistico può trovare un fitting perfetto (ottimo esatto).
• Barriera Classica: Qualsiasi miglioramento fisso rispetto al rapporto $1/2$ da parte di un algoritmo classico randomizzato risolverebbe il problema del logaritmo discreto in un sottogruppo di numeri primi sicuri.
• Conclusione: Sotto l'assunzione che il logaritmo discreto in un sottogruppo di numeri primi sicuri non sia in $FBPP$, $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$. Ciò dimostra un divario alla soglia di approssimazione di $1/2$.

4. General Search Padding (Teorema 8)
Il documento fornisce una costruzione generica che mostra come qualsiasi problema di ricerca con testimoni facilmente verificabili possa essere trasformato in un problema NPO con una soglia di approssimazione di $1/2$. Se esiste un risolutore quantistico per la ricerca ma non un risolutore classico randomizzato, il problema di ottimizzazione risultante appartiene a $BQ\text{-}FPTAS$ ma è esterno a $R\text{-}PTAS$.

5. Analisi di Metodi Quantistici Esistenti
Il documento applica queste definizioni ad algoritmi esistenti:

• QAOA: Per il QAOA a profondità fissa su 3-regular MaxCut, il documento usa il trasferimento della media decodificata per mostrare che la ripetizione può produrre una garanzia di output a errore limitato (ad esempio, superando i $2/3$ dell'ottimo), collocando questa specifica famiglia di grafi in $BQ\text{-}APX$.
• Decoded Quantum Interferometry (DQI): Il documento nota che, sebbene il DQI mostri punteggi attesi migliorati su specifiche famiglie (come l'OPI ripiegato), stabilire una separazione nel modello di tempo a input esplicito richiede di dimostrare che gli algoritmi classici randomizzati non possano raggiungere lo stesso rapporto, il che rimane una sfida aperta per problemi non ristretti.

Significatività e Rivendicazioni

Il documento sostiene di fornire le prime definizioni rigorose per le classi di approssimazione quantistica a errore limitato e di dimostrare che, sotto esplicite ipotesi di complessità, il calcolo quantistico può migliorare strettamente le garanzie di approssimazione nel caso peggiore rispetto al calcolo classico randomizzato.

• Ambito Modesto: L'autore afferma esplicitamente che per problemi comuni e non ristretti come MaxCut o MaxSAT, un divario quantistico-classico nei rapporti di output nel caso peggiore rimane un problema aperto. Le separazioni stabilite si basano su specifiche costruzioni di problemi, spesso crittografiche (CMO, DLog-Fit), o su famiglie di grafi ristrette.
• Framework Teorico: Il lavoro colma il divario tra la performance euristica quantistica (spesso misurata tramite valori attesi) e la rigorosa teoria della complessità (garanzie di output a errore limitato). Chiarisce che alti punteggi nei benchmark da soli non stabiliscono l'appartenenza alla classe di approssimazione senza uniformità e limiti di tempo.
• Direzione Futura: Il documento identifica la ricerca di un algoritmo quantistico uniforme che garantisca un rapporto migliore della soglia di durezza classica per problemi standard (come l'unrestricted MaxCut) come il problema centrale nel campo.