Quantum search sharpens theoretical bounds for hard graph problems

Faster search, not an escape from exponential time

The paper studies problems whose search spaces grow rapidly with the number of vertices or elements, denoted by n. Graph colouring, for example, asks whether vertices can receive a fixed number of colours without adjacent vertices sharing a colour. Dominating Set asks for a small collection of vertices such that every vertex is selected or neighbours a selected vertex.

The proposed algorithms still take exponential time in the worst case. Their contribution is to reduce the base of that exponential. A bound proportional to 1.3032^n grows more slowly than one proportional to 1.3231^n, potentially creating a substantial asymptotic difference as n increases. These expressions are complexity bounds, however, not predictions of seconds on a particular computer.

All the stated quantum algorithms use polynomial space: their memory requirements grow no faster than a fixed power of input size. They also avoid quantum random access memory, a capability for accessing stored data through quantum superpositions. Their answers have bounded error rather than guaranteed correctness on every run; repetition can reduce that error.

Turning classical branches into quantum walks

The central method starts with classical branching algorithms. These repeatedly simplify an instance or split it into smaller alternatives, producing a search tree. A successful leaf represents a solution.

Senge checks whether particular algorithms fit the conditions needed for an existing quantum backtracking technique. Each node must be describable and processed with polynomial resources, the tree must have polynomial depth, and an explicit upper bound on its size must be available. Under these conditions, a quantum walk can detect a successful leaf in roughly the square root of the tree’s size, multiplied by polynomial overhead.

This is not a claim that any fast classical algorithm can automatically be accelerated this way. Some algorithms solve subsidiary optimization problems before continuing, rather than simply branching over alternatives. The paper explicitly excludes several such methods from its framework.

For colouring, the analysis combines a classical branching procedure with algorithms for handling the terminal instances where branching stops. Larger numbers of colours are addressed through established reductions to smaller colouring problems.

What the bounds improve

For four-colouring, the headline quantum running-time bound is O(1.3032^n), compared with the previous O(1.3231^n) bound reported for the same memory model. A version relying only on the earlier branching algorithm gives O(1.3100^n). The stronger result additionally uses terminal algorithms from another recent preprint.

The paper also reports improvements for selected numbers of colours between five and eighteen—not for every value in that range. Examples include O(1.4518^n) for five colours and O(1.9233^n) for eighteen.

For Dominating Set, the reported bound is O(1.2235^n). Independent Dominating Set receives O(1.1583^n), while Edge Dominating Set and Minimum Maximal Matching receive O(1.1501^n). Polynomial factors are suppressed in the underlying tree-based bounds.

A broader result concerns monotone local search: sample part of a possible solution, then use an extension algorithm to complete it. The quantum version combines amplitude amplification, which increases the chance of finding successful samples, with quantum backtracking for the completion step. If completion has a search tree bounded by c^k up to polynomial factors, where k is the remaining solution budget, the resulting bound is (2 − 1/c)^(n/2), again with polynomial overhead.

Applications include Feedback Vertex Set, which deletes vertices to eliminate cycles, at O(1.3081^n). Allowing approximate rather than optimal answers can improve the bounds further. A 1.1-approximation—returning a valid solution at most 10% larger than the optimum—is reported for Vertex Cover in O(1.0555^n).

Evidence and limits

This is a theoretical preprint, not a demonstrated quantum-computing speedup. The supplied paper reports selected arithmetic proofs checked in Lean and classical scripts testing algorithm components against brute force on small random instances. Those checks do not verify the entire argument or execute the quantum walks.

The larger-colouring calculations use floating-point evaluation with a stated safety margin, not interval arithmetic. The strongest four-colouring result depends on terminal algorithms that the author identifies as unrefereed. Other bounds inherit numerical analyses from their classical sources.

Version 1 was posted to arXiv on 9 November 2026. Its results should therefore be read as proposed theoretical improvements awaiting further scrutiny. The main contribution is a route for converting suitable classical search structures into better quantum complexity bounds, not evidence that these problems are now practical to solve on quantum hardware.