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:2512.18464

Hierarchical divide and conquer quantum approach to combinatorial optimization problems with tunable reduction

Mathias Schmid, Naeimeh Mohseni, Michael J. Hartmann

quant-phSubmitted Dec 20, 2025• Announced Dec 23, 2025• 0 citations
arXivHTMLPDF

Abstract

Combinatorial optimization is considered a promising class of problems in which quantum computers can show significant advantages. However, problems of practical relevance typically have more variables than current or foreseeable quantum computers have qubits. Here we introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors. We then find all states of the subgraphs that can possibly be part of the solution to the entire problem by determining the cost or energy ranges in which the local subgraph energies of these states must be contained. This allows us to reduce the problem by only considering the subspace spanned by these states. We then recombine the system using a binary encoding for each subgraph with a local energy ordering. This process can be iterated until no further reduction is possible. We also find that the number of necessary qubits can be reduced further when only retaining states in a fraction of the relevant energy range at very little expense in terms of approximation ratio to the global ground state. In numerical simulations, we find that our approach allows us to solve combinatorial optimization problems on weighted random 3-regular graphs with $|\mathcal{V}|=40$ discrete variables on $\sim |\mathcal{V}| / 4$ qubits while retaining a possible approximation ratio of $\sim99.9\%$. We also observe an increasing reduction with larger system sizes.

Related papers

Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing

Zain H. Saleem, Teague Tomesh, Michael A. Perlin +2 more

We introduce a quantum divide and conquer algorithm that enables the use of distributed computing for constrained combinatorial optimization problems. The algorithm consists of three major components: classical partitioning of a target graph into multiple subgraphs, variational optimization over these subgraphs, and a quantum circuit cutting procedure that allows the optimization to take place independently on separate quantum processors. We simulate the execution of the quantum divide and conquer algorithm to find approximate solutions to instances of the Maximum Independent Set problem which have nearly twice as many nodes than the number of qubits available on a single quantum processor.

•Jul 15, 2021•11 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•12 citations

Towards large-scale quantum optimization solvers with few qubits

Marco Sciorilli, Lucas Borges, Taylor L. Patti +4 more

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over $$m={{\mathcal{O}}}({n}^{k})$$ binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.

arXiv:2401.09421•Nature Communications•Jan 8, 2025•47 citations

Large-Scale Quantum Approximate Optimization via Divide-and-Conquer

Junde Li, Mahabubul Alam, Swaroop Ghosh

Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm for solving combinatorial optimization problems. However, it cannot overcome qubit limitation for large-scale problems. Furthermore, the simulation time of QAOA scales poorly with the problem size. We propose a divide-and-conquer QAOA (DC-QAOA) to address the above challenges for graph maximum cut (MaxCut) problem. The algorithm works by recursively partitioning a larger graph into smaller ones whose MaxCut solutions are obtained with small-size noisy intermediate-scale quantum computers. The overall solution is retrieved from the subsolutions by applying the combination policy of measurement distribution reconstruction (MDR). The solution quality depends on the graph partitioning algorithm and MDR policy. Multiple partitioning and reconstruction methods are proposed and compared. Results are evaluated by metrics, such as quantum program runtime, measurement expectation value (EV), and approximation ratio (AR). The results show that DC-QAOA achieves 97.14% AR (20.32% higher than classical counterpart), and 94.79% EV (15.80% higher than quantum annealing). DC-QAOA solves large-scale graph instances with a polynomial rate or returns unsuccessful partition if graph connectivity requirement is not fulfilled otherwise.

arXiv:2102.13288•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 5, 2022•43 citations

A Resource-Efficient Variational Quantum Framework for the Traveling Salesman Problem

Yuefeng Lin, Chao Zheng, Cong Guo

The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.

quant-pharXiv:2605.00739•May 4, 2026•0 citations

Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization

Cameron, Ibrahim, Tomesh, Teague, Saleem, Zain +1 more

