Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2007.07040 · Quantum

Hybrid divide-and-conquer approach for tree search algorithms

Mathys Rennela, Sebastiaan Brand, Alfons Laarman, Vedran Dunjko

Published Mar 23, 2023• 15 citations
arXivHTMLPDF

Abstract

One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems.

DOI
10.22331/q-2023-03-23-959

Related papers

A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles

Yimin Ge, Vedran Dunjko

Recent works have shown that quantum computers can polynomially speed up certain SAT-solving algorithms even when the number of available qubits is significantly smaller than the number of variables. Here, we generalize this approach. We present a framework for hybrid quantum-classical algorithms which utilize quantum computers significantly smaller than the problem size. Given an arbitrarily small ratio of the quantum computer to the instance size, we achieve polynomial speedups for classical divide-and-conquer algorithms, provided that certain criteria on the time- and space-efficiency are met. We demonstrate how this approach can be used to enhance Eppstein’s algorithm for the cubic Hamiltonian cycle problem and achieve a polynomial speedup for any ratio of the number of qubits to the size of the graph.

arXiv:1907.01258•Journal of Mathematical Physics•Jan 1, 2020•18 citations

Quantum walk speedup of backtracking algorithms

Ashley Montanaro

$ $ We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on $n$ variables, or outputs that none exists, and whose corresponding tree contains $T$ vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using $O(\sqrt{T} n^{3/2} \log n)$ tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree.

arXiv:1509.02374•Theory of Computing•Jan 1, 2018•131 citations

Hybrid benchmarking of quantum algorithms

Andreea-Iulia Lefterovici

Combinatorial optimisation is a main topic for real-world applications, where fast solutions are required. Optimisation algorithms are incredibly powerful, but still face bottlenecks for certain problems. In recent years, quantum algorithms have been proposed as a potential candidate for solving such problems. The question that naturally arises is whether they could provide meaningful speed-ups over classical approaches. The study of asymptotic complexity has become central in the development of quantum algorithms. Nevertheless, having a promising asymptotic improvement does not directly translate into good practical performance. This is already well known for classical algorithms, which can be executed and evaluated directly. When it comes to quantum algorithms, the situation is more nuanced, as solving practically relevant instances would require a fully fault-tolerant quantum computer. In this thesis, we address the challenge of assessing the practical performance of a quantum algorithm without access to quantum hardware. Our strategy is to evaluate how these algorithms would perform under idealised fault-tolerant assumptions and to identify parameter regimes in which quantum approaches could potentially become useful. Our goal is to guide algorithmic development long before implementation becomes possible. We first give a general overview of the quantum (sub)routines that serve as building blocks for more advanced algorithms, as well as of the three hybrid benchmarking techniques used throughout this thesis. Then, we elaborate on each method: we start with the algorithmic descriptions, proceed to the methodology, and conclude with their hybrid evaluation on practically relevant datasets. Within the hybrid benchmarking method 1 (gate count analysis), we analytically derive the minimum number of gates that a quantum version of the classical simplex algorithm would require to solve realistic instances. By executing classical counterparts of the quantum subroutines, we infer the execution speed required per gate for the quantum simplex to outperform its classical counterpart. Within the hybrid benchmarking method 2 (query count analysis), we benchmark functional quantum linear solvers by analytically deriving a precise number of query calls made to the same oracles as a function of problem parameters. This provides insight into which algorithm might be more suitable in a given parameter regime. It allows for a direct comparison only between different quantum algorithms and is independent of classical runtime measurements. Within the hybrid benchmarking method 3 (cycle count analysis), we develop a runtime estimation framework tailored to the quantum tree generator–based search for solving 0-1-knapsack problems. We evaluate its performance on large scale instances beyond the reach of general simulation. We compare it with state-of-the-art classical linear programming solvers in terms of processor cycle counts. Hybrid benchmarking provides a fair, systematic benchmarking methodology, ensuring reproducible and relevant comparisons not only between classical and quantum approaches, but also among different quantum algorithms.

•Jan 1, 2026•0 citations

On the Quantum Time Complexity of Divide and Conquer

Allcock, Jonathan, Bao, Jinge, Aleksandrs Belovs +2 more

In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.

arXiv:2311.16401•Leibniz international proceedings in informatics•Nov 28, 2023•17 citations

Quantum Davis-Putnam-Logemann-Loveland and generalized constraints in iterative quantum algorithms

Anonymous, Stuart Hadfield

