2024/07/19 by Li, Jianqiang, Tong, Yu · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2407.14398
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 \citeCharles2009, 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.