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

Chinese Control Conference (CCC)

A Tutorial on Quantum Approximate Optimization Algorithm for Maximum Independent Set Problem

Mingyu Yang, Fang Gao, Guojian Wu, Wei Dai, Feng Shuang

Published Jul 26, 2021• 3 citations
Publisher

Abstract

In the past few years, quantum computers and quantum algorithms have shown advantages compared to their classical counterparts. In combinatorial optimization problems, quantum approximate optimization algorithm(QAOA) has good performance. This paper focuses on the application of QAOA to one combinational problem called maximum independent set(MIS). Two different Hamiltonian construction methods are employed in this algorithm using IBM Qiskit. It is shown that the key is to design proper Hamiltonians to map the solution to the feasible states of the Hilbert space.

DOI
10.23919/ccc52363.2021.9550042

Related papers

A Tutorial on Quantum Approximate Optimization Algorithm (QAOA): Fundamentals and Applications

Jaeho Choi, Joongheon Kim

Over the past few years, many researchers around the world have been keen to know the potential and efficiency of quantum computers. The researchers have focused on specific issues that classical computers cannot solve or issues that quantum computers can handle in a better way. Among these various attractive research topics in quantum computers, this paper introduces the Quantum Approximate Optimization Algorithm (QAOA) which guarantees relatively considerable performances in many combinatorial optimization problems. For the comprehensive understanding of QAOA, this paper also describes the approximate optimization, the Quantum Alternating Operator Ansatz, and applications. Besides the theories of QAOA and Quantum Alternating Operator Ansatz, this paper explains the applications of QAOA to major combinatorial optimization problems such as maximum cut (MaxCut) problem and the max-independent set (MIS) problem.

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 1, 2019•121 citations

Iterative quantum algorithms for maximum independent set

Lucas T. Brady, Stuart Hadfield

Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study an alternative class of hybrid approaches to quantum optimization, termed iterative quantum algorithms, which in particular generalizes the recursive quantum approximate optimization algorithm (QAOA). This paradigm can incorporate hard problem constraints, which we demonstrate by considering the maximum independent set (MIS) problem. We show that, for QAOA with $p=1$ circuit layers, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper $p>1$ circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.

Physical Review A•Nov 25, 2024•12 citations

Proper Cost Hamiltonian Design for Combinatorial Optimization Problems: A Boolean Function Approach

Jaeho Choi, Seunghyeok Oh, Soohyun Park +2 more

Advanced researches on the variational quantum algorithms are actively conducted. In particular, the quantum approximate optimization algorithm (QAOA) is one of the promising variational quantum algorithms and can be applied to various graph-based problems, and is a promising algorithm that shows good performance even in small quantum computers. As is widely known, QAOA obtains the approximate solution via the expectation value of the cost Hamiltonian on the parameterized state. Therefore, in addition to finding the optimal parameters, the proper design of the cost Hamiltonian is important. This paper designs the cost function of the combinatorial optimization problem via Boolean function and maps it to the proper cost Hamiltonian. The proposed cost Hamiltonian design method is applied to the maximum independent set (MIS) and minimum dominating set (MDS) problems.

International Conference on Information Networking•Jan 13, 2021•0 citations

An Introduction to the Quantum Approximate Optimization Algorithm

Alessandro Giovagnoli

The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.

quant-pharXiv:2511.18377•Nov 25, 2025•0 citations

Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms

Lucas T. Brady, Stuart Hadfield

Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study a new class of hybrid approaches to quantum optimization, termed Iterative Quantum Algorithms, which in particular generalizes the Recursive Quantum Approximate Optimization Algorithm. This paradigm can incorporate hard problem constraints, which we demonstrate by considering the Maximum Independent Set (MIS) problem. We show that, for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper $p>1$ circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.

arXiv:2309.13110•Sep 22, 2023•4 citations

Transpilation and optimization of QAOA for maximum weighted independent set

Nguyen Viet Dung Nghiem, Sy Vinh Le, Thang N. Dinh

