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

Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem

Shasha Wang, Hailing Liu, Yan-Qi Song, Fei Gao, Su‐Juan Qin, Qiaoyan Wen

Published Jan 1, 2023• 0 citations
Publisher
DOI
10.2139/ssrn.4458977

Related papers

Quantum alternating operator ansatz for solving the minimum exact cover problem

Shasha Wang, Hailing Liu, Yan-Qi Song +3 more

Physica A Statistical Mechanics and its Applications•Jul 22, 2023•14 citations

Performance analysis of the quantum alternating operator ansatz for solving the minimum weighted vertex cover problem

Guanghui Li, Shasha Wang, Xiao‐Hui Ni +4 more

Physics Letters A•May 28, 2025•0 citations

Quantum alternating operator ansatz for solving the minimum dominating set problem on sparse graphs with a specific structure

Guanghui Li, Shasha Wang, Zhao Xiumei +4 more

Quantum Information Processing•Jun 6, 2025•1 citation

Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem

Shasha Wang, Hailing Liu, Su‐Juan Qin +2 more

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.

arXiv:2211.15266•Nov 28, 2022•0 citations

Investigations of the Quantum Alternating Operator Ansatz

Eleanor Gilbert Rieffel, Stuart Hadfield, Zhihui Wang +2 more

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

On the Use of the Quantum Alternating Operator Ansatz in Quantum-Informed Recursive Optimization: A Case Study on the Minimum Vertex Cover

Pablo Ramos-Ruiz, Antonio Miguel Fuentes-Jiménez, José E. Ramos-Ruíz +1 more

In recent years, several quantum algorithms have been proposed for addressing combinatorial optimization problems. Among them, the Quantum Approximate Optimization Algorithm (QAOA) has become a widely used approach. However, reported limitations of QAOA have motivated the development of multiple algorithmic variants, including recursive hybrid methods such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), as well as the Quantum-Informed Recursive Optimization (QIRO) framework. In this work, we integrate the Quantum Alternating Operator Ansatz within the QIRO framework in order to improve its quantum inference stage. Both the original and the enhanced versions of QIRO are applied to the Minimum Vertex Cover problem, an NP-complete problem of practical relevance. Performance is evaluated on a benchmark of Erdös-Rényi graph instances with varying sizes, densities, and random seeds. The results show that the proposed modification leads to a higher number of successfully solved instances across the considered benchmark, indicating that refinements of the variational layer can improve the effectiveness of the QIRO framework.

AppliedMath•Feb 6, 2026•0 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.
In recent years, several quantum algorithms have been proposed for addressing combinatorial optimization problems. Among them, the Quantum Approximate Optimization Algorithm (QAOA) has become a widely used approach. However, reported limitations of QAOA have motivated the development of multiple algorithmic variants, including recursive hybrid methods such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), as well as the Quantum-Informed Recursive Optimization (QIRO) framework. In this work, we integrate the Quantum Alternating Operator Ansatz within the QIRO framework in order to improve its quantum inference stage. Both the original and the enhanced versions of QIRO are applied to the Minimum Vertex Cover problem, an NP-complete problem of practical relevance. Performance is evaluated on a benchmark of Erdös-Rényi graph instances with varying sizes, densities, and random seeds. The results show that the proposed modification leads to a higher number of successfully solved instances across the considered benchmark, indicating that refinements of the variational layer can improve the effectiveness of the QIRO framework.