Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems

Abstract

The quantum approximate optimization algorithm (QAOA) is among the 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 form a general class of combinatorial optimization problems involving multivariable interactions. We present a comprehensive numerical study demonstrating that GM-QAOA, unlike XM-QAOA, exhibits monotonic improvement in performance with circuit depth and achieves superior results for HUBO problems within a layerwise optimization framework. 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 parametrized version of GM-QAOA nearly matches the performance of the version optimized using the layerwise approach while being significantly less demanding, making it a highly effective approach for complex optimization tasks. These findings highlight the potential of GM-QAOA and provide a practical pathway for its implementation on current quantum hardware.

14 pages, 6 figures