Resource-Efficient Synthesis of Sparse Quantum States

Sintesi Tecnica: Sintesi Efficiente delle Risorse per Stati Quantistici Sparsi

Problema
La preparazione di stati quantistici è una sottoprocedura fondamentale per numerosi algoritmi quantistici, inclusi la simulazione dell'Hamiltoniana, i risolutori lineari e il machine learning. Tuttavia, preparare uno stato arbitrario di $n$ qubit richiede generalmente un circuito di dimensione $\Omega(2^n)$, rendendolo inefficiente dal punto di vista delle risorse per sistemi di grandi dimensioni. Sebbene molti applicazioni pratiche richiedano solo stati sparsi (vettori con poche voci non nulle), i metodi di sintesi esistenti spesso non riescono a ottimizzare metriche critiche per il calcolo quantistico tollerante ai guasti (FTQC). Nello specifico, nell'FTQC, i gate non-Clifford (come i gate T) sono significativamente più costosi da implementare rispetto ai gate Clifford. Gli attuali metodi per la sintesi di stati sparsi spesso presentano elevati conteggi di gate non-Clifford o una profondità di circuito eccessiva, e pochi approcci hanno esplicitamente minimizzato le risorse non-Clifford mantenendo una profondità lineare.

Metodologia
Gli autori propongono una nuova metodologia che decompone la sintesi di uno stato di $n$ qubit $s$-sparso in due compiti distinti e ottimizzati:

1. Generazione di uno Stato W Pesato: Il primo passo consiste nella preparazione di uno stato W generalizzato, $|W(\vec{\alpha})\rangle = \sum \alpha_i |e_i\rangle$, che codifica le ampiezze dello stato sparso. Il documento presenta due strategie di costruzione:

   • Costruzione basata su Albero (Tree-based): Un metodo esatto, privo di ancilla, basato su una definizione induttiva mediante una struttura ad albero binario. Questo approccio utilizza gate $RY(\theta)$ e raggiunge una dimensione $O(n)$ e una profondità $O(\log n)$. Gli autori analizzano le condizioni in cui queste rotazioni possono essere compilate nel set Clifford+T, osservando che gli stati W uniformi permettono riduzioni significative dei gate T.
   • Costruzione dello Stato Completo (Full-State): Un approccio alternativo che prepara uno stato completo su $\lceil \log_2 n \rceil$ qubit e mappa gli stati della base alla base dello stato W. Questo metodo sfrutta i recenti risultati ottimali per la preparazione dello stato completo (Gosset et al.) per ottenere un numero di gate T migliore nel regime fault-tolerant, sebbene con requisiti di ancilla più elevati.

2. Permutazione tramite Circuiti Reversibili Classici: Il secondo passo mappa gli stati della base $|e_i\rangle$ dello stato W agli specifici stati della base del vettore sparso. Ciò è modellato come un problema di permutazione su stringhe binarie.

   • Gli autori riducono questo problema alla diagonalizzazione di una matrice binaria $M_\chi$ utilizzando operazioni di riga elementari corrispondenti a gate reversibili classici (X, CX, CCX).
   • Introducono una nuova variante dell'eliminazione di Gauss-Jordan che utilizza passaggi di eliminazione paralleli per minimizzare la profondità del circuito.
   • Un'ottimizzazione chiave consiste nell'uso di circuiti Clifford adattivi (che coinvolgono misurazioni e gate controllati classicamente) per sostituire i costosi gate Toffoli (CCX) quando il qubit target è garantito essere $|0\rangle$ post-operazione. Ciò consente di implementare il circuito di permutazione con un conteggio T di $O(s)$ (o zero T con misurazioni) e una profondità di $O(s+n)$.

Contributi Chiave e Risultati

• Efficienza delle Risorse: L'algoritmo proposto sintetizza stati sparsi con un conteggio non-Clifford lineare rispetto alla sparsità $s$ ($O(s)$) e una profondità di circuito lineare sia nella sparsità che nel numero di qubit ($O(s+n)$). Questo migliora rispetto ai metodi allo stato dell'arte dove la profondità è spesso $O(sn)$ o i conteggi non-Clifford sono super-lineari.
• Compilazione Fault-Tolerant: Quando compilato al set di gate Clifford+T, gli autori forniscono tre costruzioni che offrono compromessi tra conteggio T, profondità e numero di ancilla.
  • La costruzione più ottimizzata per il conteggio T raggiunge un conteggio T di $O(\sqrt{s \log_2(1/\epsilon)} + \log_2(1/\epsilon))$. Gli autori osservano che questo eguaglia i limiti di ottimalità per la preparazione dello stato completo di Gosset et al., suggerendo che la costruzione sia probabilmente ottimale anche per gli stati sparsi.
• Ottimizzazione per Casi Speciali: Per gli stati sparsi "T-uniformi" (dove le voci non nulle appartengono all'insieme $\{e^{ik\pi/4}\}$), gli autori dimostrano una sintesi esatta utilizzando solo $O(\sqrt{s})$ gate T con una probabilità di successo $> 1/2$, utilizzando ancille "dirty".
• Tecnica di Diagonalizzazione di Matrici: Il documento contribuisce con un algoritmo specifico per la diagonalizzazione di matrici binarie utilizzando operazioni parallele CX e CCX, che funge da motore centrale per il circuito di permutazione.

Significatività
Il documento rivendica la propria importanza principalmente affrontando il collo di bottiglia delle risorse rappresentato dai gate non-Clifford nel calcolo quantistico tollerante ai guasti. Decoppiando la preparazione delle ampiezze (stato W) dalla permutazione della base, gli autori ottengono un metodo di sintesi in cui le risorse non-Clifford costose scalano linearmente con la sparsità piuttosto che con il numero totale di qubit. Anche la profondità del circuito è migliorata, essendo additiva in $s$ e $n$, un miglioramento sostanziale rispetto alle dipendenze moltiplicative dei lavori precedenti.

Gli autori notano con modestia che, sebbene il loro metodo sia altamente efficiente in termini di conteggio T e profondità, potrebbe richiedere un numero maggiore di qubit ancillari rispetto ad alcuni approcci esistenti (specificamente $\max(s, n) - n$). Identificano l'ottimizzazione delle strutture ad albero per massimizzare le operazioni "Clifford-friendly" come un problema classico NP-hard (relativo al problema della partizione) e suggeriscono che il lavoro futuro potrebbe esplorare l'adattamento della logica del circuito reversibile a specifici vincoli di connettività dell'hardware o la generalizzazione dell'approccio agli stati Dicke.