In recent years, quantum computing has shown promise in solving certain problems more efficiently than classical methods. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a leading candidate for achieving quantum advantage on noisy intermediate-scale quantum (NISQ) devices. This study explores the application of QAOA to the Maximum Weighted Independent Set (MWIS) problem, with particular focus on circuit transpilation strategies and parameter optimization methods. Using IBM Qiskit, we systematically examine factors affecting QAOA performance, including different transpilation optimization levels and classical optimizer selection. Our results demonstrate that optimization level 3 reduced circuit depth by 32% compared to level 0 for p=3 circuits, while maintaining solution quality. Among classical optimizers, COBYLA achieved an 81.24% approximation ratio with only 54.8 function evaluations at p=2, outperforming both grid search and SPSA methods. Execution on IBM’s real quantum hardware resulted in performance degradation ranging from 16% at p=1 to 34% at p=3 compared to ideal simulations, highlighting the compounding impact of noise and gate errors as circuit depth increases.These findings provide practical guidance for quantum algorithm implementation on NISQ devices, demonstrating that appropriate selection of transpilation techniques and optimization methods can substantially improve quantum resource efficiency while maintaining solution quality.

Journal of Computer Science and Cybernetics•Sep 3, 2026•0 citations
In the past few years, quantum computers and quantum algorithms have shown advantages compared to their classical counterparts. In combinatorial optimization problems, quantum approximate optimization algorithm(QAOA) has good performance. This paper focuses on the application of QAOA to one combinational problem called maximum independent set(MIS). Two different Hamiltonian construction methods are employed in this algorithm using IBM Qiskit. It is shown that the key is to design proper Hamiltonians to map the solution to the feasible states of the Hilbert space.
Over the past few years, many researchers around the world have been keen to know the potential and efficiency of quantum computers. The researchers have focused on specific issues that classical computers cannot solve or issues that quantum computers can handle in a better way. Among these various attractive research topics in quantum computers, this paper introduces the Quantum Approximate Optimization Algorithm (QAOA) which guarantees relatively considerable performances in many combinatorial optimization problems. For the comprehensive understanding of QAOA, this paper also describes the approximate optimization, the Quantum Alternating Operator Ansatz, and applications. Besides the theories of QAOA and Quantum Alternating Operator Ansatz, this paper explains the applications of QAOA to major combinatorial optimization problems such as maximum cut (MaxCut) problem and the max-independent set (MIS) problem.
Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study an alternative class of hybrid approaches to quantum optimization, termed iterative quantum algorithms, which in particular generalizes the recursive quantum approximate optimization algorithm (QAOA). This paradigm can incorporate hard problem constraints, which we demonstrate by considering the maximum independent set (MIS) problem. We show that, for QAOA with p=1p=1p=1 circuit layers, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper p>1p>1p>1 circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.
Advanced researches on the variational quantum algorithms are actively conducted. In particular, the quantum approximate optimization algorithm (QAOA) is one of the promising variational quantum algorithms and can be applied to various graph-based problems, and is a promising algorithm that shows good performance even in small quantum computers. As is widely known, QAOA obtains the approximate solution via the expectation value of the cost Hamiltonian on the parameterized state. Therefore, in addition to finding the optimal parameters, the proper design of the cost Hamiltonian is important. This paper designs the cost function of the combinatorial optimization problem via Boolean function and maps it to the proper cost Hamiltonian. The proposed cost Hamiltonian design method is applied to the maximum independent set (MIS) and minimum dominating set (MDS) problems.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study a new class of hybrid approaches to quantum optimization, termed Iterative Quantum Algorithms, which in particular generalizes the Recursive Quantum Approximate Optimization Algorithm. This paradigm can incorporate hard problem constraints, which we demonstrate by considering the Maximum Independent Set (MIS) problem. We show that, for QAOA with depth p=1p=1p=1, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper p>1p>1p>1 circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.
In recent years, quantum computing has shown promise in solving certain problems more efficiently than classical methods. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a leading candidate for achieving quantum advantage on noisy intermediate-scale quantum (NISQ) devices. This study explores the application of QAOA to the Maximum Weighted Independent Set (MWIS) problem, with particular focus on circuit transpilation strategies and parameter optimization methods. Using IBM Qiskit, we systematically examine factors affecting QAOA performance, including different transpilation optimization levels and classical optimizer selection. Our results demonstrate that optimization level 3 reduced circuit depth by 32% compared to level 0 for p=3 circuits, while maintaining solution quality. Among classical optimizers, COBYLA achieved an 81.24% approximation ratio with only 54.8 function evaluations at p=2, outperforming both grid search and SPSA methods. Execution on IBM’s real quantum hardware resulted in performance degradation ranging from 16% at p=1 to 34% at p=3 compared to ideal simulations, highlighting the compounding impact of noise and gate errors as circuit depth increases.These findings provide practical guidance for quantum algorithm implementation on NISQ devices, demonstrating that appropriate selection of transpilation techniques and optimization methods can substantially improve quantum resource efficiency while maintaining solution quality.