Applying Grover-mixer Quantum Alternating Ansatz Algorithm to Higher-order Quadratic Unconstrained Optimization Problems

Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is among leading candidates for achieving quantum advantage on near-term processors. While typically implemented with a transverse-field mixer (XM-QAOA), the Grover-mixer variant (GM-QAOA) offers a compelling alternative due to its global search capabilities. This work investigates the application of GM-QAOA to Higher-Order Unconstrained Binary Optimization (HUBO) problems, also known as Polynomial Unconstrained Binary Optimization (PUBO), which constitute a generalized class of combinatorial optimization tasks characterized by intrinsically multi-variable interactions. We present a comprehensive numerical study demonstrating that GM-QAOA, unlike XM-QAOA, exhibits monotonic performance improvement with circuit depth and achieves superior results for HUBO problems. An important component of our approach is an analytical framework for modeling GM-QAOA dynamics, which enables a classical approximation of the optimal parameters and helps reduce the optimization overhead. Our resource-efficient parameterized GM-QAOA nearly matches the performance of the fully optimized algorithm while being far less demanding, establishing it as a highly effective approach for complex optimization tasks. These findings highlight GM-QAOA's potential and provide a practical pathway for its implementation on current quantum hardware.