The Complexity of Stoquastic Sparse Hamiltonians

Enunciato del Problema

Il documento affronta la complessità computazionale del problema Stoquastic Sparse Hamiltonian (StoqSH). Mentre la complessità degli Hamiltoniani stoquastici locali è ben compresa (noto come StoqMA-completo), la complessità degli Hamiltoniani stoquastici sparsi non era stata direttamente stabilita.

Gli Hamiltoniani sparsi costituiscono una classe più ampia rispetto agli Hamiltoniani locali; un Hamiltoniano $k$-locale con $m$ termini è $2^{km}$-sparsa. Il problema StoqSH chiede, dato un Hamiltoniano stoquastico $d$-sparsa $H$ (dove gli elementi fuori diagonale sono non positivi) e i parametri $\alpha, \beta$, se l'energia dello stato fondamentale $\lambda_{\min}(H) \le \alpha$ o $\lambda_{\min}(H) \ge \beta$, con la promessa che vale uno dei due casi.

La sfida centrale è che le tecniche standard per dimostrare l'appartenenza a StoqMA per gli Hamiltoniani locali (che si basano sulla conversione dei termini locali in proiezioni specifiche) non si estendono all'ambito sparso. Inoltre, i metodi standard di verifica quantistica come la Stima di Fase (utilizzati per gli Hamiltoniani sparsi generali in QMA) sono intrinsecamente quantistici e non possono essere simulati dai verificatori stoquastici ristretti, limitati a circuiti reversibili classici e misurazioni nella base di Hadamard.

Metodologia

Gli autori impiegano una procedura di verifica che colma il divario tra la struttura degli Hamiltoniani sparsi e i limiti dei verificatori stoquastici. La metodologia consta di tre componenti principali:

1. Decomposizione Sparsa:
   Gli autori utilizzano una decomposizione nota (da [BCC+14]) in cui qualsiasi Hamiltoniano $d$-sparsa $H$ può essere scritto come somma di $d^2$ termini 1-sparsi ($H = \sum H_j$). Crucialmente, se $H$ è stoquastico, ogni termine $H_j$ in questa decomposizione è anch'esso stoquastico, e gli elementi della matrice non nulli sono assegnati in modo univoco a termini specifici.

2. Verificatori StoqMA Generalizzati (gStoqMA):
   Per gestire la verifica, gli autori introducono una generalizzazione del verificatore StoqMA. I verificatori StoqMA standard misurano un singolo qubit nella base di Hadamard. Gli autori definiscono gStoqMA, dove il verificatore può misurare un numero polinomiale di qubit nelle basi di Hadamard, $|0\rangle$, o $|1\rangle$.

   • Dimostrano che questa generalizzazione non aumenta la potenza computazionale della classe; può essere simulata da un verificatore StoqMA standard con una perdita lineare nel gap di completezza/suono (Teorema 1.2). Ciò consente l'uso di misurazioni multi-qubit (specificamente test di Swap) all'interno del quadro stoquastico.

3. Procedura di Verifica per StoqSH:
   Il contributo centrale è un protocollo di verifica per StoqSH che accetta uno stato testimone $|\psi\rangle$ con una probabilità linearmente correlata all'aspettazione energetica $\langle \psi | H | \psi \rangle$. Il verificatore sceglie casualmente tra due sottoprocedure ($V_1$ e $V_2$):

   • Procedura $V_1$: Utilizza l'oracolo per gli elementi della matrice dell'Hamiltoniano per costruire uno stato dipendente da $|\psi\rangle$ e dal termine 1-sparsa $H_j$. Esegue un test "simile a Hadamard" che coinvolge una query controllata all'oracolo e misurazioni nelle basi $X$ e $Z$. La probabilità di accettazione è correlata agli elementi fuori diagonale e all'energia.
   • Procedura $V_2$: Una procedura complementare che misura l'ultimo qubit nella base $Z$.
   • Risultato Combinato: Mediante la media delle probabilità di accettazione di $V_1$ e $V_2$, la probabilità totale di accettazione diventa $1/2 - \frac{1}{4d^2}\langle \psi | H | \psi \rangle$. Questa relazione lineare permette al verificatore di distinguere tra istanze a bassa energia (SÌ) e ad alta energia (NO).

