Quantum alternating operator ansatz for solving the minimum exact cover problem

DOI10.1016/J.PHYSA.2023.129089MaRDI QIDQ6095686zbMATH OpenFDO

Authors Shasha Wang, Hailing Liu, Yanqi Song, Fei Gao, Su-Juan Qin, Qiaoyan Wen

Publication date 8 September 2023

Published in Physica A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.15266

zbMATH Keywords

minimum exact covermulti-objective constrained optimization problemquantum alternating operator ansatztrivial feasible solutions

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

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.

Cites work

• A Family of Variable-Metric Methods Derived by Variational Means
• A new approach to variable metric algorithms
• Conditioning of Quasi-Newton Methods for Function Minimization
• Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• Impact of graph structures for QAOA on maxcut
• Max-independent set and the quantum alternating operator ansatz
• On the linear weighted sum method for multi-objective optimization
• Quantum algorithms for anomaly detection using amplitude estimation
• Quantum discriminative canonical correlation analysis
• Quantum mean centering for block-encoding-based quantum algorithm
• Reducibility among combinatorial problems
• The Convergence of a Class of Double-rank Minimization Algorithms 1. General Considerations

Cited in

(4)

• scientific article; zbMATH DE number 6487863 (Why is no real title available?)
• Performance analysis of the quantum alternating operator ansatz for solving the minimum weighted vertex cover problem
• Quantum alternating operator ansatz for solving the minimum dominating set problem on sparse graphs with a specific structure
• Max-Cut linear binary classifier based on quantum approximate optimization algorithm

This page was built for publication: Quantum alternating operator ansatz for solving the minimum exact cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095686)