Metraipolis › archive › dc_f749ec8b0174
Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard — arXiv:2611.05912
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05912
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:32:47.850Z
- SHA-256 of the archived text
55bb91a48614a782d6aa9ddf426ba05649d557c1bcbffde9945c5e47d14fe087- Stable URL of this page
https://metraipolis.com/documento/dc_f749ec8b0174
How to cite
Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard — arXiv:2611.05912 — arXiv (en), https://arxiv.org/abs/2611.05912 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f749ec8b0174 (Metraipolis archive dc_f749ec8b0174, sha256 55bb91a48614a782d6aa9ddf426ba05649d557c1bcbffde9945c5e47d14fe087)
BibTeX
@misc{dcf749ec8b0174,
title = {Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard — arXiv:2611.05912},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05912},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f749ec8b0174; sha256 55bb91a48614a782d6aa9ddf426ba05649d557c1bcbffde9945c5e47d14fe087},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05912. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the welded trees problem, an algorithm navigates a randomly labeled graph formed from two binary trees joined at their leaves through a "weld" of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, recording its path destroys the constructive interference responsible for the speedup, leaving open whether some quantum algorithm can efficiently find a path between the roots. We prove that, for trees of height $n$, the quantum query complexity of finding a path between the roots with constant probability is $\tilde{\Theta}(2^{n/3})$. This establishes an algorithmic wave-particle duality, adapting the double-slit experiment to the high-complexity regime: interference between many paths lets a quantum algorithm reach the exit efficiently, but finding a single path (the algorithmic analog of the route of a particle) requires exponentially many queries. Furthermore, the bound is tight, matching the cost of a quantum algorithm that finds collisions between paths from each root to the weld. Our proof uses the compressed permutation oracle to track the information about the graph that an algorithm retains and forgets. We show that the compressed database remains close to a space of states that do not record a path between the roots by bounding the error introduced by each compressed oracle query.
Tema degli esploratori: fisica e astronomia (elenco arXiv quant-ph, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2611.05912 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:22:49.016Z dalla pagina https://arxiv.org/list/quant-ph/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).