Contributi e Risultati Chiave

1. Completezza StoqMA di StoqSH
Il risultato principale è il Teorema 1.1, che afferma che il problema degli Hamiltoniani Stoquastici Sparsi è StoqMA-completo.

• Durezza: Deriva immediatamente dal fatto che gli Hamiltoniani stoquastici locali sono un caso particolare degli Hamiltoniani stoquastici sparsi e sono già noti come StoqMA-duri.
• Contenimento: Stabilito tramite la procedura di verifica descritta sopra, dimostrando che StoqSH $\in$ StoqMA.

2. Hamiltoniani Stoquastici Sparsi Separabili e StoqMA(2)
Gli autori estendono la loro analisi al problema Separable Stoquastic Sparse Hamiltonian (SepStoqSH), dove il testimone è vincolato a essere uno stato prodotto $|\psi\rangle = |\chi_A\rangle \otimes |\chi_B\rangle$.

• Definiscono StoqMA(k), l'analogo stoquastico di QMA(k), che coinvolge $k$ provatori non entangled.
• Teorema 1.4 (Semplificato): Mostrano che, per certi parametri di completezza e suono, $k$ provatori possono essere simulati da 2 provatori ($StoqMA(k) \subseteq StoqMA(2)$). La prova adatta il protocollo "Product Test" da [HM13] all'ambito stoquastico, sfruttando la capacità dei verificatori stoquastici di eseguire misurazioni multi-qubit (tramite la generalizzazione gStoqMA).
• Teorema 4.5: Il problema SepStoqSH è StoqMA(2)-completo. La prova di durezza adatta la costruzione da circuito a Hamiltoniano per Hamiltoniani sparsi separabili [CS12] all'ambito stoquastico, utilizzando la teoria delle perturbazioni per gestire la mancanza di amplificazione dell'errore in StoqMA(2).

3. Generalizzazione di StoqMA
Il documento introduce gStoqMA e dimostra che consentire misurazioni di dimensioni polinomiali non aumenta la potenza della classe oltre uno spostamento dei parametri (Teorema 3.5). Questa proprietà è evidenziata come potenzialmente di interesse indipendente per lo studio dei sistemi di prova stoquastici.

Significato e Affermazioni

Il documento afferma di avanzare la comprensione della classe di complessità StoqMA, che si colloca tra le classi randomizzate MA e AM ($NP \subseteq MA \subseteq StoqMA \subseteq AM$).

• Completezza: Identificando StoqSH come un problema completo per StoqMA, gli autori forniscono un problema naturale più generale per questa classe, andando oltre i modelli locali ristretti.
• Prove Separabili: Il lavoro colloca StoqMA(2) come un modello intermedio interessante tra la verifica stoquastica a singolo provatore e la verifica quantistica multi-provatore generale. Fornisce un problema completo naturale (SepStoqSH) per StoqMA(2), analogo al ruolo degli Hamiltoniani sparsi separabili per QMA(2).
• Robustezza: I risultati suggeriscono che la potenza dei verificatori stoquastici è robusta anche quando il testimone è vincolato a essere separabile, a condizione che l'Hamiltoniano sia sparso.

Gli autori notano che, sebbene dimostrino che StoqMA(k) collassa in StoqMA(2) per parametri specifici, la robustezza di questo collasso sotto vincoli di errore più stretti rimane una questione aperta. Inoltre, la complessità del problema degli Hamiltoniani Stoquastici Locali Separabili rimane aperta, poiché le tecniche attuali per la coerenza delle matrici di densità locali non si applicano direttamente all'ambito stoquastico.

In sintesi, il documento stabilisce la durezza computazionale degli Hamiltoniani stoquastici sparsi, introduce una nuova tecnica di verifica che utilizza misurazioni multi-qubit e caratterizza la potenza dei sistemi di prova stoquastici con più provatori non entangled.