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:1905.04809 · International Journal of Quantum Information

Max-independent set and the quantum alternating operator ansatz

Zain H. Saleem

Published Jun 1, 2020• 28 citations
arXivHTMLPDF

Abstract

The maximum-independent set (MIS) problem of graph theory using the quantum alternating operator ansatz is studied. We perform simulations on the Rigetti Forest simulator for the square ring, [Formula: see text], and [Formula: see text] graphs and analyze the dependence of the algorithm on the depth of the circuit and initial states. The probability distribution of observation of the feasible states representing maximum-independent sets is observed to be asymmetric for the MIS problem, which is unlike the Max-Cut problem where the probability distribution of feasible states is symmetric. For asymmetric graphs, it is shown that the algorithm clearly favors the independent set with the larger number of elements even for finite circuit depth. We also compare the approximation ratios for the algorithm when we choose different initial states for the square ring graph and show that it is dependent on the choice of the initial state.

DOI
10.1142/s0219749920500112

Related papers

Maximum weighted independent set and quantum alternating operator ansatz

Zain H. Saleem

We study the maximum weighted independent set problem of graph theory using the quantum approximate optimization algorithm. We perform simulations on the Rigetti Forrest simulator and analyze the dependence of the algorithm on the depth of the circuit, intial states and the wieghts of the vertices. We also numerically obtain an estimate of the expected approximation ratio of the algorithm for the circuit depths of p=1 and p=2 for a degree 2 graph.

•May 12, 2019•0 citations

Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz

Xiao‐Hui Ni, Lingxiao Li, Yan-Qi Song +3 more

Hadfield et al. proposed a novel Quantum Alternating Operator Ansatz algorithm (QAOA+), and this algorithm has wide applications in solving constrained combinatorial optimization problems (CCOPs) because of the advantages of QAOA+ ansatz in constructing a feasible solution space. In this paper, we propose a Progressive Quantum Algorithm (PQA) with QAOA+ ansatz to solve the Maximum Independent Set (MIS) problem using fewer qubits. The core idea of PQA is to construct a subgraph that is likely to contain the MIS solution of the target graph and then solve the MIS problem on this subgraph to obtain an approximate solution. To construct such a subgraph, PQA starts with a small-scale initial subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results demonstrate that to achieve an approximation ratio of 0.95, PQA requires only $5.565\%$ ($2.170\%$) of the qubits and $17.59\%$ ($6.430\%$) of the runtime compared with directly solving the original problem using QAOA+ on Erdős-Rényi (3-regular) graphs, highlighting the efficiency of PQA.

arXiv:2405.04303•May 7, 2024•0 citations

Progressive quantum algorithm for maximum independent set with quantum alternating operator ansatz

Xiao‐Hui Ni, Ling-Xiao 凌霄 Li 李, Yanqi Song +3 more

Abstract The quantum alternating operator ansatz algorithm (QAOA+) is widely used for constrained combinatorial optimization problems (CCOPs) due to its ability to construct feasible solution spaces. In this paper, we propose a progressive quantum algorithm (PQA) to reduce qubit requirements for QAOA+ in solving the maximum independent set (MIS) problem. PQA iteratively constructs a subgraph likely to include the MIS solution of the original graph and solves the problem on it to approximate the global solution. Specifically, PQA starts with a small-scale subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph using QAOA+. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results show that PQA achieves an approximation ratio of 0.95 using only 5.57% (2.17%) of the qubits and 17.59% (6.43%) of the runtime compared with directly solving the original problem with QAOA+ on Erdös–Rényi (3-regular) graphs, highlighting the efficiency and scalability of PQA.

Chinese Physics B•May 28, 2025•1 citation

A scalable quantum-enhanced greedy algorithm for maximum independent set problems

Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi +2 more

We investigate a hybrid quantum-classical algorithm for solving the Maximum Independent Set (MIS) problem on regular graphs, combining the Quantum Approximate Optimization Algorithm (QAOA) with a minimal degree classical greedy algorithm. The method leverages pre-computed QAOA angles, derived from depth-$p$ QAOA circuits on regular trees, to compute local expectation values and inform sequential greedy decisions that progressively build an independent set. This hybrid approach maintains shallow quantum circuit and avoids instance-specific parameter training, making it well-suited for implementation on current quantum hardware: we have implemented the algorithm on a 20 qubit IQM superconducting device to find independent sets in graphs with thousands of nodes. We perform tensor network simulations to evaluate the performance of the algorithm beyond the reach of current quantum hardware and compare to established classical heuristics. Our results show that even at low depth ($p=4$), the quantum-enhanced greedy method significantly outperforms purely classical greedy baselines as well as more sophisticated approximation algorithms. The modular structure of the algorithm and relatively low quantum resource requirements make it a compelling candidate for scalable, hybrid optimization in the NISQ era and beyond.

quant-pharXiv:2601.21923•Jan 30, 2026•0 citations

The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover

Jeremy Cook, Stephan Eidenbenz, Andreas Bärtschi

