Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 56 min ago
PreprintCC BY 4.0arXiv

Hardness of Pathfinding in a Welded Tree

  • David Miloschewsky
  • Supartha Podder
Open at sourcePDFDOICite

Abstract

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 Ω(2n/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.

Related

  1. Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard
    Joseph Carolan, Andrew M. Childs, Matthew Coudron +3
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. A quantum lower bound for path finding in welded trees
    Joseph Carolan, Andrew M. Childs, Matthew Coudron +1
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. Identification of Local Elasto-Plastic Properties in Multi-Material Thin Aluminum Welded Structures through Experimental Methods, Modeling, and AI
    Arthur Thibault, Théo Dobrossy, Jean-François Witz +4
    Procedia Structural IntegrityPeer-reviewedCC BY-NC-NDGeneral physicsHAL
  4. Phase stability and mechanical response of Ag-interlayered Al/Cu resistance spot-welded joints
    Shuang Lin, Kyubok Lee, Jiahui Ye +6
    arXivPreprintCC BY 4.0Full textComputational physicsCondensed matterarXiv
  5. Average-case hardness of Betti number estimation
    Sergii Strelchuk, Sathyawageeswar Subramanian, Adam Wesołowski
    arXivPreprintCC BY-SA 4.0Full textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{miloschewsky2026hardness,
  title = {{Hardness of Pathfinding in a Welded Tree}},
  author = {David Miloschewsky and Supartha Podder},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.20651},
  eprint = {2609.20651},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.20651},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Hardness of Pathfinding in a Welded Tree
AU  - David Miloschewsky
AU  - Supartha Podder
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.20651
UR  - https://arxiv.org/abs/2609.20651
AB  - 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 Ω(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.
ER  -