The authors' quantum algorithm for the Hamiltonian cycle problem has a worst-case time bound of O(2^{n/4}) on 3-regular undirected graphs with n nodes.

The paper

The paper's details are OpenAlex's; the citation count is OpenAlex's, 18 Oct 2026. The line on the paper is machine-written, as noted under Why it matters.

Why it matters

Written by Claude (claude-sonnet-5-5) on 18 Oct 2026 from the paper's abstract (as arXiv publishes it) and its OpenAlex record. Machine-written context to help a reader: it is not evidence, it moves no number, and it may be wrong. The quoted sentence is the claim; where it stands is computed from the record. If it misreads the paper, tell the stewards.

The story so far

1. 1

   What the authors did

   The authors designed a quantum algorithm that first restricts the search to a subspace containing all valid assignments, then runs a quantum search there. They derived worst-case complexity bounds and applied them by mapping the Hamiltonian cycle problem to Exact Satisfiability.

   Machine-written from the paper's abstract, as noted under Why it matters.

2. 2

   What they found

   • The quantum algorithm has worst-case query complexities of O(√(2^(n−M'))) for finding a solution and O(2^(n−M')) for counting solutions, where M' is the number of linearly independent clauses.
   • The same O(2^{n/4}) bound holds for (3,3)-regular bipartite graphs, where the best classical algorithm is stated as O(2^{31n/96}).
   • For random instances near the satisfiability threshold, the algorithm is said to be faster than classical WalkSAT and Adiabatic Quantum Optimization.

   Machine-written from the paper's abstract, as noted under Why it matters.

3. 3

   What has been checked on Ecdysis

   Exuvia registered the claim on 18 October 2026, with a test written from the paper. No check has been filed yet.

What would check it

How far it has been checked

1. 1
   The object itself, checked againverification · not yet

   Not yet: re-run the paper's analysis on its own data, where the authors have published it.

2. 2
   New instances of the constructionreproduction · not yet

   Not yet: the same construction run afresh.

3. 3
   The designrobustness tests and arguments · not yet

   Nothing yet: change the method or the data and see whether it holds (a robustness test), or argue that the method does not test what the claim says.

How sure is the record?

Share this finding

Ready-made posts, written from the record. You post them yourself, from your own account; nothing is ever posted for anyone.

Click a post's text to select all of it. Both posts give the claim's standing on the record, and the longer one says what the checks show and what they do not; the wording changes when the record does. The longer post quotes the paper first, then gives the machine-written headline, marked as such; edit it as you like. To cite the claim, see Cite this claim.

What would prove it wrong

Refuted if an infinite family of 3‑regular graphs is shown to force the algorithm to run in time ω(2^{n/4}), or a rigorous proof that its worst‑case running time is Ω(2^{αn}) for some α>1/4.

The test as Exuvia registered it on 18 Oct 2026, written from the paper's words.

The wider literature

Other claims from the same paper

• uncheckedThe quantum algorithm's worst-case query counts are O(√(2^(n−M′))) to find or certify a solution and O(2^(n−M′)) to count solutions.“The query complexities for the worst-case are respectively bounded by $O(\sqrt{2^{n-M^{\prime}}})$ and $O(2^{n-M^{\prime}})$, where $n$ is the number of variables and $M^{\prime}$ the number of linea…”

Headlines are machine-written from the paper's abstract, or from the quote and the paper's title where no abstract is open; each claim's own words are quoted beneath its headline.