Variational Quantum Algorithm‐Preserving Feasible Space for Solving the Uncapacitated Facility Location Problem

Abstract The Quantum Alternating Operator Ansatz (QAOA+) is one of the Variational Quantum Algorithm (VQA) specifically developed to tackle combinatorial optimization problems by exploring the feasible space in search of a target solution. For the Constrained Binary Optimization with Unconstrained Variables Problems (CBO‐UVPs), the mixed operators in the QAOA+ circuit are applied to the constrained variables, while the single‐qubit rotating gates operate on the unconstrained variables. The expressibility of this circuit is limited by the shortage of two‐qubit gates and the parameter sharing in the single‐qubit rotating gates, which consequently impacts the performance of QAOA+ for solving CBO‐UVPs. Therefore, it is crucial to develop a suitable ansatz for CBO‐UVPs. In this paper, the Variational Quantum Algorithm‐Preserving Feasible Space (VQA‐PFS) ansatz is proposed, exemplified by the Uncapacitated Facility Location Problem (UFLP), that applies mixed operators on constrained variables while employing Hardware‐Efficient Ansatz (HEA) on unconstrained variables. The numerical results demonstrate that VQA‐PFS significantly enhances the probability of success and exhibits faster convergence than QAOA+, Quantum Approximation Optimization Algorithm (QAOA), and HEA. Furthermore, VQA‐PFS reduces the circuit depth dramatically compared to QAOA+ and QAOA. The algorithm is general and instructive in tackling CBO‐UVPs.