Sparse quantum state preparation with improved Toffoli cost

Sintesi Tecnica: Preparazione di Stati Quantistici Sparsi con Costo Toffoli Migliorato

Enunciato del Problema
La preparazione di stati quantistici è un primitivo fondamentale nel calcolo quantistico, essenziale per applicazioni che spaziano dai risolutori di sistemi lineari al machine learning quantistico e alla simulazione quantistica. Mentre la preparazione di stati generici è stata ampiamente studiata, gli stati quantistici sparsi — stati su $n$ qubit contenenti solo $s \ll 2^n$ stati della base computazionale non nulli — richiedono algoritmi specializzati ed efficienti.

Nel calcolo quantistico fault-tolerant, la metrica principale delle risorse è spesso il numero di gate Toffoli (e gate T), poiché queste operazioni non-Clifford sono significativamente più costose da implementare rispetto ai gate Clifford a causa dell'overhead della distillazione degli stati magici. Gli approcci esistenti per la preparazione di stati sparsi rientrano generalmente in due categorie:

1. Costruzione iterativa: Costruire lo stato in $s$ passi, ognuno dei quali prepara un singolo stato della base. Ciò comporta tipicamente un costo Toffoli superiore a $s \lceil \log(s) \rceil$.
2. Approccio in due fasi (Preparazione Densa + Isometria): Preparare prima uno stato denso su un sottoregistro di $\lceil \log(s) \rceil$ qubit, quindi mappare tale stato verso lo stato sparso target tramite un'isometria. La preparazione densa è ben ottimizzata (ad esempio, tramite algoritmi di Grover-Rudolph), ma il passaggio di isometria è storicamente stato il collo di bottiglia. L'arte precedente, come il metodo di Malvetti et al., richiede un costo Toffoli nel caso peggiore di $s(\lceil \log(s) \rceil - 1)$ per l'isometria, il che domina il costo totale dell'algoritmo.

Metodologia
Gli autori propongono un framework raffinato in due fasi (illustrato nella Figura 1) che ottimizza il passaggio di isometria e lo integra con la preparazione dello stato denso:

1. Costruzione dell'Isometria a Batch (Lotti):
   L'innovazione principale è un nuovo algoritmo classico per la costruzione del circuito isometrico. Invece di applicare singoli gate multi-controllati-X per azzerare i qubit non appartenenti al sottospazio per ciascuno dei $s$ stati (come fatto da Malvetti et al.), l'algoritmo raggruppa gli stati in batch di dimensione $m$, dove $m$ è la massima potenza di due che rientra nel registro non appartenente al sottospazio disponibile ($m \le n - \lceil \log(s) \rceil$).

   • Per ogni batch, l'algoritmo trasforma gli stati in una forma in cui il registro non appartenente al sottospazio contiene un singolo $|1\rangle$ in posizioni distinte (ad esempio, $|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$).
   • Un circuito di Iterazione Unaria Parziale (PUI) viene quindi applicato per azzerare simultaneamente i registri non appartenenti al sottospazio per l'intero batch.

2. Circuiti di Iterazione Unaria Parziale (PUI):
   Gli autori introducono due varianti di circuiti PUI, che iterano su un intervallo specifico $[l, r]$ di un registro di indirizzi piuttosto che sull'intero spazio:

   • PUI Restritta: Garantisce che le unitarie siano applicate solo agli stati all'interno dell'intervallo target $[l, r]$.
   • PUI Non Restritta: Permette al circuito di applicare unitarie non triviali agli stati con valori di indirizzo superiori a $r$. Questo rilassamento riduce significativamente il conteggio dei Toffoli. Gli effetti "indesiderati" sui valori di indirizzo superiori sono tracciati classicamente e corretti in passaggi o batch successivi.

