  We study a Grover-type method for Quadratic Binary Optimization problems. In
the unconstrained (QUBO) case, for an $n$-dimensional problem with $m$ nonzero
terms, we construct a marker oracle for such problems with a tuneable
parameter, $\Lambda \in \left[ 1, m \right] \cap \mathbb{Z}$. At $d \in
\mathbb{Z}_+$ precision, the oracle uses $O \left( n + \Lambda d \right)$
qubits, has total depth $O \left( \tfrac{m}{\Lambda} \log_2 \left( n \right) +
\log_2 \left( d \right) \right)$, and non-Clifford depth of $O \left(
\tfrac{m}{\Lambda} \right)$. Moreover, each qubit required to be connected to
at most $O \left( \log_2 \left( \Lambda + d \right) \right)$ other qubits. In
the case of a maximal graph cuts, as $d = 2 \log_2 \left( n \right)$ always
suffices, the depth of the marker oracle can be made as shallow as $O \left(
\log_2 \left( n \right) \right)$. For all values of $\Lambda$, the non-Clifford
gate count of these oracles is strictly lower (by a factor of $\sim 2$) than
previous constructions.
  We then introduce a novel \emph{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 previous Grover
Adaptive Search methods. Finally, we give a heuristic argument that, with high
probability and in $O \left( \tfrac{\log_2 \left( n \right)}{\sqrt{\epsilon}}
\right)$ time, this adaptive method finds a configuration that is among the
best $\epsilon 2^n$ ones.
