Exponential speedup of quantum algorithms for the pathfinding problem

• URL: http://arxiv.org/abs/2307.12492v2
• Date: Thu, 13 Jun 2024 14:33:05 GMT
• Title: Exponential speedup of quantum algorithms for the pathfinding problem
• Authors: Jianqiang Li,
• Abstract summary: Given $s, t$ in an unweighted undirected graph $G$, the goal of the pathfinding problem is to find an $s$-$t$ path. We construct a graph $G$ based on welded trees and define a pathfinding problem in the adjacency list oracle $O$. We prove that no classical algorithm can find an $s$-$t$ path in subexponential time with high probability.
• Score: 5.260626311429307
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given $s, t$ in an unweighted undirected graph $G$, the goal of the pathfinding problem is to find an $s$-$t$ path. In this work, we first construct a graph $G$ based on welded trees and define a pathfinding problem in the adjacency list oracle $O$. Then we provide an efficient quantum algorithm to find an $s$-$t$ path in the graph $G$. Finally, we prove that no classical algorithm can find an $s$-$t$ path in subexponential time with high probability. The pathfinding problem is one of the fundamental graph-related problems. Our findings suggest that quantum algorithms may potentially offer advantages in more types of graphs to solve the pathfinding problem and open up new possibilities for practical applications of quantum computations in various fields.

Related papers

Err

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.