Fixed-point Grover Adaptive Search for QUBO Problems

We apply and study a Grover-type method for Quadratic Unconstrained Binary Optimization (QUBO) problems. First, we construct a marker oracle for such problems. For an n-dimensional QUBO problem, these oracles have a circuit depth and gate count of \(\mathcal{O}(n^2)\). We also develop a novel Fixed-point Grover Adaptive Search for QUBO Problems, using our oracle design and a hybrid Fixed-point Grover Search of Li et al. This method has better performance guarantees than the Grover Adaptive Search of Gilliam et al.

Preprint is available here.