Quantum Signal Processing Based Grover's Adaptative Search Oracle for High Order Unconstrained Binary Optimization Problems

Grover's Adaptative Search (GAS) algorithm combined with the High Order Binary Optimization (HOBO) oracle proposal is currently the Fault Tolerant Quantum Computer (FTQC)'s main algorithm to solve binary optimization problems. In this paper, we propose a new way to obtain the Grover's oracle needed which is costless in terms of gates and ancilla qubits. This oracle proposal also has zero additional costs linked to decimal numbers of the problem weights and a very small overcost due to high order problems with respect to the other proposals. Nevertheless, it cannot be easily adapted to constrained problems. This new oracle is based on a completely different approach, which uses Quantum Signal Processing (QSP) techniques and amplitude encoding. This method can also be described in the Quantum Singular Value Transformation (QSVT) framework as a variant of eigenstate search algorithms. Our oracle combines the benefits of both the QSVT amplitude encoding of the problem and GAS strategies to seek eigenvalues.