Electrostatic Limits on Quantum Spatial Search

Nel mondo del calcolo quantistico, i ricercatori cercano costantemente di risolvere un problema classico: trovare un singolo elemento specifico nascosto tra una vasta collezione di altri. Immaginate una biblioteca con milioni di libri, dove solo uno contiene un codice segreto. Un computer standard dovrebbe controllare i libri uno alla volta, un processo lento che richiede un tempo pari al numero di libri. I computer quantistici, tuttavia, utilizzano le strane regole della fisica per controllare molte possibilità contemporaneamente, offrendo un modo per trovare il codice segreto molto più velocemente. Questo incremento di velocità è noto come l'algoritmo di Grover, ed è considerato il punto di riferimento per la ricerca in dati non ordinati. Ma questa velocità ha un limite: l'algoritmo presuppone che il computer possa saltare istantaneamente a qualsiasi libro nella biblioteca, indipendentemente da dove stia guardando in quel momento. Nel mondo reale, i computer quantistici sono spesso costruiti su griglie fisiche, come una scacchiera fatta di atomi o fasci di luce, dove l'informazione può muoversi solo verso i vicini. Questa limitazione fisica trasforma la ricerca in un viaggio attraverso un paesaggio, sollevando una domanda difficile: il bisogno di viaggiare passo dopo passo attraverso una griglia bidimensionale costringe il computer a rallentare, o può ancora mantenere la sua leggendaria velocità?

Per oltre due decenni, questa domanda è rimasta uno dei misteri più persistenti nel campo. Mentre i computer quantistici potevano facilmente cercare in griglie tridimensionali con la stessa incredibile velocità della versione idealizzata, la griglia quadrata bidimensionale sembrava resistere. I migliori metodi conosciuti per la ricerca in una griglia piatta richiedevano un po' di tempo extra, un fattore che coinvolge il logaritmo del numero totale di elementi, il quale sembrava essere una penalità per vivere in un mondo piatto. Alcuni ricercatori speravano che un nuovo trucco astuto potesse rimuovere questa penalità, mentre altri sospettavano che la geometria della griglia piatta rendesse semplicemente impossibile essere veloci quanto le versioni tridimensionali o idealizzate. Un team di fisici ha ora risolto questo dibattito con una prova definitiva. Hanno dimostrato che, per quanto astuto sia l'algoritmo, o quanta memoria possieda il computer, la ricerca in una griglia bidimensionale richiede inevitabilmente quel tempo extra. Il limite di velocità non è un difetto della nostra tecnologia attuale o una mancanza di ingegno; è una legge fondamentale della fisica imposta dalla natura bidimensionale dello spazio stesso.

I ricercatori sono giunti a questa conclusione tracciando un collegamento sorprendente e potente tra la meccanica quantistica e l'elettrostatica classica, lo studio delle cariche elettriche e dei campi. Invece di tracciare le complesse onde di probabilità che si muovono attraverso il computer quantistico, hanno trattato il problema della ricerca come se fosse un circuito elettrico. Nel loro modello, l'elemento nascosto che stanno cercando agisce come una singola carica elettrica. Il computer quantistico è visto come una rete di fili, e il processo di ricerca è simile all'invio di una corrente attraverso questa rete per trovare quella carica. I ricercatori hanno scoperto che la difficoltà della ricerca è direttamente legata al "potenziale di auto-interazione" di quella carica, una misura di quanta energia sia necessaria per mantenere la carica in posizione all'interno della griglia. In un mondo piatto e bidimensionale, questa energia cresce lentamente ma costantemente man mano che la griglia si espande, specificamente in un modo che corrisponde alla crescita logaritmica del fattore di tempo extra visto negli algoritmi precedenti.

Trattando la ricerca quantistica come un problema elettrico, il team è stato in grado di dimostrare un limite inferiore rigoroso su quanto possa essere veloce la ricerca. Hanno dimostrato che l' "energia di campo" della rete limita la rapidità con cui il computer quantistico può cambiare il proprio stato per rilevare l'elemento contrassegnato. Poiché l'energia necessaria per creare un segnale rilevabile in una griglia bidimensionale cresce logaritmicamente con la dimensione della griglia, il computer deve compiere un numero corrispondente di passi per costruire quel segnale. Ciò significa che il fattore di tempo extra, che era stato fonte di confusione e di speranza di miglioramento, è in realtà un costo inevitabile della località in due dimensioni. La prova è valida anche se il computer ha memoria illimitata o se le query di ricerca sono gratuite, confermando che il collo di bottiglia è il movimento fisico dell'informazione attraverso la griglia, non l'efficienza della logica di ricerca.

Lo studio ha anche esplorato cosa accade quando ci sono più elementi nascosti invece di uno solo. In questo scenario, la singola carica elettrica è sostituita da un gruppo di cariche, che si comportano come un singolo conduttore. I ricercatori hanno scoperto che la disposizione di questi elementi conta significativamente. Se gli elementi sono sparsi in un modello regolare e ripetitivo, la ricerca è relativamente più facile. Tuttavia, se gli elementi sono raggruppati in un cluster compatto e stretto, la ricerca diventa molto più difficile. La difficoltà aumenta di un fattore correlato alla radice quadrata del numero di elementi, il che significa che trovare un gruppo di elementi nascosti che sono ammassati insieme è significativamente più impegnativo rispetto a trovare lo stesso numero di elementi distribuiti uniformemente sulla griglia. Questa distinzione rivela che la geometria dei dati nascosti determina la velocità della ricerca, aggiungendo un altro livello di complessità al problema.

Le scoperte confermano che l'algoritmo sviluppato da un ricercatore di nome Tulsi, che raggiunge la velocità della radice quadrata del numero di elementi moltiplicata per la radice quadrata di quel numero, è la migliore soluzione possibile per una griglia bidimensionale. Il lavoro del team dimostra che nessun algoritmo futuro potrà battere questa prestazione. Il fattore di tempo extra non è un bug da correggere, ma una caratteristica della geometria dell'universo. Questo risultato ha importanti implicazioni per la progettazione dei futuri computer quantistici, in particolare quelli costruiti su piattaforme bidimensionali come qubit superconduttori o chip fotonici. Dice agli ingegneri che non possono semplicemente aspettarsi di scalare i loro attuali progetti per raggiungere la velocità idealizzata dell'algoritmo di Grover senza tenere conto del costo intrinseco del movimento dell'informazione su una superficie piatta. Le leggi dell'elettrostatica, si scopre, hanno stabilito un limite di velocità invalicabile per la ricerca quantistica in un mondo piatto.