3. Ottimizzazione Congiunta con la Preparazione dello Stato Denso:
   Gli autori analizzano il compromesso tra il costo dell'isometria e il costo della preparazione dello stato denso. Propongono di "esternalizzare" alcuni sottotask dalla preparazione densa al circuito di isometria:

   • Correzioni di Segno: Invece di uncompute il registro degli angoli dopo la preparazione densa (il che richiede Toffoli aggiuntivi per la correzione del segno), l'informazione sul segno viene codificata direttamente nell'isometria usando PUI ristrette.
   • Stati Reali: Per stati target con coefficienti puramente reali, il passaggio di codifica della fase della preparazione densa viene interamente rimosso e gestito all'interno dell'isometria, riducendo potenzialmente il costo Toffoli della preparazione densa fino a un fattore di tre.

Contributi Chiave

• Algoritmo di Isometria Migliorato: Un nuovo algoritmo classico (Algoritmo 1) che costruisce circuiti isometrici con un costo Toffoli nel caso peggiore limitato da:
  $$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$$
  dove $\tilde{s} = 2^{\lceil \log(s) \rceil}$. Ciò rappresenta un miglioramento di circa $\log(s)/2$ rispetto al metodo allo stato dell'arte di Malvetti et al.
• Varianti PUI: La definizione e l'analisi del costo dei circuiti di iterazione unaria parziale ristretti e non ristretti. La versione non ristretta ottiene conteggi Toffoli inferiori permettendo la "dispersione" (leakage) delle operazioni a valori di indirizzo superiori, il che è gestibile nel contesto della costruzione dell'isometria a batch.
• Analisi del Compromesso delle Risorse: Un'analisi completa (Tabella 1) dei costi combinati di Toffoli e qubit per la preparazione di stati sparsi, dimostrando come l'ottimizzazione dell'isometria permetta una migliore utilizzazione dei qubit ancilla per ridurre il costo della preparazione densa, particolarmente per stati a valori reali.
• Implementazione: I circuiti sono implementati nel framework Qualtran, con l'algoritmo classico di ricerca dell'isometria ottimizzato tramite codice Rust con accelerazione SIMD.

Risultati

• Limiti Teorici: Il costo Toffoli nel caso peggiore per l'isometria è ridotto da $O(s \log s)$ a circa $O(s)$ per $n$ sufficientemente grandi. Nello specifico, il costo si avvicina a $s$ nei benchmark numerici su stati casuali, rispetto al precedente migliore di circa $s \log s$.
• Benchmark Numerici:
  • Per stati $s$-sparsi casuali, il numero di Toffoli per $s$ si avvicina a 1 all'aumentare di $n$ (Figura 2, destra).
  • Per stati puramente reali, l'ottimizzazione congiunta riduce significativamente il conteggio totale dei Toffoli rispetto agli stati complessi generici (Figura 9).
  • L'algoritmo classico gira efficientemente, trovando isometrie per $s=10^7$ stati in circa 10–20 minuti su hardware CPU standard.
• Confronto: Il metodo proposto supera la letteratura esistente (ad esempio, [4, 14, 20, 21]) in termini di conteggio Toffoli mantenendo un overhead di qubit comparabile o inferiore.

Significatività e Rivendicazioni
Il documento rivendica di presentare i circuiti di preparazione di stati sparsi più efficienti in letteratura in termini di conteggi Toffoli e qubit. La significatività risiede in:

1. Rimozione del Collo di Bottiglia: Riducendo il costo dell'isometria da fattore dominante a un livello paragonabile alla preparazione densa, l'algoritmo complessivo diventa più efficiente.
2. Scalabilità: L'approccio scala favorevolmente con il numero di qubit $n$, rendendolo adatto ad algoritmi quantistici fault-tolerant su larga scala dove $s$ è grande ma $s \ll 2^n$.
3. Praticità: Il metodo è compatibile con gli attuali framework di stima delle risorse fault-tolerant (focalizzati sui conteggi Toffoli) ed è implementato in un framework software modulare (Qualtran).

Gli autori rimangono modesti riguardo alle implicazioni future, osservando che, sebbene il conteggio Toffoli sia la metrica standard attuale, i progressi nella generazione di stati magici (coltivazione/distillazione) potrebbero spostare l'attenzione verso le metriche di tempo di esecuzione in futuro. Essi lasciano inoltre aperta la questione se sia possibile raggiungere costi Toffoli sub-lineari in $s$ con risorse ancilla limitate.