Random-Oracle Unitary Synthesis is Impossible

Nel mondo quantistico, le leggi fondamentali della fisica permettono una varietà quasi infinita di trasformazioni. Immaginate una macchina che possa prendere un pezzo di informazione e torcerlo in qualsiasi forma possibile, per quanto complessa o strana. Queste trasformazioni, note come unitarie, sono i mattoni fondamentali dell'informatica quantistica. Tuttavia, il fatto che la natura permetta una trasformazione non significa che un computer possa costruirla. Esiste un vasto divario tra le unitarie facili da costruire e quelle che sono effettivamente impossibili da creare con la tecnologia attuale. Per decenni, gli scienziati si sono chiesti se questo divario fosse reale o se fosse solo una lacuna nella nostra comprensione. Nello specifico, si sono chiesti se ogni difficile trasformazione quantistica potesse essere costruita semplicemente sapendo come calcolare una specifica, difficile funzione classica. Se la risposta fosse stata sì, avrebbe significato che i problemi più difficili dell'informatica quantistica sarebbero stati altrettanto difficili dei problemi più difficili dell'informatica classica, legando strettamente i due mondi. Se la risposta fosse stata no, avrebbe suggerito che la meccanica quantistica detiene segreti che la logica classica non può sbloccare, richiedendo potenzialmente una teoria della complessità completamente nuova.

Un team di ricercatori ha ora indagato su questa questione cambiando leggermente le regole del gioco. Invece di chiedere se un computer possa costruire una specifica trasformazione utilizzando una funzione specifica e complicata, hanno chiesto se un computer potesse costruire una trasformazione completamente casuale e imprevedibile usando solo una funzione casuale e priva di struttura. Questo cambiamento ha permesso loro di testare i limiti di ciò che è possibile quando i dati in ingresso non possiedono schemi nascosti da sfruttare. Le loro scoperte sono definitive: è impossibile sintetizzare efficientemente una trasformazione quantistica veramente casuale utilizzando solo una funzione casuale. Hanno dimostrato che, indipendentemente dalla genialità dell'algoritmo, se esso si basa su una funzione scelta casualmente, fallirà nel creare lo stato quantistico desiderato a meno che non ponga un numero astronomico di domande. Questo risultato risolve un dibattito di lunga data mostrando che la capacità di costruire stati quantistici complessi dipende interamente dalla struttura delle informazioni fornite. Senza tale struttura, il compito rimane fuori portata.

I ricercatori hanno anche esplorato un concetto correlato utilizzato nella crittografia quantistica, ovvero le unitarie pseudocasuali. Queste sono trasformazioni quantistiche che appaiono casuali a chiunque non conosca la chiave segreta utilizzata per crearle, nonostante siano state costruite attraverso un processo semplice ed efficiente. Per anni, i migliori metodi conosciuti per creare queste trasformazioni casuali "finte" sono stati limitati; potevano ingannare un osservatore che poneva un numero relativamente piccolo di domande. I ricercatori volevano sapere se questo limite fosse un ostacolo tecnico temporaneo o una legge fondamentale della natura. Hanno costruito un nuovo metodo che crea con successo queste trasformazioni in modo da rimanere sicuro anche contro un osservatore che pone un numero molto più grande di domande, specificamente fino a un numero proporzionale alla dimensione totale del sistema. Questo è un miglioramento significativo rispetto ai metodi precedenti, che potevano gestire solo un numero di domande proporzionale alla radice quadrata della dimensione del sistema.

Tuttavia, il loro lavoro ha anche rivelato un soffitto invalicabile. Sebbene siano riusciti a spingere la sicurezza di queste trasformazioni pseudocasuali molto più avanti rispetto al passato, hanno dimostrato che è impossibile spingerla fino al massimo teorico senza rendere il processo inefficiente. Hanno dimostrato che, se un metodo deve essere efficiente in termini di passaggi eseguiti, non può rimanere sicuro contro un osservatore che pone un numero molto elevato di domande. Ciò crea un confine preciso: si può avere un metodo che sia efficiente e sicuro contro un numero moderato di domande, oppure si può avere un metodo che sia sicuro contro un numero massiccio di domande, ma non si possono avere entrambi contemporaneamente. Questa scoperta suggerisce che le attuali limitazioni nella crittografia quantistica non sono solo una questione di attesa di algoritmi migliori; sono probabilmente un vincolo fondamentale dell'universo.

Lo studio ha anche affrontato la questione più ampia se sia mai possibile costruire una macchina universale capace di sintetizzare qualsiasi trasformazione quantistica fornendo le giuste istruzioni classiche. Dimostrando che gli input casuali non producono output casuali, i ricercatori hanno fornito una forte evidenza che la struttura dell'input è essenziale. Non basta avere un computer potente e una funzione casuale; la funzione stessa deve essere attentamente progettata per guidare il computer verso il risultato desiderato. Ciò implica che la difficoltà di creare certi stati quantistici non è solo una questione di potenza computazionale, ma è intrinseca alla natura delle informazioni necessarie per descriverli. Il lavoro chiude efficacementmente la porta all'idea che un semplice oracolo casuale possa servire come chiave universale per sbloccare tutte le possibilità quantistiche.

In definitiva, l'articolo dipinge un quadro di un panorama quantistico dove efficienza e casualità sono in tensione. I ricercatori hanno mostrato che, sebbene possiamo creare imitazioni molto convincenti della casualità, esiste un limite netto a quanto possano essere buone tali imitazioni se vogliamo che il processo rimanga veloce. Hanno anche dimostrato che la speranza di utilizzare una semplice funzione casuale per costruire qualsiasi trasformazione quantistica è infondata. I risultati non offrono solo un nuovo algoritmo o una nuova limitazione; essi ridefiniscono i confini di ciò che è possibile nel regno quantistico. Ci dicono che la complessità del mondo quantistico non è un'illusione che può essere aggirata con un trucco astuto, ma è una caratteristica reale che richiede informazioni specifiche e strutturate per essere navigata. Per coloro che costruiscono il futuro della tecnologia quantistica, ciò significa che la strada da seguire richiede non solo più potenza, ma una progettazione più precisa. L'universo, sembra, esige che sappiamo esattamente cosa stiamo chiedendo prima di darci la risposta.