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

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

Ishan Patwardhan, Akhil Akkapelli

Published Oct 21, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2410.15626

Related papers

Assessing the Efficacy of Hybrid Quantum-Classical Computing for Combinatorial Optimization: A Comparative Analysis of QAOA and Classical Solver

Ayan Khan

This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.

•May 7, 2026•0 citations

Assessing the Efficacy of Hybrid Quantum-Classical Computing for Combinatorial Optimization: A Comparative Analysis of QAOA and Classical Solvers

Ayan Khan

The transition from theoretical quantum computing to practical real-world applications heavily relies onhybrid quantum-classical architectures designed for NoisyIntermediate-Scale Quantum (NISQ) devices. Among these approaches, the Quantum Approximate Optimization Algorithm(QAOA) is a prominent strategy for addressing complex combinatorial optimization challenges, such as the NP-hard MaxCut problem. Instead of performing the entire computationon a quantum processor, QAOA utilizes a quantum circuit toevaluate a parameterized cost function, whereas a classical optimizer refines the parameters iteratively. This study presentsa rigorous empirical evaluation comparing the performanceof QAOA against established classical solvers on small-scaleMax-Cut instances. All experiments were implemented andexecuted using Python (Qiskit Aer) on a state-vector simulator.Using Erdős–Rényi random graphs and regular graphs with4 to 20 nodes, we benchmark QAOA at depths p = 2 andp = 3 against simulated annealing, the Goemans–WilliamsonSDP-based algorithm, and a linear-time greedy heuristic. Ourexperimental results demonstrate that low-depth QAOA implementations exhibit severe performance degradation, prohibitive computational overhead (O(2^n) scaling), and low convergencerates compared to mature classical algorithms. At 20 nodes,QAOA (p = 2) achieves only a 0.467 approximation ratio versus0.856 for Goemans–Williamson, with a 210× runtime slowdownover greedy heuristics

•Jun 3, 2026•0 citations

Benchmarking QAOA vs Classical Algorithms for Max-Cut Optimization

Ayan Khan

This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.

•May 6, 2026•0 citations

Benchmarking QAOA vs Classical Algorithms for Max-Cut Optimization

Ayan Khan

This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.

•Jan 1, 2026•0 citations

Quantum-Enhanced Network Flow Optimization: A Max-Flow Min-Cut Perspective

Gagan Guruprasad Phadke, Vandana M. Ladwani

This paper is a comparison between classical and quantum inspired methods for solving the max-flow problem, which is commonly a foundational challenge in optimization and graph theory. This study will investigate the feasibility and performance of applying the Quantum Approximate Optimization Algorithm (QAOA) and other hybrid quantum-classical approaches to address the max-flow problem. This paper starts with comparing quantum approaches with well-established classical methods such as the Ford-Fulkerson and Edmonds-Karp.The main aim of this work is to asses how close quantum-inspired formulations can get to classical approaches in terms of their flow value as well as their runtime. Implementations are developed using the Qiskit framework on simulated quantum backends and compared against classical baselines across synthetic graph instances of varying sizes and densities. Experimentally, it can be seen that quantum approaches implemented using the QAOA technique managed to attain flow solutions comparable to classical ones, demonstrating similar accuracy, and in certain very dense graph configurations, competitive runtime performance due to parallelization in state-vector computing.These findings suggest that although current quantum-inspired approaches may not yet surpass classical algorithms in efficiency, but they can replicate their outcomes with reasonable fidelity. This provides an important validation of their applicability to combinatorial optimization. This study also lays groundwork for future research to explore hardware-level implementations, scalability enhancements, and also hybrid integration strategies for quantum optimization in network flow problems.

International Conference on Next-Gen Quantum and Advanced Computing: Algorithms, Security, and Beyond (NQComp)•Mar 5, 2026•0 citations

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 +2 more

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.

cs.DCCross-listedarXiv:2603.26232•Mar 30, 2026•0 citations
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.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
The transition from theoretical quantum computing to practical real-world applications heavily relies onhybrid quantum-classical architectures designed for NoisyIntermediate-Scale Quantum (NISQ) devices. Among these approaches, the Quantum Approximate Optimization Algorithm(QAOA) is a prominent strategy for addressing complex combinatorial optimization challenges, such as the NP-hard MaxCut problem. Instead of performing the entire computationon a quantum processor, QAOA utilizes a quantum circuit toevaluate a parameterized cost function, whereas a classical optimizer refines the parameters iteratively. This study presentsa rigorous empirical evaluation comparing the performanceof QAOA against established classical solvers on small-scaleMax-Cut instances. All experiments were implemented andexecuted using Python (Qiskit Aer) on a state-vector simulator.Using Erdős–Rényi random graphs and regular graphs with4 to 20 nodes, we benchmark QAOA at depths p = 2 andp = 3 against simulated annealing, the Goemans–WilliamsonSDP-based algorithm, and a linear-time greedy heuristic. Ourexperimental results demonstrate that low-depth QAOA implementations exhibit severe performance degradation, prohibitive computational overhead (O(2^n) scaling), and low convergencerates compared to mature classical algorithms. At 20 nodes,QAOA (p = 2) achieves only a 0.467 approximation ratio versus0.856 for Goemans–Williamson, with a 210× runtime slowdownover greedy heuristics
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
This paper is a comparison between classical and quantum inspired methods for solving the max-flow problem, which is commonly a foundational challenge in optimization and graph theory. This study will investigate the feasibility and performance of applying the Quantum Approximate Optimization Algorithm (QAOA) and other hybrid quantum-classical approaches to address the max-flow problem. This paper starts with comparing quantum approaches with well-established classical methods such as the Ford-Fulkerson and Edmonds-Karp.The main aim of this work is to asses how close quantum-inspired formulations can get to classical approaches in terms of their flow value as well as their runtime. Implementations are developed using the Qiskit framework on simulated quantum backends and compared against classical baselines across synthetic graph instances of varying sizes and densities. Experimentally, it can be seen that quantum approaches implemented using the QAOA technique managed to attain flow solutions comparable to classical ones, demonstrating similar accuracy, and in certain very dense graph configurations, competitive runtime performance due to parallelization in state-vector computing.These findings suggest that although current quantum-inspired approaches may not yet surpass classical algorithms in efficiency, but they can replicate their outcomes with reasonable fidelity. This provides an important validation of their applicability to combinatorial optimization. This study also lays groundwork for future research to explore hardware-level implementations, scalability enhancements, and also hybrid integration strategies for quantum optimization in network flow problems.
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.