The Signal
Stony Brook dimostra che gli algoritmi quantistici richiedono un numero esponenziale di interrogazioni per trovare un percorso negli alberi saldati
Una dimostrazione di Stony Brook mostra che gli algoritmi quantistici richiedono almeno Ω(2^(n/24)) interrogazioni per trovare un percorso attraverso un albero saldato di altezza n, anche se una passeggiata quantistica può trovare l’uscita
Quantum.world Team · Scritto con l’IA · verificato ·
Per un albero saldato di altezza n, qualsiasi algoritmo quantistico richiede almeno Ω(2n/24) interrogazioni per produrre un percorso dall’ingresso all’uscita con probabilità costante, secondo una dimostrazione dei ricercatori della Stony Brook University. Il risultato riguarda le interrogazioni a un oracolo matematico per grafi, non il tempo di esecuzione di un computer quantistico fisico. Risolve una questione aperta da tempo su un problema in cui una passeggiata quantistica può individuare l’uscita esponenzialmente più in fretta degli algoritmi classici, mentre trovare e descrivere un percorso appare molto più difficile.
Un limite inferiore di 2n/24 interrogazioni
Il grafo è formato da due alberi binari collegati in corrispondenza delle foglie da archi alternati che formano una saldatura centrale. Le radici fungono da ingresso e da uscita. Un algoritmo parte dall’etichetta dell’ingresso e acquisisce informazioni sul grafo interrogando un oracolo per ottenere le etichette dei vertici vicini; ai vertici vengono assegnate etichette casuali, che quindi non rivelano da sole la loro posizione nel labirinto.
David Miloschewsky, dottorando in informatica a Stony Brook, e Supartha Podder, professore associato nel dipartimento, hanno pubblicato il loro preprint il 17 settembre 2026. Gli autori enunciano il risultato nell’abstract: «Rispondiamo dimostrando un limite inferiore esponenziale al numero di interrogazioni quantistiche necessarie per trovare un simile percorso».
Rispondiamo dimostrando un limite inferiore esponenziale al numero di interrogazioni quantistiche necessarie per trovare un simile percorso.
David Miloschewsky e Supartha Podder, autori di «Hardness of Pathfinding in a Welded Tree»
Il limite inferiore è esponenziale rispetto all’altezza dell’albero, ma il suo significato preciso dipende dal modello a oracolo e dalla distribuzione delle istanze del grafo adottati nell’articolo. Gli autori osservano che il loro modello e la loro distribuzione somigliano a quelli usati nei precedenti lavori sugli alberi saldati, ma non sono identici. Il teorema stabilisce un limite inferiore al numero di interrogazioni all’oracolo; non afferma che i computer quantistici non possano trovare l’uscita.
Trovare l’uscita non significa trovare il percorso
La distinzione è importante perché una passeggiata quantistica può sfruttare l’interferenza tra molti percorsi possibili per identificare l’uscita senza lasciare una traccia classica del tragitto. Una ricerca classica può registrare la sequenza dei bivi attraversati e ripercorrere quei passi dopo aver raggiunto la destinazione. Per un algoritmo quantistico, conservare informazioni sul percorso può interferire con il comportamento che rende efficace la passeggiata.
I risultati precedenti lasciavano aperta la possibilità che una diversa strategia quantistica evitasse questo compromesso: esplorare parti del grafo, cancellare dalla memoria alcune connessioni e ricostruire in seguito un percorso completo. Secondo quanto riferisce Stony Brook, Miloschewsky e Podder eliminano le restrizioni imposte in un’analisi del 2023. Il loro limite inferiore vale anche quando un algoritmo può dimenticare come una parte del grafo che ha esplorato sia collegata all’ingresso.
Un registro di ciò che l’algoritmo dimentica
La dimostrazione usa un oracolo a permutazione compressa, una tecnica per seguire le interazioni di un algoritmo con un grafo le cui etichette sono nascoste. I ricercatori rappresentano queste informazioni in un «registro quantistico» che tiene traccia di ciò che l’algoritmo ha appreso e di ciò che ha cancellato dalla memoria. La loro analisi mostra perché è improbabile che sezioni del grafo esplorate indipendentemente si colleghino attraverso la sua ampia regione centrale abbastanza in fretta da formare un percorso dall’ingresso all’uscita.
L’argomentazione va oltre la nota osservazione secondo cui registrare il percorso di una passeggiata quantistica può compromettere l’interferenza. Mira a escludere che qualsiasi algoritmo quantistico nel modello indicato possa trovare un percorso in modo efficiente, compresi gli approcci che non si limitano a registrare la passeggiata passo dopo passo. È questa affermazione più ampia a trasformare il limite di un singolo algoritmo in un limite inferiore al numero di interrogazioni per l’intera classe studiata.
Una seconda dimostrazione apre la questione dell’esponente
Un altro gruppo ha pubblicato una dimostrazione il 22 settembre, cinque giorni dopo il preprint di Stony Brook. Joseph Carolan, Andrew M. Childs, Matthew Coudron e Amin Shiraz Gilani riportano un limite inferiore di Ω(2n/12) interrogazioni per grafi di altezza n con alberi saldati mediante abbinamenti indipendenti. I due articoli stabiliscono limiti inferiori esponenziali nei rispettivi contesti; i loro esponenti non vanno confrontati direttamente senza tenere conto dei modelli e delle distribuzioni dei grafi.
Stony Brook riferisce che i due gruppi stanno ora lavorando insieme per determinare il limite ottimale. Questo obiettivo comune è la misura concreta ancora da stabilire dello sforzo, in termini di interrogazioni, richiesto per trovare un percorso in un albero saldato: il limite inferiore più forte valido per una formulazione comune del problema.