⚛️ quantum physics

Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

This paper presents polynomial-space quantum algorithms without quantum random access memory that significantly improve the exponential-time bounds for various NP-hard problems, including graph colouring, domination, and monotone local search tasks, by leveraging classical branching techniques and a new quantum form of monotone local search.

Original author: Sebastian Senge

Published 2026-11-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original author: Sebastian Senge

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where solving a complex puzzle requires checking every single possible arrangement of pieces, one by one. For many problems involving networks, maps, or schedules, the number of arrangements is so vast that even the fastest supercomputers would take longer than the age of the universe to find the answer. This is the realm of exponential-time problems, where the difficulty grows so rapidly that adding just a few more items to the puzzle makes the task suddenly impossible. For decades, computer scientists have accepted that some of these problems are simply too hard to solve quickly, no matter how clever the method. However, a new approach is changing the landscape by showing how quantum computers, which operate on the strange rules of the subatomic world, can navigate these vast forests of possibilities much faster than classical machines, without needing to store every single path in memory.

The core of this challenge lies in how we search for solutions. In a classical computer, finding a solution often feels like walking through a massive, branching maze. You choose a path, hit a dead end, and have to walk all the way back to the last choice to try a different route. If the maze has billions of branches, this process takes an enormous amount of time. Quantum computers offer a different way of moving through this maze. Instead of walking one path at a time, they can explore many paths simultaneously, using a technique that allows them to "feel" for the correct exit much more quickly. The new research demonstrates that for a specific and important class of problems—those involving coloring maps, finding efficient groups of nodes in a network, or deleting specific parts of a graph to fix a structure—this quantum speedup can be achieved even with very limited memory. The researchers have built algorithms that run in polynomial space, meaning they do not need to store the entire history of their search, a crucial constraint for practical quantum devices.

The paper focuses on three main types of problems that appear frequently in computer science and mathematics. The first is graph coloring, which asks whether a map can be colored with a limited number of colors so that no two touching regions share the same color. The second involves domination problems, which ask for the smallest group of points in a network that can "watch over" or connect to every other point. The third category includes problems where you must remove a few specific elements to break cycles or fix structural issues, such as finding the minimum number of vertices to delete to eliminate all loops in a network. For each of these, the researchers took the best-known classical algorithms, which are already quite fast but still require exponential time, and adapted them for quantum computers. They did this by proving that the step-by-step logic of these classical algorithms forms a specific kind of tree structure. This structure allows a quantum computer to use a "quantum walk" to find the solution in roughly the square root of the time a classical computer would need.

The results are a significant reduction in the time required to solve these problems. For the classic four-coloring problem, the new quantum algorithm can find a solution in a time proportional to 1.3032 raised to the power of the number of vertices. This is a meaningful improvement over the previous best quantum estimate of 1.3231. For problems requiring more colors, such as five or up to eighteen, the new method consistently beats the old limits, with the time required growing much more slowly as the number of colors increases. For domination problems, the improvements are even more striking. The time to find a dominating set drops from a previous best of roughly 1.4969 to 1.2235, and for finding an independent dominating set, it falls to 1.1583. These numbers might seem abstract, but in the world of exponential growth, a small reduction in the base number translates to a massive saving in actual computing time for large networks.

The researchers also applied this logic to a technique called monotone local search, which is used for problems where you start with a partial solution and try to extend it to a full one. By combining this with quantum search, they created a new method that solves problems like finding the minimum set of vertices to delete to break all cycles in a graph. For this specific problem, the new quantum time is roughly 1.3081 raised to the power of the number of vertices, representing the first known quantum bound for this approach, as no prior quantum form of monotone local search had been stated. Perhaps most interestingly, the team showed that this approach works not just for finding the perfect, exact solution, but also for finding "good enough" approximations. For example, they demonstrated a way to find a solution for the vertex cover problem that is only 10 percent larger than the perfect answer, but can be found in a time proportional to 1.0555 raised to the power of the number of vertices. This is faster than finding the exact solution, offering a practical trade-off for real-world applications where a near-perfect answer is often sufficient.

A critical aspect of this work is the strict limitation on memory. The algorithms are designed to run with polynomial space, meaning the amount of memory they need grows at a manageable rate as the problem gets bigger. This is a vital constraint because current and near-future quantum computers will not have the massive memory capacity required by other theoretical quantum algorithms that rely on "quantum random access memory." By avoiding this requirement, the researchers have created a path that is more realistic for hardware that will actually exist. They verified their results using a combination of mathematical proofs and computer simulations, checking that the algorithms behave correctly on random graphs and that the time estimates hold up under scrutiny. The work does not claim to have solved these problems in a way that makes them easy for any computer; rather, it has pushed the boundary of what is possible, showing that quantum machines can tackle these difficult, exponential-time puzzles with a level of efficiency that was previously thought to require more memory than is feasible.

The implications of these findings extend beyond the specific numbers. The research establishes a clear blueprint for how to take existing, highly optimized classical algorithms and translate them into the quantum realm without losing their efficiency or demanding impossible resources. It suggests that for a wide range of hard problems, the path to a quantum advantage may not require inventing entirely new mathematical theories, but rather carefully re-engineering the way we traverse the search space. As quantum hardware continues to develop, these polynomial-space algorithms provide a concrete target for what these machines can achieve. The work confirms that the speedup is real and measurable, offering a glimpse of a future where problems that are currently intractable for classical computers might become solvable, provided we can build the machines to run these specific, memory-efficient quantum paths.

Technical Summary: Polynomial-Space Quantum Algorithms from Classical Branching

