Sintesi Tecnica: Sulla Difficoltà dell'Approssimazione della Membership di Circuiti Quantistici e dell'Ottimizzazione

1. Definizione del Problema

Il documento investiga la complessità computazionale di due problemi fondamentali nella teoria dei circuiti quantistici: Membership Approssimata e Ottimizzazione Approssimata.

• Membership Approssimata ($\text{ApproxMember}$): Dato un circuito quantistico $C$ su un insieme di porte $G$, un insieme di unitari $S$, una metrica di distanza $m$ e una tolleranza $\epsilon$, decidere se esiste un unitario $U \in S$ tale che la distanza $d_m(C, U) \le \epsilon$.
  • Un caso speciale è l'Identità Approssimata ($\text{ApproxId}$), dove $S = \{I\}$.
  • Il documento considera tre insiemi specifici per $S$:
    1. $S = \{I\}$ (Identità).
    2. $S \subseteq S_{\text{Cliff}}$ (Unitari implementabili da circuiti Clifford).
    3. $S \subseteq S_{\text{GP}}$ (Matrici di Permutazione Generalizzate, ovvero unitari che non creano sovrapposizione).
• Ottimizzazione Approssimata ($\text{ApproxOpt}$): Dato un circuito $C$, una funzione di costo $f$ e un budget $k$, decidere se esiste un circuito equivalente $C'$ tale che $d_m(C, C') \le \epsilon$ e $f(C') \le k$. La funzione di costo $f$ è caratterizzata dal suo "insieme libero" $S_f = \{U_{C'} \mid f(C') = 0\}$.

Lo studio si concentra su input senza promessa (promise-free), contrapponendosi al lavoro precedente (Janzing, Wocjan e Beth, 2005) che ha stabilito la QMA-completezza per il problema del "controllo di non-identità" sotto una promessa che il circuito sia vicino o lontano dall'identità. Questo lavoro rimuove tale promessa, chiedendosi se il problema rimanga difficile quando la distanza del circuito di input rispetto all'insieme target è sconosciuta.

Gli autori analizzano tre metriche standard per misurare la distanza tra unitari:

1. Metrica Sine: Basata sulla traccia, cattura le differenze nel caso medio ($d_{\text{Sine}}$).
2. Metrica Spettrale: Basata sulla norma dell'operatore, cattura le differenze nel caso peggiore ($d_{\text{sp}}$).
3. Metrica Operatore: La versione della metrica spettrale invariante rispetto alla fase globale ($d_{\text{op}}$).

2. Metodologia

Gli autori stabiliscono la durezza riducendo la classe di complessità PP (Tempo Polinomiale Probabilistico) al problema della membership approssimata. Il nucleo della loro metodologia prevede i seguenti passaggi:

1. Problema Sorgente: Utilizzano AtMostSat, un problema PP-hard che chiede se una formula proposizionale $\phi$ è soddisfatta da al massimo una frazione $\beta$ delle sue assegnazioni. Introducono una versione con promessa, PromiseAtMostSat, dove la frazione di assegnazioni soddisfacenti è promessa di essere al massimo $\kappa$.
2. Riduzione da Promessa ad Approssimazione: Dimostrano che PromiseApproxId (controllare se un circuito è $\epsilon$-vicino all'identità sotto la promessa che sia $\tau$-vicino) è PP-hard. Ciò viene ottenuto costruendo circuiti Clifford+T partendo da formule $\phi$ tali che la distanza $d_m(I, C)$ sia una funzione strettamente crescente $g(\gamma(\phi))$ della frazione di soddisfazione $\gamma(\phi)$.
   • Per la metrica Sine, costruiscono un circuito che implementa un'operazione controllata-XOR ($|x\rangle|b\rangle \mapsto |x\rangle|b \oplus \phi(x)\rangle$).
   • Per le metriche Spettrale e Operatore, utilizzano l'iterazione di Grover per costruire circuiti con angoli di autovalori dipendenti da $\gamma(\phi)$. Per la metrica operatore, impiegano prodotti tensoriali di questi circuiti per controllare la lunghezza d'arco degli angoli di autovalore sul cerchio unitario.
3. Rimozione della Promessa:
   • Caso $S = \{I\}$: La durezza della versione con promessa implica direttamente la durezza della versione senza promessa per gli specifici intervalli di $\epsilon$.
   • Caso $S \subseteq S_{\text{Cliff}}$: Utilizzano un argomento di disuguaglianza triangolare (Lemma 6). Dimostrano che per $\epsilon$ sufficientemente piccoli (specificamente $\epsilon < \sqrt{2}/4$), se un circuito è promesso essere vicino a $I$, gli unici elementi in $S_{\text{Cliff}}$ che possono essere $\epsilon$-vicini a $C$ sono quelli a distanza 0 da $I$ (ovvero, $I$ stesso). Ciò si basa sulla determinazione di un limite inferiore per la distanza minima non nulla tra $I$ e qualsiasi altro unitario Clifford.
   • Caso $S \subseteq S_{\text{GP}}$: Costruiscono circuiti specifici dove la distanza dall'insieme delle matrici di permutazione generalizzate è esattamente la distanza dall'identità per piccoli valori di $\gamma(\phi)$, permettendo una riduzione diretta dal problema con promessa. Questa riduzione si applica specificamente quando l'identità $I$ è inclusa nell'insieme $S$ (ovvero, $I \in S \subseteq S_{\text{GP}}$).

3. Contributi Principali e Risultati

Teorema Principale (Teorema 1)

Il documento dimostra che ApproxMember è PP-hard per un ampio intervallo di parametri, a condizione che l'insieme di porte $G$ possa implementare esattamente Clifford+T. La durezza è valida per:

• Insiemi $S$: $S=\{I\}$, $I \in S \subseteq S_{\text{Cliff}}$, e $I \in S \subseteq S_{\text{GP}}$.
• Metriche: Sine, Spettrale e Operatore.
• Tolleranza $\epsilon$:
  • Per $S=\{I\}$ e metriche basate sulla traccia (Sine): PP-hard per tutti i $0 < \epsilon < 1$ (il diametro completo).
  • Per $S=\{I\}$ e metriche Spettrale/Operatore: PP-hard per tutti i $0 < \epsilon < 2$.
  • Per $I \in S \subseteq S_{\text{Cliff}}$: PP-hard per $0 < \epsilon < \sqrt{2}/4 \approx 0.3536$.
  • Per $I \in S \subseteq S_{\text{GP}}$: PP-hard per $0 < \epsilon < 1$ (Sine) e $0 < \epsilon < \sqrt{2}$ (Spettrale/Operatore).

Corollario 1 (Durezza dell'Ottimizzazione)

I risultati implicano direttamente che ApproxOpt è PP-hard per la minimizzazione della profondità totale di porte/conteggio porte, della profondità di porte non-Clifford/conteggio porte, e della profondità di porte di sovrapposizione/conteggio porte, entro i corrispondenti intervalli di $\epsilon$.

Risultati Tecnici Specifici

1. Durezza per Porte Classiche-Reversibili: Anche quando l'insieme di porte $G$ consiste solo in porte classiche-reversibili (es. X, CNOT, Toffoli) che non possono creare sovrapposizione, il problema ApproxId sotto la metrica Sine rimane PP-hard per tutti i $0 < \epsilon < 1$.
2. Robustezza: I risultati di durezza si generalizzano a qualsiasi misura di distanza derivata dalle metriche Sine, Spettrale o Operatore tramite una funzione strettamente crescente. Inoltre, i problemi rimangono PP-hard anche se l'obiettivo è solo approssimare il costo minimo entro qualsiasi fattore (costante o meno), poiché la durezza sussiste quando il costo ottimale è 0.
3. Confronto con il Lavoro Precedente: Il documento rafforza il risultato di Janzing, Wocjan e Beth (2005). Mentre il loro risultato mostrava la QMA-completezza per il problema della promessa del controllo di non-identità, questo lavoro mostra che il problema senza promessa è PP-hard (una classe ritenuta strettamente più difficile di QMA) per un insieme più ampio di metriche e insiemi $S$.

4. Significato e Rivendicazioni

Gli autori affermano che i loro risultati dimostrano che l'ottimizzazione approssimata dei circuiti quantistici è fondamentalmente più difficile sugli input senza promessa rispetto alla QMA-completezza del controllo di non-identità basato su promessa.

• Indipendenza dalle Risorse: La durezza persiste indipendentemente dalle risorse quantistiche disponibili (qualsiasi porta, porte non-Clifford o sovrapposizione).
• Indipendenza dalla Metrica: La durezza è valida per varie metriche di distanza (basate sulla traccia, spettrali e operatore).
• Implicazioni Pratiche: Poiché gli standard hardware (come Clifford+T) soddisfano le condizioni, questi risultati di durezza si applicano direttamente ai compiti reali di compilazione e ottimizzazione quantistica. I risultati indicano che trovare un circuito approssimativamente equivalente con costo minimo (ad esempio, minimo conteggio T o profondità) è intrattabile per i computer classici, anche permettendo errori di approssimazione, a meno che la tolleranza dell'errore non sia trivialmente grande (superiore al diametro dello spazio metrico).

Il documento conclude notando i problemi aperti riguardanti la complessità per valori di $\epsilon$ più grandi (specificamente $\epsilon \ge \sqrt{2}/4$ per gli insiemi Clifford e $\epsilon \ge \sqrt{2}$ per gli insiemi di permutazione) e i limiti superiori corrispondenti, sebbene noti che per gli insiemi algebrici e la metrica Sine a $\epsilon = \sqrt{2}/2$, il problema è PP-completo.