Comparing QAOA Implementations of Penalty Function and XY-Mixer for Constrained Optimization: Application to the Circular Maximum Diversity Problem on IBM Quantum Computer

We compare two different implementations of Quantum Alternating Operator Ansatz (QAOA) for constrained optimization: the penalty function and the XY-mixer. The penalty function method converts a constrained problem to an unconstrained problem by penalizing constraint violations, whereas the XY-mixer uses two-qubit operators to maintain feasibility. We use a special case of the maximum diversity problem (MDP) to demonstrate the effectiveness of the XY-mixer. The MDP aims at selecting a subset of elements from a larger set to maximize diversity between the selected elements. The special case deals with instances in which elements are arranged in a circular structure. The circular MDP instances are challenging to solve using classical methods due to solution space symmetry but are well-suited for the topology of IBM quantum devices. We introduce a grouping and an approximation mechanism facilitating XY-mixer implementation on IBM quantum computers. Experiments with different-sized instances show that the XY-mixer generates more and better feasible solutions than the penalty function approach and increases the probability of finding good solutions.