Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
<|reference_start|>Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs: Finding problems that allow for superpolynomial quantum speedup is one of the most important tasks in quantum computation. A key challenge is identifying problem structures that can only be exploited by quantum mechanics. In this paper, we find a class of graphs that allows for exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle, and this class of graphs is named regular sunflower graphs. We prove that, with high probability, a regular sunflower graph of degree at least $7$ is a mild expander graph, that is, the spectral gap of the graph Laplacian is at least inverse polylogarithmic in the graph size.   We provide an efficient quantum algorithm to find an $s$-$t$ path in the regular sunflower graph while any classical algorithm takes exponential time. This quantum advantage is achieved by efficiently preparing a $0$-eigenstate of the adjacency matrix of the regular sunflower graph as a quantum superposition state over the vertices, and this quantum state contains enough information to help us efficiently find an $s$-$t$ path in the regular sunflower graph.   Because the security of an isogeny-based cryptosystem depends on the hardness of finding an $s$-$t$ path in an expander graph \cite{Charles2009}, a quantum speedup of the pathfinding problem on an expander graph is of significance. Our result represents a step towards this goal as the first provable exponential speedup for pathfinding in a mild expander graph.<|reference_end|>
@article{li2024exponential,
    title={Exponential Quantum Advantage for Pathfinding in Regular Sunflower
  Graphs},
    author={Jianqiang Li, Yu Tong},
    journal={arXiv preprint arXiv:2407.14398},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.14398},
    primaryClass={quant-ph cs.DS}
}