The Grover Adaptive Search Algorithm as a Solver: High-Order Unconstrained Binary Optimization Problems
Le Manh Quan Tran · Aaltodoc (Aalto University) · 2026
High-order binary optimization (HUBO) formulation can represent many real world problems. This mathematical approach is particularly relevant within the quantum computation domain because quantum hardware allows to directly map and solve these problems. The thesis explores the implementation of Grover Adaptive Search (GAS) by varying the different free parameters to evaluate the quality of the solution and the success rate of the algorithm, along with a possible optimization procedure. In particular, GAS is an algorithm that is compliant with HUBO and theoretically offer a quadratic speed up over classical computation. This thesis implements a quantum circuit for GAS algorithm to solve a 4-city traveling salesman problem along with two strategies to reduce the gate counts. The results include the output quality of the value of the objective function and the success rate of reaching the true minimum of 7, where the optimal configuration achieves an average value of 9.4 and a success rate of 36%. This configuration also maintains a 7% lower average value and a 10% higher success rate compared to randomly generated parameters.