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

Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem

Shasha Wang, Hailing Liu, Su‐Juan Qin, Gao, Fei, Qiaoyan Wen

Published Nov 28, 2022• 0 citations
arXivHTMLPDF

Abstract

The Quantum Alternating Operator Ansatz (QAOA+) is an extension of the Quantum Approximate Optimization Algorithm (QAOA), where the search space is smaller in solving constrained combinatorial optimization problems. However, QAOA+ requires a trivial feasible solution as the initial state, so it cannot be used for problems that are difficult to find a trivial feasible solution. For simplicity, we call them as Non-Trivial-Feasible-Solution Problems (NTFSP). In this paper, we take the Minimum Exact Cover (MEC) problem as an example, studying how to apply QAOA+ to NTFSP. As we know, exact covering (EC) is the feasible space of MEC problem, which has no trivial solutions. To overcome the above problem, the EC problem is divided into two steps to solve. First, disjoint sets are obtained, which is equivalent to solving independent sets. Second, on this basis, the sets covering all elements (i.e., EC) are solved. In other words, we transform MEC into a multi-objective constrained optimization problem, where feasible space consists of independent sets that are easy to find. Finally, we also verify the feasibility of the algorithm from numerical experiments. Our method provides a feasible way for applying QAOA+ to NTFSP, and is expected to expand its application significantly.

DOI
10.48550/arxiv.2211.15266

Related papers

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.

arXiv:2405.04303•Chinese Physics B•May 28, 2025•9 citations

An Adaptive Mixer Allocation Strategy for the Quantum Alternating Operator Ansatz

Xiao‐Hui Ni, Yusen Wu, Bin‐Bin Cai +3 more

ABSTRACT Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA‐QAOA+. Unlike QAOA+, AMA‐QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA‐QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA‐QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by on Erdős–Rényi random graphs and on 3‐regular graphs. Moreover, AMA‐QAOA+ significantly reduces the CNOT gate consumption, requiring only and of the CNOT gates used by QAOA+ on Erdős–Rényi and 3‐regular random graphs, respectively. These results demonstrate that AMA‐QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource‐efficient quantum circuits.

arXiv:2412.19621•Advanced Quantum Technologies•Nov 23, 2025•5 citations

Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz

Brayden Goldstein-Gelb, Phillip C. Lotshaw

We present a quantum alternating operator ansatz (QAOA + ) that solves a class of linearly constrained optimization problems by evolving a quantum state within a Hilbert subspace of feasible problem solutions. Our main focus is on a class of problems with a linear constraint containing sequential integer coefficients. For problems in this class, we devise QAOA + circuits that provably converge to the optimal solution as the number of circuit layers increases, generalizing previous guarantees for solving unconstrained problems or problems with symmetric constraints. Our approach includes asymmetric “mixing” Hamiltonians that drive transitions between feasible states, as well as a method to incorporate an arbitrary known feasible solution as the initial state, each of which can be applied beyond the specific linear constraints considered here. This analysis extends QAOA + performance guarantees to a more general set of linearly-constrained problems and provides tools for future generalizations.

arXiv:2409.18829•ACM Transactions on Quantum Computing•Sep 8, 2026•5 citations

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

XY vs X mixer in Quantum Alternating Operator Ansatz for optimization problems with constraints

Zhihui Wang, Nicholas C. Rubin, Eleanor Gilbert Rieffel

Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.

Bulletin of the American Physical Society•Mar 8, 2018•0 citations

The Art of Avoiding Constraints: A Penalty-free Approach to Constrained Combinatorial Optimization with QAOA

Prashanti Priya Angara, Danylo Lykov, Ulrike Stege +2 more

The quantum approximate optimization algorithm (QAOA) is designed to determine optimum and near optimum solutions of quadratic (and higher order) unconstrained binary optimization (QUBO or HUBO) problems, which in turn accurately model unconstrained combinatorial optimization problems. While the solution space of an unconstrained combinatorial optimization problem consists of all possible combinations of the objective function's decision variables, for a constrained combinatorial optimization problem, the solution space consists only of solutions that satisfy the problem constraints. While solving such a QUBO problem optimally results in an optimal solution to the underlying constrained problem, setting the right penalty parameters is crucial. Moreover, finding suitable penalties that ensure near-optimal solutions is also challenging. In this article, we introduce our innovative profit-relaxation framework to solve constrained combinatorial optimization problems. Our effective hybrid approach transforms a selected constrained combinatorial optimization problem into an unconstrained profit problem, such that the solution spaces of the two problems are interrelated with respect to their solution qualities. This allows us to determine optimal and near-optimal solutions for the constrained problem. We use three NP-hard problems -- Minimum Vertex Cover, Maximum Independent Set, and Maximum Clique -- to demonstrate the feasibility and effectiveness of our approach. We conducted a detailed performance evaluation of our profit-relaxation framework on two different platforms: Xanadu PennyLane and Argonne QTensor Quantum Circuit Simulator.

