Riassunto Tecnico: Il Problema dell'Hamiltoniano Locale Commutante: Evidenza Relativizzata Contro la BQP-Hardness

1. Definizione del Problema e Contesto

Il problema dell'Hamiltoniano Locale Commutante (CLH) chiede se l'energia dello stato fondamentale di un hamiltoniano locale, in cui tutti i termini locali commutano tra loro a coppie, sia al di sotto di una soglia $\alpha$ o al di sopra di una soglia $\beta$. Sebbene il problema generale dell'Hamiltoniano Locale sia QMA-completo, la complessità della variante commutante rimane una questione centrale nella teoria della complessità quantistica.

Lavori precedenti hanno dimostrato che per specifiche famiglie di hamiltoniani commutanti (ad esempio, 2-locali, determinati 3-locali, o quelli su specifici reticoli), il problema appartiene a NP. Tuttavia, non esisteva alcuna prova formale per escludere la possibilità che il problema CLH generale sia QMA-completo.

La classe di complessità QIMA (Quantum Interactive Merlin-Arthur con unità commutanti) è stata introdotta da Bostanci e Hwang per catturare la potenza di verificatori quantistici le cui unità di test locali sono riflessioni mutuamente commutanti. Il problema CLH è completo per QIMA. Di conseguenza, la questione se CLH sia QMA-completo è equivalente a chiedere se QIMA = QMA.

Questo articolo investiga la relazione tra QIMA e BQP (Bounded-error Quantum Polynomial time) in un contesto relativizzato. Nello specifico, cerca di determinare se esiste un oracolo classico $O$ tale che BQP$^O \not\subseteq$ QIMA$^O$. Un risultato positivo fornirebbe evidenza relativizzata contro la possibilità che il problema CLH generale sia BQP-hard e, quindi, contro la possibilità che sia QMA-completo.

2. Metodologia e Definizioni

2.1 Il Modello di Oracolo QIMA$^O$

Gli autori definiscono un analogo relativizzato di QIMA, denominato QIMA$^O$, con vincoli specifici per garantire che il modello rimanga una restrizione non banale di QMA$^O$:

• Struttura del Verificatore: Su un input $x$, il verificatore esegue un pre-processing classico (effettuando query adattive a $O$) per generare un insieme di "unità" $W_1^O, \dots, W_m^O$ che agiscono su un testimone (witness) quantistico.
• Commutatività: Nelle istanze promesse, tutte le unità devono commutare a coppie: $[W_i^O, W_j^O] = 0$.
• Requisito di Riflessione: Fondamentalmente, qualsiasi unità $W_j^O$ che contenga almeno una query all'oracolo deve essere una riflessione esatta (ovvero $(W_j^O)^\dagger = W_j^O$ e $(W_j^O)^2 = I$). Le unità prive di oracolo possono essere unitarie arbitrarie.
• Verifica: Il verificatore utilizza il test di Hadamard per controllare se il testimone si trova nello spazio eigensetale $+1$ di ciascuna unità.
• Assenza di Ancilla Fidata: Il verificatore non possiede alcuno spazio di lavoro fidato oltre ai qubit di controllo freschi utilizzati per i test di Hadamard.

Gli autori sostengono che il Requisito di Riflessione sia essenziale. Dimostrano che rilassare questo requisito per permettere unità commutanti arbitrarie (anche quelle vicine a riflessioni) o permettere qubit ancilla fidati, fa collassare la classe a QMA$^O$.

2.2 Il Problema della Forrelation

La separazione si basa sul problema della Forrelation, definito da Aaronson. Dato l'accesso all'oracolo a due funzioni booleane $f, g: \{0,1\}^n \to \{-1, +1\}$, il compito è distinguere tra:

• Sì: $f$ è altamente correlata con la trasformata di Fourier di $g$ ($\Phi(f,g) \ge \alpha$).
• No: La correlazione è piccola ($|\Phi(f,g)| \le \beta$).

La Forrelation è risolvibile da un algoritmo BQP con un numero costante di query quantistiche. L'articolo mira a dimostrare che qualsiasi verificatore QIMA$^O$ per la Forrelation richiede un numero esponenziale di query.

3. Contributi Chiave e Risultati

3.1 Separazione di Oracolo: BQP$^O \not\subseteq$ QIMA$^O$

Il risultato primario è la costruzione di un oracolo classico $O$ tale che BQP$^O \not\subseteq$ QIMA$^O$. Ciò viene ottenuto dimostrando un limite inferiore esponenziale delle query per il problema della Forrelation contro i verificatori QIMA$^O$.

Teorema 1.7 (Informale): Qualsiasi verificatore QIMA$^O$ che decida la Forrelation per tutte le coppie promesse $(f, g)$ deve soddisfare:
$$C(n) + T(n) \ge \beta 2^n - O(1)$$
dove $C(n)$ è il numero di query di pre-processing classico e $T(n)$ è il numero totale di query all'oracolo quantistico.

