Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.01572 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929339882274816 |
|---|---|
| author | Sano, Yuki Mitarai, Kosuke Yamamoto, Naoki Ishikawa, Naoki |
| author_facet | Sano, Yuki Mitarai, Kosuke Yamamoto, Naoki Ishikawa, Naoki |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_01572 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations Sano, Yuki Mitarai, Kosuke Yamamoto, Naoki Ishikawa, Naoki Quantum Physics 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. |
| title | Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2308.01572 |