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

References in corpus (24)

• Quantum Machine Learning
• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum computational chemistry
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Theory of variational quantum simulation
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Variational algorithms for linear algebra
• Reachability Deficits in Quantum Approximate Optimization
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Scalable quantum computing with qudits on a graph
• Scalable algorithm simplification using quantum AND logic
• Decomposing the generalized Toffoli gate with qutrits
• Efficient realization of quantum algorithms with qudits
• Qudits for decomposing multiqubit gates and realizing quantum algorithms
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Scalable improvement of the generalized Toffoli gate realization using trapped-ion-based qutrits
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Transforming optimization problems into a QUBO form: A tutorial
• Grover's search meets Ising models: a quantum algorithm for finding low-energy states
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios