Rasengan: A Transition Hamiltonian-based Approximation Algorithm for Solving Constrained Binary Optimization Problems

Constrained binary optimization is a representative NP-hard problem in various domains, including engineering, scheduling, and finance.Variational quantum algorithms (VQAs) provide a promising methodology for solving this problem by integrating the power of quantum parallelism and classical optimizer.However, existing methods fail to achieve both high accuracy and low circuit complexity, rendering it impossible to deploy onto current quantum devices.This paper proposes Rasengan, a high-precision and deployable approach that leverages algorithm-hardware codesign for solving constrained optimization problems.Unlike traditional VQAs that shrink the whole space and locate the possible solutions in a superposition state, our key idea is to expand the search space from one feasible solution and precisely identify the optimal solution in a basis state.Specifically, we propose the transition Hamiltonian that exponentially explores the entire feasible solution space with all combinations of homogeneous basis vectors.We then introduce three optimization techniques, which greatly reduce the circuit complexity when implementing the Hamiltonian simulation, including Hamiltonian simplification and pruning, segmented execution, and solution purification.Experiments demonstrate that Rasengan improves the accuracy by 4.12× compared to SOTA QAOA [43] and exhibits 379× improvement on real-world quantum platforms.