Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations
| Autor: | Yuki Sano, Kosuke Mitarai, Naoki Yamamoto, Naoki Ishikawa |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2024 |
| Předmět: |
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 |
| Zdroj: | IEEE Transactions on Quantum Engineering, Vol 5, Pp 1-12 (2024) |
| Druh dokumentu: | article |
| ISSN: | 2689-1808 |
| DOI: | 10.1109/TQE.2024.3393437 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|