Related papers: Exponential speedup of quantum algorithms for the pathfinding problem

Exponential speedup of quantum algorithms for the pathfinding problem

URL: http://arxiv.org/abs/2307.12492v3
Date: Mon, 23 Dec 2024 18:05:32 GMT
Title: Exponential speedup of quantum algorithms for the pathfinding problem
Authors: Jianqiang Li,
Abstract summary: 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 $x$-$y$ path in subexponential time with high probability. Our findings suggest that quantum algorithms could potentially offer advantages in more types of graphs to solve the pathfinding problem.
Score: 5.260626311429307
License:
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.

Related papers

Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
We give two bounded-error quantum algorithms in the adjacency list model that solve the problem on structured instances. The first approach is based on sparsifying the original graph via sampling the quantum flow state and running a classical algorithm on the smaller problem. The second approach is based on a divide and conquer procedure that outputs the shortest path in $tildeO(lsqrtm)$ steps.
arXiv Detail & Related papers (2024-08-19T21:30:02Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z)
Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem [2.107421958337625]
We consider an inverse problem for a finite graph $(X,E)$ where we are given a subset of vertices. We show that this problem has unique solution under certain conditions and develop quantum computing methods to solve it.
arXiv Detail & Related papers (2023-06-08T14:48:48Z)
Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
We prove that the minimax regret is proportional to $R*$ for any graph and time horizon $T$. Introducing an intricate exploration strategy, we define the mainAlgorithm algorithm that achieves the minimax optimal regret bound.
arXiv Detail & Related papers (2023-06-05T15:35:00Z)
On the Unlikelihood of D-Separation [69.62839677485087]
We provide analytic evidence that on large graphs, d-separation is a rare phenomenon, even when guaranteed to exist. For the PC Algorithm, while it is known that its worst-case guarantees fail on non-sparse graphs, we show that the same is true for the average case. For UniformSGS, while it is known that the running time is exponential for existing edges, we show that in the average case, that is the expected running time for most non-existing edges as well.
arXiv Detail & Related papers (2023-03-10T00:11:18Z)
Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications [0.0]
We present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs) We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps.
arXiv Detail & Related papers (2022-12-29T19:07:39Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z)
Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
arXiv Detail & Related papers (2022-07-04T19:33:06Z)
Quantum Algorithm for the Longest Trail Problem [0.0]
We present the quantum algorithm for the Longest Trail Problem. The running time of our algorithm is $O* (1.728m)$.
arXiv Detail & Related papers (2021-12-27T09:42:19Z)
Logarithmic Regret from Sublinear Hints [76.87432703516942]
We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
arXiv Detail & Related papers (2021-11-09T16:50:18Z)
Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
We show a modified span program algorithm to show these speed-ups persist even without having a promise ahead of time. Our algorithm uses $tildeO(sqrtkn)$ queries to solve this problem if there is a path with at most $k$ edges.
arXiv Detail & Related papers (2020-12-02T15:32:52Z)

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