Problem Statement
This work addresses the design of quantum algorithms for exponential-time combinatorial problems on graphs and sets, specifically focusing on $k$ -Colouring, Domination problems, and Monotone Local Search variants. The algorithms operate under strict constraints: they must have bounded error, use only polynomial space, and crucially, do not utilize Quantum Random Access Memory (QRAM). The goal is to improve upon the best-known quantum time bounds in this specific model, which previously relied on reductions from classical algorithms or generic search techniques.

Methodology
The core methodology leverages the observation that many efficient classical exact algorithms for NP-hard problems are structured as backtracking trees. The paper applies the quantum walk algorithm of [31] (Montanaro) to these trees. If a classical algorithm explores a search tree with $T$ nodes, the quantum walk can decide the existence of a marked leaf (a solution) in time $O(\sqrt{T} \cdot \text{poly}(n))$ using polynomial space.

The approach involves three main technical components:

Tree Verification: Demonstrating that specific classical branching algorithms (from sources like [43], [45], [33], [34], [7], etc.) can be viewed as backtracking trees where the number of nodes is bounded by $c^n$ for some base $c$ .
Quantum Speedup: Applying the square-root speedup to the classical running time $O(c^n)$ , resulting in quantum time $O(c^{n/2})$ .
Recursive Evaluation for $k$ -Colouring: For $k$ -Colouring with $k \ge 6$ , the paper utilizes the reduction framework of [36]. It evaluates the recursion relations governing the running time, replacing the exact maximums with computable upper bounds derived from floating-point evaluations with a safety margin. This allows the construction of explicit quantum procedures with verified time bounds.
Monotone Local Search: The paper extends the "monotone local search" paradigm [17] to the quantum setting. It combines amplitude amplification over random samples with the quantum walk on the extension algorithm's backtracking tree. This yields a quantum running time of $(2 - 1/c)^{n/2}$ if the classical extension problem has a tree of size $c^k$ .

Key Contributions and Results

$k$ -Colouring:
- 4-Colouring: The paper shows that the polynomial-space branching algorithm of [43], combined with terminal algorithms from [45], forms a backtracking tree. This yields a quantum time of $O(1.3032^n)$ , improving the previous best bound of $O(1.3231^n)$ [36]. Using [43] alone yields $O(1.3100^n)$ .
- $k \ge 5$ : By evaluating the recursion of [36] with the new base cases for 3- and 4-colouring, the author provides improved quantum time bounds for $k \in \{5, 7, \dots, 18\}$ . For example, 5-Colouring is solved in $O(1.4518^n)$ (down from $O(1.4695^n)$ ), and 18-Colouring in $O(1.9233^n)$ . These exponents are derived from floating-point computations with margins to ensure they are rigorous upper bounds.
Domination Problems:
- The author proves that the decision versions of classical branch-and-reduce algorithms for Dominating Set, Independent Dominating Set, Edge Dominating Set, and Minimum Maximal Matching are backtracking trees.
- Dominating Set: Improved from $O(2^{n/2})$ [42] to $O(1.2235^n)$ .
- Independent Dominating Set: Improved to $O(1.1583^n)$ .
- Edge Dominating Set / Minimum Maximal Matching: Improved to $O(1.1501^n)$ .
- These results rely on the square root of the classical bases established in [33, 34, 7, 24]. The paper notes that faster classical algorithms exist (e.g., [24] for Dominating Set), but their structures are not covered by the backtracking tree framework used here; if they were, they would yield even faster quantum bounds.
Monotone Local Search:
- A quantum form of monotone local search is introduced. If the extension problem has a backtracking tree of size $c^k$ , the subset problem is solved in $(2 - 1/c)^{n/2}$ .
- Exact Bounds: This yields improvements for Feedback Vertex Set ( $O(1.3081^n)$ ), Cluster Vertex Deletion ( $O(1.2033^n)$ ), 3-Hitting Set ( $O(1.2405^n)$ ), Proper Interval Vertex Deletion ( $O(1.3541^n)$ ), Multicut on Trees ( $O(1.1647^n)$ ), and Min-Ones $d$ -SAT ( $O((2-1/d)^{n/2})$ ).
- Approximation: The framework is extended to exponential-time approximations. For instance, a 1.1-approximation for Vertex Cover is achieved in $O(1.0555^n)$ , and for Feedback Vertex Set in $O(1.2161^n)$ . These bounds are strictly below the quantum exact bounds for the same problems.

Significance and Claims
The paper provides quantum algorithms for these specific problems in the polynomial-space, no-QRAM model that improve upon previously known quantum bounds (such as $O(2^{n/2})$ for Dominating Set) and, where applicable, the square roots of the best-known backtracking-tree-based classical algorithms.

Rigorous Verification: The author emphasizes that the exponents for $k \ge 6$ are not just theoretical limits but upper bounds on the running time of an explicit algorithm. The values were computed using floating-point arithmetic with a margin far exceeding rounding errors, and specific inequalities were verified using the Lean theorem prover.
Modesty on Scope: The author explicitly states that their results apply to algorithms that can be modeled as backtracking trees. They note that faster classical algorithms involving steps like computing the optimum of a sub-part before a tail call (e.g., certain 3-Hitting Set algorithms) or multivariate local search forms are not covered by this framework. Consequently, the quantum improvements are relative to the specific classical algorithms that fit the backtracking tree model.
Approximation Novelty: The paper highlights that no quantum algorithm designed specifically for exponential-time approximation of these problems had been stated prior to this work. The approximate bounds provided are the first of their kind in this model.

The work serves as a bridge, demonstrating that improvements in classical polynomial-space branching algorithms directly translate to improved quantum algorithms in the polynomial-space, no-QRAM model via the square-root speedup of the quantum walk.

Technical Summary: Polynomial-Space Quantum Algorithms from Classical Branching

More like this