Metraipolis › archive › dc_1bcfe12f8d16
Hardness of Pathfinding in a Welded Tree — arXiv:2609.20651
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.20651
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T05:45:27.993Z
- SHA-256 of the archived text
4567b16b85d0818cc99f6354be96db57f0d7fd5a245daee168e795983709da13- Stable URL of this page
https://metraipolis.com/documento/dc_1bcfe12f8d16
How to cite
Hardness of Pathfinding in a Welded Tree — arXiv:2609.20651 — arXiv (en), https://arxiv.org/abs/2609.20651 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1bcfe12f8d16 (Metraipolis archive dc_1bcfe12f8d16, sha256 4567b16b85d0818cc99f6354be96db57f0d7fd5a245daee168e795983709da13)
BibTeX
@misc{dc1bcfe12f8d16,
title = {Hardness of Pathfinding in a Welded Tree — arXiv:2609.20651},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.20651},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1bcfe12f8d16; sha256 4567b16b85d0818cc99f6354be96db57f0d7fd5a245daee168e795983709da13},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20651. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $\Omega(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.20651 — 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-10-10T05:12:38.410Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).