The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints. In this paper, we study Maximum k-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two XY-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially in$p$(the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.

arXiv:1910.13483•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•73 citations

From Maximum Cut to Maximum Independent Set

Chuixiong Wu, Jianan Wang, Fen Zuo

The Maximum Cut (Max-Cut) problem could be naturally expressed either in a Quadratic Unconstrained Binary Optimization (QUBO) formulation, or as an Ising model. It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. Therefore, it would be natural to attack MIS with various Max-Cut/Ising solvers. It turns out that this strategy greatly improves the approximation for the independence number of random Erdős-Rényi graphs. It also exhibits perfect performance on a benchmark arising from coding theory. These results pave the way for further development of approximate quantum algorithms on MIS, and specifically on the corresponding coding problems.

arXiv:2408.06758•Aug 13, 2024•1 citation
The maximum-independent set (MIS) problem of graph theory using the quantum alternating operator ansatz is studied. We perform simulations on the Rigetti Forest simulator for the square ring, [Formula: see text], and [Formula: see text] graphs and analyze the dependence of the algorithm on the depth of the circuit and initial states. The probability distribution of observation of the feasible states representing maximum-independent sets is observed to be asymmetric for the MIS problem, which is unlike the Max-Cut problem where the probability distribution of feasible states is symmetric. For asymmetric graphs, it is shown that the algorithm clearly favors the independent set with the larger number of elements even for finite circuit depth. We also compare the approximation ratios for the algorithm when we choose different initial states for the square ring graph and show that it is dependent on the choice of the initial state.
Hadfield et al. proposed a novel Quantum Alternating Operator Ansatz algorithm (QAOA+), and this algorithm has wide applications in solving constrained combinatorial optimization problems (CCOPs) because of the advantages of QAOA+ ansatz in constructing a feasible solution space. In this paper, we propose a Progressive Quantum Algorithm (PQA) with QAOA+ ansatz to solve the Maximum Independent Set (MIS) problem using fewer qubits. The core idea of PQA is to construct a subgraph that is likely to contain the MIS solution of the target graph and then solve the MIS problem on this subgraph to obtain an approximate solution. To construct such a subgraph, PQA starts with a small-scale initial subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results demonstrate that to achieve an approximation ratio of 0.95, PQA requires only 5.565%5.565\%5.565% (2.170%2.170\%2.170%) of the qubits and 17.59%17.59\%17.59% (6.430%6.430\%6.430%) of the runtime compared with directly solving the original problem using QAOA+ on Erdős-Rényi (3-regular) graphs, highlighting the efficiency of PQA.
Abstract The quantum alternating operator ansatz algorithm (QAOA+) is widely used for constrained combinatorial optimization problems (CCOPs) due to its ability to construct feasible solution spaces. In this paper, we propose a progressive quantum algorithm (PQA) to reduce qubit requirements for QAOA+ in solving the maximum independent set (MIS) problem. PQA iteratively constructs a subgraph likely to include the MIS solution of the original graph and solves the problem on it to approximate the global solution. Specifically, PQA starts with a small-scale subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph using QAOA+. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results show that PQA achieves an approximation ratio of 0.95 using only 5.57% (2.17%) of the qubits and 17.59% (6.43%) of the runtime compared with directly solving the original problem with QAOA+ on Erdös–Rényi (3-regular) graphs, highlighting the efficiency and scalability of PQA.
We investigate a hybrid quantum-classical algorithm for solving the Maximum Independent Set (MIS) problem on regular graphs, combining the Quantum Approximate Optimization Algorithm (QAOA) with a minimal degree classical greedy algorithm. The method leverages pre-computed QAOA angles, derived from depth-ppp QAOA circuits on regular trees, to compute local expectation values and inform sequential greedy decisions that progressively build an independent set. This hybrid approach maintains shallow quantum circuit and avoids instance-specific parameter training, making it well-suited for implementation on current quantum hardware: we have implemented the algorithm on a 20 qubit IQM superconducting device to find independent sets in graphs with thousands of nodes. We perform tensor network simulations to evaluate the performance of the algorithm beyond the reach of current quantum hardware and compare to established classical heuristics. Our results show that even at low depth (p=4p=4p=4), the quantum-enhanced greedy method significantly outperforms purely classical greedy baselines as well as more sophisticated approximation algorithms. The modular structure of the algorithm and relatively low quantum resource requirements make it a compelling candidate for scalable, hybrid optimization in the NISQ era and beyond.
The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints. In this paper, we study Maximum k-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two XY-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially inppp(the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.
The Maximum Cut (Max-Cut) problem could be naturally expressed either in a Quadratic Unconstrained Binary Optimization (QUBO) formulation, or as an Ising model. It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. Therefore, it would be natural to attack MIS with various Max-Cut/Ising solvers. It turns out that this strategy greatly improves the approximation for the independence number of random Erdős-Rényi graphs. It also exhibits perfect performance on a benchmark arising from coding theory. These results pave the way for further development of approximate quantum algorithms on MIS, and specifically on the corresponding coding problems.