Exponential speedup of quantum algorithms for the pathfinding problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916539216691200 |
|---|---|
| author | Li, Jianqiang |
| author_facet | Li, Jianqiang |
| contents | Given $x, y$ on an unweighted undirected graph $G$, the goal of the pathfinding problem is to find an $x$-$y$ 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 $x$-$y$ path in the graph $G$. Finally, we prove that no classical algorithm can find an $x$-$y$ path in subexponential time with high probability. The pathfinding problem is one of the fundamental graph-related problems. Our findings suggest that quantum algorithms could potentially offer advantages in more types of graphs to solve the pathfinding problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_12492 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Exponential speedup of quantum algorithms for the pathfinding problem Li, Jianqiang Quantum Physics Given $x, y$ on an unweighted undirected graph $G$, the goal of the pathfinding problem is to find an $x$-$y$ 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 $x$-$y$ path in the graph $G$. Finally, we prove that no classical algorithm can find an $x$-$y$ path in subexponential time with high probability. The pathfinding problem is one of the fundamental graph-related problems. Our findings suggest that quantum algorithms could potentially offer advantages in more types of graphs to solve the pathfinding problem. |
| title | Exponential speedup of quantum algorithms for the pathfinding problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2307.12492 |