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

• URL: http://arxiv.org/abs/2603.26232v1
• Date: Fri, 27 Mar 2026 09:55:44 GMT
• Title: ParaQAOA: Efficient Parallel Divide-and-Conquer QAOA for Large-Scale Max-Cut Problems Beyond 10,000 Vertices
• Abstract summary: ParaQAOA is a parallel divide-and-conquer framework for large-scale Max-Cut problems.<n>It achieves 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.<n>ParaQAOA solves a 16,000-vertex instance in 19 minutes, compared to over 13.6 days required by the best-known approach.
• Score: 0.41942958779358674
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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

• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz.<n>One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally.<n>Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources.
  arXiv  Detail & Related papers  (2025-06-03T17:46:53Z)
• SCOOP: A Quantum-Computing Framework for Constrained Combinatorial Optimization [0.0]
  We present SCOOP, a novel framework for solving constrained optimization problems.<n>SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins.<n>We demonstrate the framework on three NP-hard problems, Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover.
  arXiv  Detail & Related papers  (2025-04-15T06:17:23Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem [6.783232060611114]
  We propose a framework for designing QAOA circuits to solve larger-scale Max-Cut problem. We derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Our framework only consumes $18$ qubits and $0.9950$ approximation ratio on average.
  arXiv  Detail & Related papers  (2023-07-28T02:06:42Z)
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management [45.82374977939355]
  We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms. We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem. Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
  arXiv  Detail & Related papers  (2023-02-08T17:09:20Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
  We propose a Divide-and-Conquer QAOA (DC-QAOA) to address the challenges for graph maximum cut (MaxCut) problem. DC-QAOA achieves 97.14% approximation ratio (20.32% higher than classical counterpart) It also reduces the time complexity of conventional QAOA from exponential to quadratic.
  arXiv  Detail & Related papers  (2021-02-26T03:10:30Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.