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

ParaQAOA: Efficient Parallel Divide-and-Conquer QAOA for Large-Scale Max-Cut Problems Beyond 10,000 Vertices

Po-Hsuan Huang, Xie-Ru Li, Chi Chuang, Chia-Heng Tu, Shih-Hao Hung

cs.DCcs.PFcs.SEquant-phSubmitted Mar 27, 2026• Announced Mar 30, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising solution for combinatorial optimization problems using a hybrid quantum-classical framework. Among combinatorial optimization problems, the Maximum Cut (Max-Cut) problem is particularly important due to its broad applicability in various domains. While QAOA-based Max-Cut solvers have been developed, they primarily favor solution accuracy over execution efficiency, which significantly limits their practicality for large-scale problems. To address the limitation, we propose ParaQAOA, a parallel divide-and-conquer QAOA framework that leverages parallel computing hardware to efficiently solve large Max-Cut problems. ParaQAOA significantly reduces runtime by partitioning large problems into subproblems and solving them in parallel while preserving solution quality. This design not only scales to graphs with tens of thousands of vertices but also provides tunable control over accuracy-efficiency trade-offs, making ParaQAOA adaptable to diverse performance requirements. Experimental results demonstrate that ParaQAOA achieves up to 1,600x speedup over state-of-the-art methods on Max-Cut problems with 400 vertices while maintaining solution accuracy within 2% of the best-known solutions. Furthermore, ParaQAOA solves a 16,000-vertex instance in 19 minutes, compared to over 13.6 days required by the best-known approach. These findings establish ParaQAOA as a practical and scalable framework for large-scale Max-Cut problems under stringent time constraints.

Related papers

MillionQAOA: A Dividable QAOA Framework for Solving Million-Vertex-Scale Max-Cut Problems

Xie-Ru Li, Po-Hsuan Huang, Chia-Heng Tu +1 more

Hybrid quantum-classical optimization has made the Quantum Approximate Optimization Algorithm (QAOA) a leading candidate for combinatorial optimization tasks, and Max-Cut stands out among them for its broad practical footprint and its clean reduction to QUBO and Ising form. Prior divide-and-conquer adaptations push QAOA toward larger inputs, yet they stay capped at tens of thousands of vertices and never engage modern GPU cluster hardware, leaving million-scale instances out of reach. This work closes that gap with MillionQAOA, a GPU-accelerated divide-and-conquer framework capable of solving Max-Cut instances of up to one million vertices on multi-node H100 GPU clusters. The framework is organized as a four-phase, topology-aware pipeline: parallel graph synthesis, solver-shard formation, concurrent GPU-parallel circuit solving, and candidate consolidation through boundary binning paired with a layer-wise frontier expansion. On a testbed of 8 DGX-H100 nodes (64 GPUs in total), MillionQAOA scales near-linearly from 62.5K through 1M vertices, matches classical greedy solvers in cut quality at the 50K-vertex mark (within 0.2% higher), and cuts execution time by up to 13.6 ×, making it a deployable route to million-vertex Max-Cut at scale.

Proceedings of the International Conference on Parallel Processing•Sep 13, 2026•0 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

Edge-based quantum approximate optimization algorithm for MAX-CUT problem

Youngjin Seo, Jun Heo

Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.

Quantum Information Processing•Sep 23, 2025•1 citation

Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA

Aniello Esposito, Tamuz Danzig

The Quantum approximate optimization algorithm (QAOA) is a leading hybrid classical-quantum algorithm for solving complex combinatorial optimization problems. QAOA-in-QAOA (QAOA2) uses a divide-and-conquer heuristic to solve large-scale Maximum Cut (MaxCut) problems, where many sub-graph problems can be solved in parallel. In this work, an implementation of the QAOA2method for the scalable solution of the MaxCut problem is presented, based on the Classiq platform. The framework is executed on an HPE-Cray EX supercomputer by means of the Message Passing Interface (MPI) and the SLURM workload manager. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated to understand if QAOA2could benefit from solving certain sub-graphs classically. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices. For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW.

arXiv:2406.17383•IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 27, 2024•4 citations

QAOA-in-QAOA: Solving Large-Scale MaxCut Problems on Small Quantum Machines

Z.-F. Zhou, Yuxuan Du, Xinmei Tian +1 more

The design of fast algorithms for combinatorial optimization greatly contributes to a plethora of domains such as logistics, finance, and chemistry. Quantum approximate optimization algorithms (QAOAs), which utilize the power of quantum machines and inherit the spirit of adiabatic evolution, are approaches to tackle combinatorial problems with potential runtime speedups. However, hurdled by the limited quantum resources nowadays, QAOAs are infeasible to manipulate large-scale problems. To address this issue, here we revisit the MaxCut problem via the divide-and-conquer heuristic: seek the solutions of subgraphs in parallel and then merge these solutions to obtain the global solution. Because of the ${\mathbb{Z}}_{2}$ symmetry in MaxCut, we prove that the merging process can be further cast into a new MaxCut problem and thus be addressed by QAOAs or other MaxCut solvers. In view of this, we propose QAOA-in-QAOA (${\mathrm{QAOA}}^{2}$) to solve arbitrary large-scale MaxCut problems using small quantum machines. We also prove that the performance of ${\mathrm{QAOA}}^{2}$ is lower bounded with respect to the divide-and-conquer process. Experiment results illustrate that, under different graph settings, ${\mathrm{QAOA}}^{2}$ attains a competitive or even better performance over classical algorithms when the node count is around $2000$. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale combinatorial optimization problems.

arXiv:2205.11762•Physical Review Applied•Feb 9, 2023•77 citations

