Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard

Questo articolo dimostra che, sebbene le passeggiate quantistiche possano attraversare alberi saldati in modo esponenzialmente più veloce rispetto agli algoritmi classici, qualsiasi algoritmo quantistico che tenti di registrare esplicitamente il percorso tra le radici richiede un numero esponenziale di query ($\tilde{\Theta}(2^{n/3})$), stabilendo così una "dualità onda-particella algoritmica" in cui l'interferenza permette una navigazione efficiente ma la ricostruzione del percorso rimane difficile.

Autore originale: Joseph Carolan, Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani, David Miloschewsky, Supartha Podder