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

Este artículo demuestra que, si bien las caminatas cuánticas pueden atravesar árboles soldados exponencialmente más rápido que los algoritmos clásicos, cualquier algoritmo cuántico que intente registrar explícitamente el camino entre las raíces requiere exponencialmente más consultas ($\tilde{\Theta}(2^{n/3})$), estableciendo así una "dualidad onda-partícula algorítmica" donde la interferencia permite la navegación eficiente pero la reconstrucción del camino sigue siendo difícil.

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