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

Diese Arbeit beweist, dass Quanten-Walks verschweißte Bäume zwar exponentiell schneller durchqueren können als klassische Algorithmen, jeder Quantenalgorithmus, der versucht, den Pfad zwischen den Wurzeln explizit aufzuzeichnen, jedoch eine exponentiell hohe Anzahl an Abfragen ($\tilde{\Theta}(2^{n/3})$) erfordert, wodurch eine „algorithmische Welle-Teilchen-Dualität“ etabliert wird, bei der Interferenz eine effiziente Navigation ermöglicht, die Pfadrekonstruktion jedoch schwierig bleibt.

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