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

Este artigo prova que, embora as caminhadas quânticas possam atravessar árvores soldadas exponencialmente mais rápido do que algoritmos clássicos, qualquer algoritmo quântico que tente registrar explicitamente o caminho entre as raízes requer um número exponencial de consultas ($\tilde{\Theta}(2^{n/3})$), estabelecendo assim uma "dualidade onda-partícula algorítmica" onde a interferência permite a navegação eficiente, mas a reconstrução do caminho permanece difícil.

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