Learning Sparse Quantum States

Sintesi Tecnica: Apprendimento di Stati Quantistici Sparsi

Definizione del Problema
Il documento affronta il problema della tomografia dello stato quantistico per stati quantistici $k$-sparsi. Mentre gli algoritmi di apprendimento delle distribuzioni classiche scalano efficientemente con la dimensione del supporto $k$ per le distribuzioni $k$-sparse, gli algoritmi standard di tomografia dello stato quantistico scalano generalmente con la dimensione completa dello spazio di Hilbert ($2^n$) o con il rango della matrice di densità, indipendentemente dal fatto che lo stato possieda una struttura sparsa in un dato basis (specificamente nel basis computazionale). L'autore mira a colmare questo divario sviluppando algoritmi la cui complessità di campionamento e temporale scala quasi linearmente con la sparsità $k$ (e il rango $r$ per gli stati misti), piuttosto che con la dimensione esponenziale $2^n$.

Metodologia
Il documento presenta un approccio unificato per l'apprendimento di stati sparsi, progredendo dagli stati di fase agli stati puri generali e, infine, agli stati misti.

1. Apprendimento di Stati di Fase Sparsi:
   L'autore affronta prima gli stati di fase $k$-sparsi, definiti come $|\psi\rangle = \frac{1}{\sqrt{k}}\sum_{x \in S} e^{i\theta_x}|x\rangle$, dove $|S|=k$. L'algoritmo procede in due fasi:

   • Identificazione del Supporto: Il set di supporto $S$ viene appreso misurando lo stato nel basis computazionale circa $O(k \log k)$ volte, utilizzando un argomento del collezionista di coupon (coupon collector argument).
   • Recupero della Fase: Una volta noto il supporto, l'algoritmo apprende le fasi relative $\theta_x$. Ciò viene ottenuto costruendo un grafo dove i vertici sono gli stati del basis e gli archi rappresentano le fasi relative apprendibili. L'autore utilizza un insieme di funzioni lineari casuali (funzioni di hash) su $\mathbb{F}_2$ per mappare coppie di stati del basis sullo stesso output. La misurazione del registro di hash proietta lo stato su una sovrapposizione di due stati del basis, $|x_1\rangle + e^{i(\theta_{x_2}-\theta_{x_1})}|x_2\rangle$, permettendo di stimare la fase relativa tramite tomografia a singolo qubit.
   • Connettività del Grafo: Un contributo tecnico chiave è la dimostrazione che un piccolo numero ($O(\log k)$) di funzioni lineari casuali è sufficiente per generare un grafo con diametro $O(\log k)$. Ciò assicura che la fase di qualsiasi stato del basis possa essere determinata rispetto a uno stato di riferimento tramite un breve percorso di fasi relative apprese.

2. Apprendimento di Stati Puri Generali Sparsi:
   Per gli stati puri generali $k$-sparsi $|\psi\rangle = \sum_{x \in S} \sqrt{p_x}e^{i\theta_x}|x\rangle$, le probabilità $p_x$ non sono uniformi. L'autore adatta l'algoritmo degli stati di fase utilizzando una tecnica di accatastamento (bucketing technique) derivata dall'apprendimento delle distribuzioni classiche:

   • Pre-elaborazione: Un algoritmo di apprendimento delle distribuzioni classiche identifica il supporto e partiziona gli stati del basis in "bucket" (livelli di probabilità) dove le probabilità sono approssimativamente uniformi all'interno di ogni bucket.
   • Apprendimento della Fase per Bucket: La costruzione del grafo di fase viene applicata separatamente a ogni bucket. Fondamentalmente, un comune stato di riferimento (lo stato del basis con la probabilità più alta) è incluso in ogni bucket per garantire la coerenza della fase globale.
   • Allocazione dell'Errore: La complessità di campionamento è allocata proporzionalmente alla massa di probabilità di ciascun bucket. Gli stati a bassa probabilità vengono appresi con una precisione inferiore, in modo coerente con il loro contributo alla fedeltà complessiva, evitando il "collo di bottiglia della bassa probabilità" dove un singolo arco in un grafo di fase richiederebbe altrimenti un numero eccessivo di campioni.