Schema di Dimostrazione:

1. Metodo Polinomiale: La probabilità di accettazione del verificatore è espressa come un polinomio nelle voci della tabella di verità dell'oracolo.
2. Commutatività e Riflessioni: Poiché le unità contenenti l'oracolo sono riflessioni esatte e commutano, il loro operatore di accettazione combinato è un prodotto di proiettori ortogonali. Ciò permette agli autori di definire un singolo proiettore $P_f$ che rappresenta l'intersezione di tutti gli spazi esaustali di accettazione.
3. Limite di Grado: Il grado del polinomio che rappresenta la probabilità di accettazione è limitato dal numero totale di query quantistiche $T(n)$.
4. Coppie di Forrelation Perfetta: Gli autori utilizzano "coppie di Forrelation perfetta" (funzioni bent) dove $\Phi(g, h) = 1$. Mostrano che perturbare $h$ con $k$ bit cambia il valore di Forrelation linearmente: $\Phi(g, f) = 1 - 2k/N$.
5. Simmetrizzazione: Fissando il transcript classico e mediando su funzioni con una distanza di Hamming fissata da una coppia perfetta, costruiscono un polinomio univariato $q(k)$.
6. Conteggio delle Radici: Il polinomio $q(k)$ deve essere zero per tutti gli istanze "No" (un ampio intervallo di $k$) e non nullo per l'istanza "Sì" ($k=0$). Un polinomio non nullo non può avere più radici del suo grado, forzando il grado (e quindi il conteggio delle query) a essere esponenziale.

3.2 Robustezza della Separazione

L'articolo dimostra che la separazione regge anche sotto lievi rilassamenti del modello:

• Deviazioni Trascurabili: Se le unità contenenti l'oracolo sono permesse di essere trascurabilmente vicine (in norma di operatore) a riflessioni esatte, la classe rimane QIMA$^O$, e il limite inferiore continua a valere.
• Supporto di Indirizzo Limitato: Gli autori estendono il limite inferiore a unità che non sono riflessioni ma effettuano una singola query, a condizione che i circuiti privi di oracolo che circondano la query agiscano in modo non banale solo su un piccolo numero di qubit di indirizzo ($k$). Se $n - k(n) = \omega(\log n)$, il limite inferiore delle query rimane superpolinomiale.

3.3 Comprensione della Precisione del Modello (Risultati di Collasso)

Per giustificare i vincoli specifici di QIMA$^O$, gli autori dimostrano che il rilassamento di tali vincoli fa collassare la classe a QMA$^O$:

• Deviazioni Inverso-Polinomiali: Se alle unità è permesso essere a una distanza inverso-polinomiale da una riflessione (anziché trascurabile), la classe collassa a QMA$^O$. Ciò è dimostrato usando una variazione del gadget di amplificazione di Marriott-Watrous, costruendo un'unica unità che simula un verificatore QMA.
• Singola Query senza Riflessione: Se il requisito di riflessione viene rimosso completamente ma le unità sono limitate a una singola query, la classe collassa comunque a QMA$^O$. Questo utilizza una costruzione a clock ciclico (simile a Feynman-Kitaev) per codificare una simulazione multi-query in una singola query.
• Ancilla Fidata: Permettere al verificatore un singolo qubit ancilla fidato (inizializzato a $|0\rangle$) collassa QIMA in QMA e QIMA$^O$ in QMA$^O$. Ciò si basa sul problema dell' "Hamiltoniano Locale Pinned Commuting", che è noto essere QMA-completo.

4. Significato e Rivendicazioni

L'articolo sostiene di fornire evidenza relativizzata contro la possibilità che il problema generale CLH sia BQP-hard. Poiché BQP è contenuto in QMA, se CLH fosse BQP-hard, ciò implicherebbe proprietà strutturali forti su QMA. La separazione $BQP^O \not\subseteq QIMA^O$ suggerisce che il vincolo di commutatività in QIMA (e per estensione in CLH) è una restrizione significativa che impedisce alla classe di catturare l'intero potere di BQP, anche in presenza di oracoli.

Inoltre, il lavoro chiarisce la precisione della definizione di QIMA. Gli autori sostengono che la specifica combinazione di commutatività, il requisito di riflessione per le query all'oracolo e l'assenza di ancilla fidate è necessaria per definire una classe che sia strettamente più debole di QMA. Rilassare anche solo una di queste condizioni recupera immediatamente il pieno potere di QMA, suggerendo che la "quanticità" di QIMA è fragile e dipende precisamente da questi vincoli strutturali.

I risultati non risolvono la questione non relativizzata se CLH sia QMA-completo, ma stabiliscono che qualsiasi prova di tale completezza richiederebbe tecniche non relativizzanti, poiché l'affermazione fallisce rispetto all'oracolo costruito.