Hybrid Quantum-HPC Solutions for Max-Cut: Bridging Classical and Quantum Algorithms

Ishan Patwardhan, Akhil Akkapelli

This research explores the integration of the Quantum Approximate Optimization Algorithm (QAOA) into Hybrid Quantum-HPC systems for solving the Max-Cut problem, comparing its performance with classical algorithms like brute-force search and greedy heuristics. We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. Using simulations, we evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization. The study also investigates the scalability of QAOA with increasing problem size, offering insights into its potential advantages over classical methods for large-scale combinatorial optimization problems, with implications for future Quantum computing applications in HPC environments.

arXiv:2410.15626•Oct 21, 2024•0 citations
Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising solution for combinatorial optimization problems using a hybrid quantum-classical framework. Among combinatorial optimization problems, the Maximum Cut (Max-Cut) problem is particularly important due to its broad applicability in various domains. While QAOA-based Max-Cut solvers have been developed, they primarily favor solution accuracy over execution efficiency, which significantly limits their practicality for large-scale problems. To address the limitation, we propose ParaQAOA, a parallel divide-and-conquer QAOA framework that leverages parallel computing hardware to efficiently solve large Max-Cut problems. ParaQAOA significantly reduces runtime by partitioning large problems into subproblems and solving them in parallel while preserving solution quality. This design not only scales to graphs with tens of thousands of vertices but also provides tunable control over accuracy-efficiency trade-offs, making ParaQAOA adaptable to diverse performance requirements. Experimental results demonstrate that ParaQAOA achieves up to 1,600x speedup over state-of-the-art methods on Max-Cut problems with 400 vertices while maintaining solution accuracy within 2% of the best-known solutions. Furthermore, ParaQAOA solves a 16,000-vertex instance in 19 minutes, compared to over 13.6 days required by the best-known approach. These findings establish ParaQAOA as a practical and scalable framework for large-scale Max-Cut problems under stringent time constraints.
Hybrid quantum-classical optimization has made the Quantum Approximate Optimization Algorithm (QAOA) a leading candidate for combinatorial optimization tasks, and Max-Cut stands out among them for its broad practical footprint and its clean reduction to QUBO and Ising form. Prior divide-and-conquer adaptations push QAOA toward larger inputs, yet they stay capped at tens of thousands of vertices and never engage modern GPU cluster hardware, leaving million-scale instances out of reach. This work closes that gap with MillionQAOA, a GPU-accelerated divide-and-conquer framework capable of solving Max-Cut instances of up to one million vertices on multi-node H100 GPU clusters. The framework is organized as a four-phase, topology-aware pipeline: parallel graph synthesis, solver-shard formation, concurrent GPU-parallel circuit solving, and candidate consolidation through boundary binning paired with a layer-wise frontier expansion. On a testbed of 8 DGX-H100 nodes (64 GPUs in total), MillionQAOA scales near-linearly from 62.5K through 1M vertices, matches classical greedy solvers in cut quality at the 50K-vertex mark (within 0.2% higher), and cuts execution time by up to 13.6 ×, making it a deployable route to million-vertex Max-Cut at scale.
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.
Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.
The Quantum approximate optimization algorithm (QAOA) is a leading hybrid classical-quantum algorithm for solving complex combinatorial optimization problems. QAOA-in-QAOA (QAOA2) uses a divide-and-conquer heuristic to solve large-scale Maximum Cut (MaxCut) problems, where many sub-graph problems can be solved in parallel. In this work, an implementation of the QAOA2method for the scalable solution of the MaxCut problem is presented, based on the Classiq platform. The framework is executed on an HPE-Cray EX supercomputer by means of the Message Passing Interface (MPI) and the SLURM workload manager. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated to understand if QAOA2could benefit from solving certain sub-graphs classically. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices. For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW.
The design of fast algorithms for combinatorial optimization greatly contributes to a plethora of domains such as logistics, finance, and chemistry. Quantum approximate optimization algorithms (QAOAs), which utilize the power of quantum machines and inherit the spirit of adiabatic evolution, are approaches to tackle combinatorial problems with potential runtime speedups. However, hurdled by the limited quantum resources nowadays, QAOAs are infeasible to manipulate large-scale problems. To address this issue, here we revisit the MaxCut problem via the divide-and-conquer heuristic: seek the solutions of subgraphs in parallel and then merge these solutions to obtain the global solution. Because of the Z2{\mathbb{Z}}_{2}Z2​ symmetry in MaxCut, we prove that the merging process can be further cast into a new MaxCut problem and thus be addressed by QAOAs or other MaxCut solvers. In view of this, we propose QAOA-in-QAOA (QAOA2{\mathrm{QAOA}}^{2}QAOA2) to solve arbitrary large-scale MaxCut problems using small quantum machines. We also prove that the performance of QAOA2{\mathrm{QAOA}}^{2}QAOA2 is lower bounded with respect to the divide-and-conquer process. Experiment results illustrate that, under different graph settings, QAOA2{\mathrm{QAOA}}^{2}QAOA2 attains a competitive or even better performance over classical algorithms when the node count is around 200020002000. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale combinatorial optimization problems.
This research explores the integration of the Quantum Approximate Optimization Algorithm (QAOA) into Hybrid Quantum-HPC systems for solving the Max-Cut problem, comparing its performance with classical algorithms like brute-force search and greedy heuristics. We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. Using simulations, we evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization. The study also investigates the scalability of QAOA with increasing problem size, offering insights into its potential advantages over classical methods for large-scale combinatorial optimization problems, with implications for future Quantum computing applications in HPC environments.