3. Apprendimento di Stati Misti Sparsi:
   Per gli stati misti $k$-sparsi di rango $r$, l'autore impiega la tecnica del canale di purificazione casuale (random purification channel).

   • Riduzione: Utilizzano un canale quantistico che converte $m$ copie di uno stato misto $\rho$ in $m$ copie di una purificazione uniformemente casuale $|\rho\rangle$.
   • Preservazione della Sparsità: Viene dimostrato che se $\rho$ è $k$-sparso e ha rango $r$, la sua purificazione casuale è uno stato puro $kr$-sparso.
   • Algoritmo: L'algoritmo di tomografia dello stato puro viene quindi applicato a questi campioni purificati per ricostruire lo stato misto.

Risultati Chiave e Limiti di Complessità
Il documento stabilisce i seguenti limiti di complessità (omettendo i fattori polilogaritmici in $k, n, 1/\epsilon$):

• Stati Puri: Per uno stato puro $k$-sparso di $n$ qubit ignoto, l'algoritmo produce una stima $|\hat{\psi}\rangle$ con fedeltà $|\langle \psi | \hat{\psi} \rangle|^2 \geq 1 - \epsilon$ utilizzando:

  • Complessità di Campionamento: $\tilde{O}(k/\epsilon)$ copie.
  • Complessità Temporale: $\tilde{O}(kn/\epsilon)$.
    Questi limiti sono ottimali fino ai fattori polilogaritmici, migliorando esponenzialmente rispetto alla tomografia generale quando $k \ll 2^n$.

• Stati Misti: Per uno stato misto $k$-sparso di rango $r$ di $n$ qubit ignoto, l'algoritmo produce una stima $\hat{\rho}$ con fedeltà $F(\rho, \hat{\rho}) \geq 1 - \epsilon$ utilizzando:

  • Complessità di Campionamento: $\tilde{O}(kr/\epsilon)$ copie.
  • Complessità Temporale: $\text{poly}(m, n)$, dove $m$ è la complessità di campionamento.
    La complessità di campionamento è quasi ottimale. Tuttavia, la complessità temporale non è ancora ottimale per $r > 1$, poiché è attualmente dominata dall'implementazione del canale di purificazione casuale (che si basa sulla trasformata di Schur).

Significato e Rivendicazioni
L'autore afferma che questo lavoro fornisce il primo algoritmo quasi-ottimale per l'apprendimento di stati quantistici sparsi, ottenendo complessità di campionamento e temporale che scalano con la dimensione del supporto $k$ piuttosto che con la dimensione $2^n$.

• Ottimalità: L'algoritismo per gli stati puri è dimostrato essere sia ottimale per il campionamento che per il tempo (fino ai fattori log) nei parametri $n, k, 1/\epsilon$.
• Apprendimento in Tempo Polinomiale: I risultati implicano che per stati sparsi in un basis efficientemente computabile (dove $k = \text{poly}(n)$), l'apprendimento può essere eseguito in tempo polinomiale. Ciò estende l'ambito degli stati quantistici apprendibili efficientemente oltre gli stati stabilizer o gli stati a prodotto di matrici (MPS).
• Robustezza: Gli algoritmi sono robusti a piccole quantità di rumore e non richiedono strettamente il parametro esatto di sparsità $k$ come input; possono funzionare con un limite superiore o apprendendo il supporto dinamicamente.
• Domande Aperte: Il documento identifica come problema principale l'ottenimento di un algoritmo temporalmente ottimale per la tomografia degli stati misti che scali efficientemente con $k$ e $r$, specificamente migliorando l'implementazione del canale di purificazione casuale. Si nota inoltre che la rimozione dei fattori polilogaritmici nella complessità temporale degli stati puri rimane una sfida aperta.

Il lavoro non propone nuovi setup sperimentali o applicazioni specifiche oltre alle implicazioni teoriche per l'apprendimento di classi speciali di stati (ad esempio, stati GHZ, W, Dicke e stati di fase sparsi) e l'analisi di sicurezza degli stati quantistici pseudocasuali.