Quantum optimization as a field has largely been restricted by the constraints of current quantum computing hardware, as limitations on size, performance, and fidelity mean most non-trivial problem instances won't fit on quantum devices. Even proposed solutions such as distributed quantum computing systems may struggle to achieve scale due to the high cost of inter-device communication. To address these concerns, we propose Deferred Constraint Quantum Divide and Conquer Algorithm (DC-QDCA), a method for constructing quantum circuits which greatly reduces inter-device communication costs for some quantum graph optimization algorithms. This is achieved by identifying a set of vertices whose removal partitions the input graph, known as a separator; by manipulating the placement of constraints associated with the vertices in the separator, we can greatly simplify the topology of the optimization circuit, reducing the number of required inter-device operations. Furthermore, we introduce an iterative algorithm which builds on these techniques to find solutions for problems with potentially thousands of variables. Our experimental results using quantum simulators have shown that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.

arXiv:2405.00861•May 1, 2024•0 citations
Combinatorial optimization is considered a promising class of problems in which quantum computers can show significant advantages. However, problems of practical relevance typically have more variables than current or foreseeable quantum computers have qubits. Here we introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors. We then find all states of the subgraphs that can possibly be part of the solution to the entire problem by determining the cost or energy ranges in which the local subgraph energies of these states must be contained. This allows us to reduce the problem by only considering the subspace spanned by these states. We then recombine the system using a binary encoding for each subgraph with a local energy ordering. This process can be iterated until no further reduction is possible. We also find that the number of necessary qubits can be reduced further when only retaining states in a fraction of the relevant energy range at very little expense in terms of approximation ratio to the global ground state. In numerical simulations, we find that our approach allows us to solve combinatorial optimization problems on weighted random 3-regular graphs with ∣V∣=40|\mathcal{V}|=40∣V∣=40 discrete variables on ∼∣V∣/4\sim |\mathcal{V}| / 4∼∣V∣/4 qubits while retaining a possible approximation ratio of ∼99.9%\sim99.9\%∼99.9%. We also observe an increasing reduction with larger system sizes.
We introduce a quantum divide and conquer algorithm that enables the use of distributed computing for constrained combinatorial optimization problems. The algorithm consists of three major components: classical partitioning of a target graph into multiple subgraphs, variational optimization over these subgraphs, and a quantum circuit cutting procedure that allows the optimization to take place independently on separate quantum processors. We simulate the execution of the quantum divide and conquer algorithm to find approximate solutions to instances of the Maximum Independent Set problem which have nearly twice as many nodes than the number of qubits available on a single quantum processor.
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.
Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over m=O(nk)m={{\mathcal{O}}}({n}^{k})m=O(nk) binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.
Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm for solving combinatorial optimization problems. However, it cannot overcome qubit limitation for large-scale problems. Furthermore, the simulation time of QAOA scales poorly with the problem size. We propose a divide-and-conquer QAOA (DC-QAOA) to address the above challenges for graph maximum cut (MaxCut) problem. The algorithm works by recursively partitioning a larger graph into smaller ones whose MaxCut solutions are obtained with small-size noisy intermediate-scale quantum computers. The overall solution is retrieved from the subsolutions by applying the combination policy of measurement distribution reconstruction (MDR). The solution quality depends on the graph partitioning algorithm and MDR policy. Multiple partitioning and reconstruction methods are proposed and compared. Results are evaluated by metrics, such as quantum program runtime, measurement expectation value (EV), and approximation ratio (AR). The results show that DC-QAOA achieves 97.14% AR (20.32% higher than classical counterpart), and 94.79% EV (15.80% higher than quantum annealing). DC-QAOA solves large-scale graph instances with a polynomial rate or returns unsuccessful partition if graph connectivity requirement is not fulfilled otherwise.
The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.
Quantum optimization as a field has largely been restricted by the constraints of current quantum computing hardware, as limitations on size, performance, and fidelity mean most non-trivial problem instances won't fit on quantum devices. Even proposed solutions such as distributed quantum computing systems may struggle to achieve scale due to the high cost of inter-device communication. To address these concerns, we propose Deferred Constraint Quantum Divide and Conquer Algorithm (DC-QDCA), a method for constructing quantum circuits which greatly reduces inter-device communication costs for some quantum graph optimization algorithms. This is achieved by identifying a set of vertices whose removal partitions the input graph, known as a separator; by manipulating the placement of constraints associated with the vertices in the separator, we can greatly simplify the topology of the optimization circuit, reducing the number of required inter-device operations. Furthermore, we introduce an iterative algorithm which builds on these techniques to find solutions for problems with potentially thousands of variables. Our experimental results using quantum simulators have shown that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.