A quantum lower bound for path finding in welded trees

Nel campo dell'informatica, esiste una differenza fondamentale tra sapere che un percorso esiste e l'essere effettivamente in grado di percorrerlo. I computer classici, che alimentano tutto, dagli smartphone ai supercomputer, risolvono i problemi controllando le possibilità una alla volta o seguendo un singolo percorso logico. I computer quantistici, al contrario, operano secondo i bizzarri principi della meccanica quantistica, consentendo loro di esplorare molteplici possibilità simultaneamente. Questa capacità, nota come sovrapposizione, ha già dimostrato di poter risolvere determinati problemi, come la fattorizzazione di grandi numeri o la simulazione di molecole, con una velocità che richiederebbe alle macchine classiche milioni di anni per essere eguagliata. Per decenni, i ricercatori hanno cercato nuovi tipi di problemi in cui questo vantaggio quantistico non fosse solo più veloce, ma fondamentalmente diverso nella sua natura. Volevano trovare un compito in cui un computer quantistico potesse vedere chiaramente la soluzione, pur essendo incapace di scrivere i passaggi per arrivarci.

Questa domanda ha condotto gli scienziati a un enigma specifico noto come il problema dell'albero saldato (welded tree problem). Immaginate due alberi alti e perfettamente simmetrici che crescono capovolti, con i rami che si protendono verso il suolo. In fondo, le foglie dell'albero di sinistra sono collegate alle foglie dell'albero di destra da una rete casuale e aggrovigliata di ponti. L'obiettivo è semplice: partire dalla cima dell'albero di sinistra e trovare la cima dell'albero di destra. Un computer classico, tentando di navigare in questo labirinto, dovrebbe controllare un numero esponenzialmente crescente di percorsi, finendo per arrendersi man mano che gli alberi diventano più alti. Un computer quantistico, invece, può inviare un'onda di probabilità attraverso l'intera struttura simultaneamente, trovando l'uscita in un tempo che cresce solo linearmente con l'altezza degli alberi. Questo era un risultato noto, un celebre esempio di velocità quantistica. Ma rimaneva un mistero persistente: sebbene l'onda quantistica potesse trovare l'uscita, sarebbe stata in grado di registrare anche il percorso specifico che aveva seguito? Se il computer avesse tentato di tenere un registro di ogni passaggio per ricostruire il percorso, la delicata onda quantistica sarebbe collassata, distruggendo il vantaggio di velocità e lasciando il computer non migliore di un computer classico. Per anni, è rimasto un interrogativo aperto se un algoritmo quantistico astuto potesse in qualche modo aggirare questo limite e trovare il percorso senza perdere il suo potere.

Un team di ricercatori dell'Università del Maryland ha ora risolto questa questione con una prova definitiva. Hanno dimostrato che è impossibile per qualsiasi algoritmo quantistico trovare efficientemente il percorso tra le due radici di questa struttura ad albero saldato. Il loro lavoro mostra che la difficoltà di trovare il percorso non è solo un ostacolo tecnico o un difetto dei design attuali, ma una legge fondamentale della meccanica quantistica per questo specifico problema. Per dimostrare ciò, i ricercatori hanno sviluppato un nuovo strumento matematico per tracciare esattamente quali informazioni un computer quantistico raccoglie mentre interroga il grafo. Hanno immaginato la memoria del computer come un database compresso che registra solo le connessioni essenziali scoperte, piuttosto che la storia completa e disordinata del suo viaggio. Analizzando come questo database cresce con ogni interrogazione, hanno dimostrato che il computer può rimanere in uno stato in cui sa che l'uscita è raggiungibile, ma la sequenza specifica di passi che collega l'inizio alla fine rimane nascosta.

I ricercatori hanno scoperto che, affinché un computer quantistico possa output con successo il percorso effettivo, dovrebbe effettuare un numero di interrogazioni che cresce esponenzialmente con la dimensione degli alberi. Questo è lo stesso sforzo esponenziale richiesto da un computer classico, il che significa che il vantaggio quantistico svanisce nel momento in cui l'algoritmo è costretto a rivelare il percorso. La prova si basa sulla dimostrazione che lo stato quantistico, anche dopo molte interrogazioni, rimane in una condizione "priva di percorso" con una probabilità schiacciante. Il computer può esistere in una sovrapposizione di molti diversi percorsi potenziali, ma questi percorsi non si fondono mai in un unico sentiero registrabile. Se l'algoritmo tenta di forzare l'esistenza del percorso, distrugge efficacemente i modelli di interferenza che rendono la ricerca quantistica veloce. Il risultato è una netta separazione: una macchina quantistica può risolvere il problema della navigazione esponenzialmente più velocemente di qualsiasi macchina classica, eppure è dimostrabilmente impossibile per quella stessa macchina dirvi come ci è riuscita.

Questa scoperta fornisce un esempio raro e concreto di un problema in cui un computer quantistico può esplorare un numero esponenzialmente grande di percorsi in sovrapposizione per trovare una soluzione, ma è fondamentalmente incapace di estrarne uno solo di tali percorsi. Suggerisce che il potere del calcolo quantistico non consiste solo nell'essere più veloci in tutto, ma nell'operare in un regime in cui il concetto di una singola, definitiva storia non si applica. I ricercatori hanno utilizzato una tecnica che coinvolge oracoli compressi, che agiscono come una memoria che memorizza solo le connessioni necessarie senza rivelare la struttura completa, per dimostrare che il progresso dell'algoritmo quantistico è strettamente limitato. Hanno dimostrato che l'informazione necessaria per ricostruire il percorso non si accumula abbastanza velocemente, indipendentmente da quante volte l'algoritmo interroga il grafo.

Le implicazioni di questo lavoro vanno oltre questo specifico enigma dell'albero. Mettono in discussione l'assunto che se un computer quantistico può trovare una soluzione, deve anche essere in grado di spiegarne il processo. In questo caso, la soluzione è trovata dal comportamento collettivo di molti percorsi, nessuno dei quali è individualmente reale finché non avviene la misurazione, e nel momento in cui la misurazione avviene, il vantaggio di velocità è svanito. Lo studio conferma che esistono compiti in cui il vantaggio quantistico è reale ed esponenziale, ma comporta un costo intrinseco: l'incapacità di tracciare i passaggi. Ciò non significa che i computer quantistici siano inutili per tali compiti; piuttosto, definisce il confine preciso della loro capacità. Possono navigare nel labirinto, ma non possono lasciare una mappa.

La prova dei ricercatori è rigorosa e non lascia spazio a dubbi all'interno del quadro matematico che hanno stabilito. Non si sono basati su simulazioni o suggerimenti; hanno fornito un limite inferiore formale, una garanzia matematica che nessun algoritmo, per quanto astuto, può avere successo con meno di un numero esponenziale di interrogazioni. Questo risolve un problema aperto da lungo tempo nel campo della complessità delle interrogazioni quantistiche. Evidenzia inoltre una profonda connessione tra la natura dell'informazione quantistica e la struttura dei problemi che può risolvere. Il problema dell'albero saldato, un tempo una curiosità, è diventato un esempio fondamentale di come la meccanica quantistica possa offrire una velocità che è allo stesso tempo miracolosa e misteriosa, permettendoci di vedere la destinazione mantenendo il viaggio per sempre fuori portata.