Quantum Algorithm for the Longest Trail Problem

• URL: http://arxiv.org/abs/2112.13847v1
• Date: Mon, 27 Dec 2021 09:42:19 GMT
• Title: Quantum Algorithm for the Longest Trail Problem
• Authors: Kamil Khadiev and Ruslan Kapralov
• Abstract summary: We present the quantum algorithm for the Longest Trail Problem. The running time of our algorithm is $O* (1.728m)$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the quantum algorithm for the Longest Trail Problem. The problem is to search the longest edge-simple path for a graph with $n$ vertexes and $m$ edges. Here edge-simple means no edge occurs in the path twice, but vertexes can occur several times. The running time of our algorithm is $O^*(1.728^m)$.

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)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• 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)
• Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
  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.
  arXiv  Detail & Related papers  (2023-07-24T02:50:34Z)
• 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)
• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics. We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
  arXiv  Detail & Related papers  (2021-12-08T08:23:37Z)
• 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)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.