  In this paper we discuss Grover Adaptive Search (GAS) for Constrained
Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic
Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can
provide a quadratic speed-up for combinatorial optimization problems compared
to brute force search. However, this requires the development of efficient
oracles to represent problems and flag states that satisfy certain search
criteria. In general, this can be achieved using quantum arithmetic, however,
this is expensive in terms of Toffoli gates as well as required ancilla qubits,
which can be prohibitive in the near-term. Within this work, we develop a way
to construct efficient oracles to solve CPBO problems using GAS algorithms. We
demonstrate this approach and the potential speed-up for the portfolio
optimization problem, i.e. a QUBO, using simulation and experimental results
obtained on real quantum hardware. However, our approach applies to
higher-degree polynomial objective functions as well as constrained
optimization problems.
