1. Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations
- Author
-
Yuki Sano, Kosuke Mitarai, Naoki Yamamoto, and Naoki Ishikawa
- Subjects
Graph coloring problem (GCP) ,Grover adaptive search (GAS) ,higher order unconstrained binary optimization (HUBO) ,quadratic unconstrained binary optimization (QUBO) ,traveling salesman problem (TSP) ,Atomic physics. Constitution and properties of matter ,QC170-197 ,Materials of engineering and construction. Mechanics of materials ,TA401-492 - Abstract
Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. In this article, 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 reducing both the search space size and the number of quantum gates. Our strategies are also beneficial for general combinatorial optimization problems using one-hot encoding.
- Published
- 2024
- Full Text
- View/download PDF