arXiv:2503.10077•IEEE Transactions on Quantum Engineering•Jan 1, 2026•7 citations
The Quantum Alternating Operator Ansatz (QAOA+) is an extension of the Quantum Approximate Optimization Algorithm (QAOA), where the search space is smaller in solving constrained combinatorial optimization problems. However, QAOA+ requires a trivial feasible solution as the initial state, so it cannot be used for problems that are difficult to find a trivial feasible solution. For simplicity, we call them as Non-Trivial-Feasible-Solution Problems (NTFSP). In this paper, we take the Minimum Exact Cover (MEC) problem as an example, studying how to apply QAOA+ to NTFSP. As we know, exact covering (EC) is the feasible space of MEC problem, which has no trivial solutions. To overcome the above problem, the EC problem is divided into two steps to solve. First, disjoint sets are obtained, which is equivalent to solving independent sets. Second, on this basis, the sets covering all elements (i.e., EC) are solved. In other words, we transform MEC into a multi-objective constrained optimization problem, where feasible space consists of independent sets that are easy to find. Finally, we also verify the feasibility of the algorithm from numerical experiments. Our method provides a feasible way for applying QAOA+ to NTFSP, and is expected to expand its application significantly.
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.
ABSTRACT Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA‐QAOA+. Unlike QAOA+, AMA‐QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA‐QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA‐QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by on Erdős–Rényi random graphs and on 3‐regular graphs. Moreover, AMA‐QAOA+ significantly reduces the CNOT gate consumption, requiring only and of the CNOT gates used by QAOA+ on Erdős–Rényi and 3‐regular random graphs, respectively. These results demonstrate that AMA‐QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource‐efficient quantum circuits.
We present a quantum alternating operator ansatz (QAOA + ) that solves a class of linearly constrained optimization problems by evolving a quantum state within a Hilbert subspace of feasible problem solutions. Our main focus is on a class of problems with a linear constraint containing sequential integer coefficients. For problems in this class, we devise QAOA + circuits that provably converge to the optimal solution as the number of circuit layers increases, generalizing previous guarantees for solving unconstrained problems or problems with symmetric constraints. Our approach includes asymmetric “mixing” Hamiltonians that drive transitions between feasible states, as well as a method to incorporate an arbitrary known feasible solution as the initial state, each of which can be applied beyond the specific linear constraints considered here. This analysis extends QAOA + performance guarantees to a more general set of linearly-constrained problems and provides tools for future generalizations.
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 Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.
The quantum approximate optimization algorithm (QAOA) is designed to determine optimum and near optimum solutions of quadratic (and higher order) unconstrained binary optimization (QUBO or HUBO) problems, which in turn accurately model unconstrained combinatorial optimization problems. While the solution space of an unconstrained combinatorial optimization problem consists of all possible combinations of the objective function's decision variables, for a constrained combinatorial optimization problem, the solution space consists only of solutions that satisfy the problem constraints. While solving such a QUBO problem optimally results in an optimal solution to the underlying constrained problem, setting the right penalty parameters is crucial. Moreover, finding suitable penalties that ensure near-optimal solutions is also challenging. In this article, we introduce our innovative profit-relaxation framework to solve constrained combinatorial optimization problems. Our effective hybrid approach transforms a selected constrained combinatorial optimization problem into an unconstrained profit problem, such that the solution spaces of the two problems are interrelated with respect to their solution qualities. This allows us to determine optimal and near-optimal solutions for the constrained problem. We use three NP-hard problems -- Minimum Vertex Cover, Maximum Independent Set, and Maximum Clique -- to demonstrate the feasibility and effectiveness of our approach. We conducted a detailed performance evaluation of our profit-relaxation framework on two different platforms: Xanadu PennyLane and Argonne QTensor Quantum Circuit Simulator.