Methods for Reducing Ancilla-Overhead in Block Encodings

I computer quantistici promettono di risolvere problemi che richiederebbero millenni alle macchine classiche, ma sono notoriamente fragili. Per eseguire calcoli complessi, queste macchine si affidano a una tecnica chiamata codifica a blocchi (block encoding), che consente loro di rappresentare operazioni matematiche che non sono perfettamente reversibili, una necessità per applicazioni del mondo reale come la simulazione di reazioni chimiche o la risoluzione di equazioni differenziali. Pensate alla codifica a blocchi come a un modo per nascondere un calcolo complesso e non reversibile all'interno di un processo quantistico più ampio e reversibile, utilizzando bit ausiliari aggiuntivi, noti come ancillae. Questi bit ausiliari fungono da spazio di lavoro temporaneo, permettendo al computer quantistico di manipolare i dati senza violare le leggi fondamentali della meccanica quantistica. Tuttavia, man mano che gli algoritmi diventano più complessi, richiedono sempre più di questi bit ausiliari. Poiché l'hardware quantistico è attualmente limitato per quanto riguarda il numero di qubit che può contenere, questa domanda di spazio extra crea un grave collo di bottiglia, costringendo spesso i ricercatori a scegliere tra l'esecuzione di un calcolo o l'esaurimento totale della memoria.

Un team di ricercatori dell'Università della California, Berkeley, e dell'Istituto di Matematica Alfréd Rényi d'Ungheria ha sviluppato due nuovi metodi per ridurre drasticamente il numero di questi bit ausiliari richiesti per le codifiche a blocchi. Il loro lavoro affronta il problema da due angolazioni diverse, offrendo un compromesso tra spazio e tempo nel primo caso, e tra spazio e accuratezza nel secondo. Il primo metodo introduce un modo per "pulire" lo spazio di lavoro una volta terminato un calcolo. In molti algoritmi quantistici, una volta utilizzata una codifica a blocchi, i bit ausiliari rimangono in uno stato disordinato ed entangled che non può essere riutilizzato. I ricercatori hanno ideato un protocollo che resetta coerentemente quasi tutti questi bit ausiliari a uno stato zero pulito, rendendoli disponibili per l'uso nelle parti successive dell'algoritmo. Questo processo non è istantaneo; richiede passaggi computazionali aggiuntivi, scambiando efficacemente tempo extra con la preziosa risorsa dello spazio extra. Il risultato è un sistema in grado di eseguire le stesse operazioni complesse utilizzando un solo bit ausiliario, indipendentemente da quanti ne fossero stati necessari originariamente, a condizione che il calcolo non sia perfettamente preciso ma sufficientemente vicino per usi pratici.

La seconda parte del loro lavoro affronta la sfida specifica di moltiplicare insieme molti codifiche a blocchi, un requisito comune nella simulazione di come i sistemi fisici evolvono nel tempo. Tradizionalmente, moltiplicare un gran numero di queste codifiche richiedeva un numero di bit ausiliari che cresceva logaritmicamente con il numero di operazioni, una richiesta che rapidamente supera l'hardware disponibile. I ricercatori hanno dimostrato che, per una moltiplicazione esatta e perfetta, questo requisito logaritmico è un limite invalicabile che non può essere aggirato. Tuttavia, hanno dimostrato che, se si è disposti ad accettare una piccola quantità di errore controllata, questo limite può essere superato. Hanno introdotto un nuovo "gadget" che esegue queste moltiplicazioni con un numero costante e piccolo di bit ausiliari, indipendentemente da quante operazioni vengano concatenate. L'errore introdotto da questa compressione è estremamente piccolo e diminuisce rapidamente all'aumentare leggermente del numero di bit ausiliari. Questo approccio è particolarmente efficace per le simulazioni in cui i singoli passaggi sono già molto vicini a non fare nulla, uno scenario comune nelle simulazioni fisiche in cui vengono utilizzati piccoli intervalli temporali per tracciare cambiamenti graduali.

Per garantire che questi calcoli compressi siano ancora utili, i ricercatori hanno anche dimostrato come utilizzare una tecnica chiamata amplificazione di ampiezza incerta (oblivious amplitude amplification). Questo metodo agisce come un filtro che aumenta la probabilità di successo del calcolo, trasformando efficacemento un processo che potrebbe fallire spesso in uno che ha successo quasi sempre, anche quando si utilizza il metodo compresso e approssimato. I risultati suggeriscono che, gestendo attentamente il compromesso tra precisione e uso delle risorse, gli algoritmi quantistici possono diventare molto più efficienti. Questa non è solo un esercizio teorico; i metodi sono direttamente applicabili alla simulazione della dinamica hamiltoniana, che descrive come l'energia si muove attraverso un sistema, e alla risoluzione di equazioni differenziali quantistiche, che sono essenziali per modellare tutto, dalla fluidodinamica alle reazioni chimiche. Riducendo l'overhead degli ancilla, queste tecniche potrebbero consentire ai computer quantistici attuali e di prossima generazione di affrontare problemi che prima erano fuori portata a causa della mancanza di memoria disponibile.