Resource-Efficient Grover-Mixer QAOA for Higher-Order Optimization via Analytical Parameter Pre-optimization

Higher-order unconstrained binary optimization (HUBO) problems are crucial for complex machine learning and logistics but remain challenging for near-term quantum devices due to intricate multi-variable interactions. While standard transverse-field QAOA (XM-QAOA) struggles with these complex landscapes, the Grover-mixer variant (GM-QAOA) offers a compelling global search alternative.

We present a comprehensive numerical study on random hypergraphs and spin-glass models, demonstrating that unlike XM-QAOA, which rapidly plateaus at shallow depths, GM-QAOA exhibits monotonic performance improvement with increasing circuit depth. Crucially, GM-QAOA shows remarkable resilience to the increased complexity of higher-order interactions, significantly outperforming XM-QAOA beyond specific critical depths.

To mitigate the high computational overhead of variational optimization, we develop an analytical framework modeling GM-QAOA dynamics. By assuming a Gaussian energy distribution and applying extreme value theory to estimate the ground-state energy, we derive a classical pre-optimization strategy for the algorithm's variational parameters. This resource-efficient approach, GM-QAOA(a), achieves approximation ratios nearly matching fully optimized layerwise GM-QAOA while drastically reducing the number of required quantum circuit evaluations.

Furthermore, we show that the performance of this analytically pre-optimized variant actually improves as the locality of the cost Hamiltonian increases. Our findings establish a practical, scalable pathway for implementing global-mixer quantum algorithms on current hardware, offering a robust solution for complex, high-order combinatorial optimization tasks without the prohibitive costs of iterative hybrid training, making it highly suitable for near-term quantum processors.