Quantum Speedups for Hard Graph Problems Without Quantum RAM — and the Math Is Formalized in Lean

New polynomial-space quantum algorithms beat prior bounds on graph coloring, domination, and a dozen NP-hard problems. No QRAM required. Proofs machine-checked.

Imagine you're pruning a massive decision tree — like playing 20 Questions, except the tree has exponentially many branches and you need to find every valid answer, not just one. Classical algorithms prune branches one at a time. Grover search lets you check all remaining leaves quadratically faster, but it usually needs quantum RAM to hold the whole tree in superposition. This paper's core move: take a classical branching algorithm that already prunes most branches away, then apply Grover-style amplitude amplification only to the surviving terminals — so you get the quantum speedup without ever needing QRAM. The branching does the heavy lifting classically; the quantum part just accelerates what's left. The committed claim: polynomial-space quantum algorithms for a wide family of NP-hard combinatorial problems — graph coloring, dominating set, feedback vertex set, and more — that beat every previously known quantum bound in this resource model (bounded error, polynomial space, no QRAM). For 4-Colouring, the exponent drops from 1.3231 to 1.3032. For Dominating Set, it drops from ~1.4142 (which is 2^{n/2}) to 1.2235. These are not small improvements; shaving a base exponent from 1.42 to 1.22 on problems of size n = 100 means the quantum algorithm is roughly 10^5 times faster. The architecture is a hybrid of classical branching (measure-and-reduce algorithms that shrink the search tree via case analysis) composed with Grover-style amplitude amplification on the terminal subproblems. A key technical ingredient is a quantum form of 'monotone local search' — if the classical extension problem has a backtracking tree of size c^k, the quantum algorithm solves it in time (2 − 1/c)^{n/2}. This is a clean, general reduction: plug in any classical branching algorithm, get a quantum speedup on the leaves, polynomial space preserved throughout. No variational circuits, no fault-tolerant overhead assumptions — just query complexity on a gate-model quantum computer. The integrity story is unusually strong for a theory paper. The results are mathematical proofs, not simulations. Better yet, the core structural claims are formalized in Lean 4, with scripts and code released on GitHub. That is rare. When a complexity-theory paper ships a proof assistant formalization, the verification is as close to airtight as the field gets. The floating-point evaluations for k ≥ 6 coloring exponents are noted explicitly and handled with error margins — an honest acknowledgment of where rigor is computational rather than symbolic. The ladder is clear and well-documented. Every claimed bound is compared against the previous best in the same resource model (polynomial space, no QRAM). The paper doesn't cherry-pick weak baselines; it names the prior records and beats them across a dozen problems. The gap is most dramatic for Dominating Set (1.2235 vs. ~1.4142) and least dramatic for some k-Colouring values. Importantly, the paper does not claim to beat algorithms that use exponential space or QRAM — it is honest about the resource model it operates in. What's missing? No implementation, no quantum hardware experiments, no empirical validation. This is pure algorithmic theory. The obvious next experiment is an end-to-end gate-level resource estimate: how many physical qubits and gates would you actually need to run 4-Colouring on, say, a 50-vertex graph? The paper doesn't attempt this, and the honest read is that the focus is on asymptotic exponents, not near-term feasibility. The gap between 'best asymptotic exponent' and 'runnable on real hardware' remains enormous for all problems in this class. The milestone to watch is whether these exponents can be pushed further — the monotone local search framework is general enough that any improvement to the classical branching algorithms feeds directly into better quantum bounds. For the broader field, this paper matters because it demonstrates that you can get meaningful quantum speedups for exact exponential-time algorithms without the crutch of QRAM — which doesn't exist yet and may never exist cheaply. The polynomial-space constraint is the realistic one. The Lean formalization sets a standard that more theory papers should follow. If you work on quantum algorithms, combinatorial optimization, or parameterized complexity, this is a paper you'll cite.