Scholarlink

<p>Given <i>x</i>,&#xa0;<i>y</i> on an unweighted undirected graph <i>G</i>, the goal of the pathfinding problem is to find an <i>x</i>–<i>y</i> path. In this work, we first construct a graph <i>G</i> based on welded trees and define a pathfinding problem in the adjacency list oracle <i>O</i>. Then we provide an efficient quantum algorithm to find an <i>x</i>–<i>y</i> path in the graph <i>G</i>. Finally, we prove that no classical algorithm can find an <i>x</i>–<i>y</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Exponential speedup of quantum algorithms for the pathfinding problem

  • 期刊论文

  • 发表日期：

    2025年2月24日

查看全文
  • Jianqiang Li

摘要

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.