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

International Conference on Next-Gen Quantum and Advanced Computing: Algorithms, Security, and Beyond (NQComp)

Implementation of the Quantum Approximate Optimization Algorithm for Max-Cut

Sowmya B J, Geetha J, Vijaya Kumar B P, Bhavik Oswal, Tanu Shree Kumawat, Shantanu Pandey

Published Mar 5, 2026• 0 citations
Publisher

Abstract

This paper presents an experimental study of the Quantum Approximate Optimization Algorithm (QAOA) applied to the Max-Cut problem on small graph instances. Using PennyLane and a quantum simulator, a modular QAOA framework is implemented and evaluated on a fixed set of graphs, including ring, complete, star, and random graphs. For each graph, QAOA circuits with one and two layers are optimized using gradient-based methods, and the optimized states are sampled to obtain candidate cut solutions. The analysis includes visualizations of graph structures, cut partitions, bitstring distributions, and quantum circuit diagrams. This study serves as a clear and reproducible demonstration of QAOA behavior on combinatorial optimization problems.

DOI
10.1109/nqcomp68334.2026.11497732

Related papers

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•2 citations

Exploring graph cuts in quantum approximate optimization algorithm

Nongmeikapam Brajabidhu Singh, Anish Kumar Saha

Abstract Graph cut, a combinatorial optimization, is explored in quantum computing, seeking optimal bi-partitions of a directed or undirected, weighted or unweighted graph. The cut models, such as max-cut and min-cut, are applied in domains including VLSI design, circuit partitioning, data clustering, and network analysis. This paper explores the Ising modeling of max-cut and min-cut in a Laplacian-based QAOA, including benchmarking, spectral analysis, and a detailed analysis of the results. It aims to discover how Ising cut modeling and QAOA perform on a structured graph class, such as a weighted chordal graph. Chordal graphs offer decomposition properties favorable to QUBO and Ising models. Experimental results show that the proposed QAOA framework yields optimal or near-optimal cut values with high and stable approximation ratios across circuit depths. Also, hardware-aware considerations are introduced through superconducting qubit layout design and eigenmode simulations in Qiskit Metal and Ansys EPR HFSS. Further analysis reveals challenges related to convergence and performance in denser topologies. The study gives the modeling and the comprehensive evaluation of QAOA for graph-cuts, including a conceptual hardware-aware analysis.

Physica Scripta•Oct 29, 2025•1 citation

Per-Shot Evaluation of QAOA on Max-Cut: A Black-Box Implementation Comparison with Goemans-Williamson

Evgenii Dolzhkov, Franz G. Fuchs, Dirk Oliver Theis

The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for addressing combinatorial optimization problems on near-term quantum hardware. In this work, we conduct an empirical evaluation of QAOA on the Max-Cut problem, using the Goemans-Williamson (GW) algorithm as a classical baseline for comparison. Unlike many prior studies, our methodology treats QAOA implementations as black-box optimizers, relying solely on default parameter settings without manual fine-tuning. We evaluate specific off-the-shelf QAOA implementations under default settings, not the algorithmic potential of QAOA with optimized parameters. This reflects a more realistic use case for end users who may lack the resources or expertise for instance-specific optimization. To facilitate fair and informative evaluation, we construct benchmark instances using well-known graph generation models that emulate practical graph structures, avoiding synthetic constructions tailored to either quantum or classical algorithms. A central component of our analysis is a per-shot statistical framework, which tracks the quality of QAOA outputs as a function of the number of circuit executions. This enables probabilistic comparisons with the GW algorithm by examining when and how frequently QAOA surpasses classical performance baselines such as the GW expectation and lower bound. Our results provide insight into the practical applicability of QAOA for Max-Cut and highlight its current limitations, offering a framework that can guide the assessment and development of future QAOA implementations.

quant-pharXiv:2604.08367•Apr 10, 2026•0 citations

Evaluation of QAOA based on the approximation ratio of individual samples

Jason M. Larkin, Matías Jonsson, Daniel Justice +1 more

Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.

arXiv:2006.04831•Quantum Science and Technology•Apr 22, 2022•45 citations

Design of quantum approximation optimization algorithm for the maximum cut problem

Yun-Jiang Wang, XI Huiming, XIAO Zhuoyan +2 more

The max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.

Acta Physica Sinica•Jan 1, 2025•1 citation

Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem

Gavin E. Crooks

The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.

arXiv:1811.08419•Bulletin of the American Physical Society•Nov 20, 2018•340 citations
This paper presents an experimental study of the Quantum Approximate Optimization Algorithm (QAOA) applied to the Max-Cut problem on small graph instances. Using PennyLane and a quantum simulator, a modular QAOA framework is implemented and evaluated on a fixed set of graphs, including ring, complete, star, and random graphs. For each graph, QAOA circuits with one and two layers are optimized using gradient-based methods, and the optimized states are sampled to obtain candidate cut solutions. The analysis includes visualizations of graph structures, cut partitions, bitstring distributions, and quantum circuit diagrams. This study serves as a clear and reproducible demonstration of QAOA behavior on combinatorial optimization problems.
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.
Abstract Graph cut, a combinatorial optimization, is explored in quantum computing, seeking optimal bi-partitions of a directed or undirected, weighted or unweighted graph. The cut models, such as max-cut and min-cut, are applied in domains including VLSI design, circuit partitioning, data clustering, and network analysis. This paper explores the Ising modeling of max-cut and min-cut in a Laplacian-based QAOA, including benchmarking, spectral analysis, and a detailed analysis of the results. It aims to discover how Ising cut modeling and QAOA perform on a structured graph class, such as a weighted chordal graph. Chordal graphs offer decomposition properties favorable to QUBO and Ising models. Experimental results show that the proposed QAOA framework yields optimal or near-optimal cut values with high and stable approximation ratios across circuit depths. Also, hardware-aware considerations are introduced through superconducting qubit layout design and eigenmode simulations in Qiskit Metal and Ansys EPR HFSS. Further analysis reveals challenges related to convergence and performance in denser topologies. The study gives the modeling and the comprehensive evaluation of QAOA for graph-cuts, including a conceptual hardware-aware analysis.
The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for addressing combinatorial optimization problems on near-term quantum hardware. In this work, we conduct an empirical evaluation of QAOA on the Max-Cut problem, using the Goemans-Williamson (GW) algorithm as a classical baseline for comparison. Unlike many prior studies, our methodology treats QAOA implementations as black-box optimizers, relying solely on default parameter settings without manual fine-tuning. We evaluate specific off-the-shelf QAOA implementations under default settings, not the algorithmic potential of QAOA with optimized parameters. This reflects a more realistic use case for end users who may lack the resources or expertise for instance-specific optimization. To facilitate fair and informative evaluation, we construct benchmark instances using well-known graph generation models that emulate practical graph structures, avoiding synthetic constructions tailored to either quantum or classical algorithms. A central component of our analysis is a per-shot statistical framework, which tracks the quality of QAOA outputs as a function of the number of circuit executions. This enables probabilistic comparisons with the GW algorithm by examining when and how frequently QAOA surpasses classical performance baselines such as the GW expectation and lower bound. Our results provide insight into the practical applicability of QAOA for Max-Cut and highlight its current limitations, offering a framework that can guide the assessment and development of future QAOA implementations.
Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.
The max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.