Too often, quantum computer scientists seek to create new algorithms entirely fresh from new cloth when there are extensive and optimized classical algorithms that can be generalized wholesale. At the same time, one may seek to maintain classical advantages of performance and runtime bounds, while enabling potential quantum improvement. Hybrid quantum algorithms tap into this potential, and here we explore a class of hybrid quantum algorithms called Iterative Quantum Algorithms (IQA) that are closely related to classical greedy or local search algorithms, employing a structure where the quantum computer provides information that leads to a simplified problem for future iterations. Specifically, we extend these algorithms beyond past results that considered primarily quadratic problems to arbitrary k-local Hamiltonians, proposing a general framework that incorporates logical inference in a fundamental way. As an application we develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems, which embeds IQAs within a complete backtracking based tree search framework. Our results also provide a general framework for handling problems with hard constraints in IQAs. We further show limiting cases of the algorithms where they reduce to classical algorithms, and provide evidence for regimes of quantum improvement.

arXiv:2509.02689•Physical Review A•Jul 14, 2026•6 citations

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•25 citations
One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems.
Recent works have shown that quantum computers can polynomially speed up certain SAT-solving algorithms even when the number of available qubits is significantly smaller than the number of variables. Here, we generalize this approach. We present a framework for hybrid quantum-classical algorithms which utilize quantum computers significantly smaller than the problem size. Given an arbitrarily small ratio of the quantum computer to the instance size, we achieve polynomial speedups for classical divide-and-conquer algorithms, provided that certain criteria on the time- and space-efficiency are met. We demonstrate how this approach can be used to enhance Eppstein’s algorithm for the cubic Hamiltonian cycle problem and achieve a polynomial speedup for any ratio of the number of qubits to the size of the graph.
$ $ We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on nnn variables, or outputs that none exists, and whose corresponding tree contains TTT vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using O(Tn3/2log⁡n)O(\sqrt{T} n^{3/2} \log n)O(T​n3/2logn) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree.
Combinatorial optimisation is a main topic for real-world applications, where fast solutions are required. Optimisation algorithms are incredibly powerful, but still face bottlenecks for certain problems. In recent years, quantum algorithms have been proposed as a potential candidate for solving such problems. The question that naturally arises is whether they could provide meaningful speed-ups over classical approaches. The study of asymptotic complexity has become central in the development of quantum algorithms. Nevertheless, having a promising asymptotic improvement does not directly translate into good practical performance. This is already well known for classical algorithms, which can be executed and evaluated directly. When it comes to quantum algorithms, the situation is more nuanced, as solving practically relevant instances would require a fully fault-tolerant quantum computer. In this thesis, we address the challenge of assessing the practical performance of a quantum algorithm without access to quantum hardware. Our strategy is to evaluate how these algorithms would perform under idealised fault-tolerant assumptions and to identify parameter regimes in which quantum approaches could potentially become useful. Our goal is to guide algorithmic development long before implementation becomes possible. We first give a general overview of the quantum (sub)routines that serve as building blocks for more advanced algorithms, as well as of the three hybrid benchmarking techniques used throughout this thesis. Then, we elaborate on each method: we start with the algorithmic descriptions, proceed to the methodology, and conclude with their hybrid evaluation on practically relevant datasets. Within the hybrid benchmarking method 1 (gate count analysis), we analytically derive the minimum number of gates that a quantum version of the classical simplex algorithm would require to solve realistic instances. By executing classical counterparts of the quantum subroutines, we infer the execution speed required per gate for the quantum simplex to outperform its classical counterpart. Within the hybrid benchmarking method 2 (query count analysis), we benchmark functional quantum linear solvers by analytically deriving a precise number of query calls made to the same oracles as a function of problem parameters. This provides insight into which algorithm might be more suitable in a given parameter regime. It allows for a direct comparison only between different quantum algorithms and is independent of classical runtime measurements. Within the hybrid benchmarking method 3 (cycle count analysis), we develop a runtime estimation framework tailored to the quantum tree generator–based search for solving 0-1-knapsack problems. We evaluate its performance on large scale instances beyond the reach of general simulation. We compare it with state-of-the-art classical linear programming solvers in terms of processor cycle counts. Hybrid benchmarking provides a fair, systematic benchmarking methodology, ensuring reproducible and relevant comparisons not only between classical and quantum approaches, but also among different quantum algorithms.
In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.
Too often, quantum computer scientists seek to create new algorithms entirely fresh from new cloth when there are extensive and optimized classical algorithms that can be generalized wholesale. At the same time, one may seek to maintain classical advantages of performance and runtime bounds, while enabling potential quantum improvement. Hybrid quantum algorithms tap into this potential, and here we explore a class of hybrid quantum algorithms called Iterative Quantum Algorithms (IQA) that are closely related to classical greedy or local search algorithms, employing a structure where the quantum computer provides information that leads to a simplified problem for future iterations. Specifically, we extend these algorithms beyond past results that considered primarily quadratic problems to arbitrary k-local Hamiltonians, proposing a general framework that incorporates logical inference in a fundamental way. As an application we develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems, which embeds IQAs within a complete backtracking based tree search framework. Our results also provide a general framework for handling problems with hard constraints in IQAs. We further show limiting cases of the algorithms where they reduce to classical algorithms, and provide evidence for regimes of quantum improvement.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.