  Grover adaptive search (GAS) is a quantum exhaustive search algorithm
designed to solve binary optimization problems. In this paper, we propose
higher-order binary formulations that can simultaneously reduce the numbers of
qubits and gates required for GAS. Specifically, we consider two novel
strategies: one that reduces the number of gates through polynomial
factorization, and the other that halves the order of the objective function,
subsequently decreasing circuit runtime and implementation cost. Our analysis
demonstrates that the proposed higher-order formulations improve the
convergence performance of GAS by both reducing the search space size and the
number of quantum gates. Our strategies are also beneficial for general
combinatorial optimization problems using one-hot encoding.
