Exponential speedup of quantum algorithms for the pathfinding problem

2023/07/24 by Jianqiang Li, Li, Jianqiang · 2 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications

paper · pdf · doi:10.48550/arxiv.2307.12492

Abstract

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.

Cited by

• Quantum Grid Path Planning Using Parallel QAOA Circuits Based on Minimum Energy Principle
• A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems

Related

• Advances in quantum algorithms for the shortest path problem
• Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs
• Efficient quantum circuit implementation of quantum walks
• Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem