← Back to papers
Quantum Algorithm for the Longest Trail Problem
K. Khadiev, Ruslan Kapralov·December 27, 2021
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
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)$.