Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations
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 stra...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Transactions on Quantum Engineering |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10508492/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832586860833013760 |
|---|---|
| author | Yuki Sano Kosuke Mitarai Naoki Yamamoto Naoki Ishikawa |
| author_facet | Yuki Sano Kosuke Mitarai Naoki Yamamoto Naoki Ishikawa |
| author_sort | Yuki Sano |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-65632f20c39a487e8421403c4ec56e70 |
| institution | Kabale University |
| issn | 2689-1808 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Transactions on Quantum Engineering |
| spelling | doaj-art-65632f20c39a487e8421403c4ec56e702025-01-25T00:03:34ZengIEEEIEEE Transactions on Quantum Engineering2689-18082024-01-01511210.1109/TQE.2024.339343710508492Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order FormulationsYuki Sano0https://orcid.org/0009-0009-8168-3440Kosuke Mitarai1https://orcid.org/0000-0002-9056-316XNaoki Yamamoto2https://orcid.org/0000-0002-8497-4608Naoki Ishikawa3https://orcid.org/0000-0001-8978-4849Faculty of Engineering, Yokohama National University, Yokohama, JapanGraduate School of Engineering Science, Osaka University, Toyonaka, JapanDepartment of Applied Physics and Physico-Informatics, Keio University, Kohoku, JapanFaculty of Engineering, Yokohama National University, Yokohama, JapanGrover 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.https://ieeexplore.ieee.org/document/10508492/Graph coloring problem (GCP)Grover adaptive search (GAS)higher order unconstrained binary optimization (HUBO)quadratic unconstrained binary optimization (QUBO)traveling salesman problem (TSP) |
| spellingShingle | Yuki Sano Kosuke Mitarai Naoki Yamamoto Naoki Ishikawa Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations IEEE Transactions on Quantum Engineering Graph coloring problem (GCP) Grover adaptive search (GAS) higher order unconstrained binary optimization (HUBO) quadratic unconstrained binary optimization (QUBO) traveling salesman problem (TSP) |
| title | Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations |
| title_full | Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations |
| title_fullStr | Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations |
| title_full_unstemmed | Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations |
| title_short | Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations |
| title_sort | accelerating grover adaptive search qubit and gate count reduction strategies with higher order formulations |
| topic | Graph coloring problem (GCP) Grover adaptive search (GAS) higher order unconstrained binary optimization (HUBO) quadratic unconstrained binary optimization (QUBO) traveling salesman problem (TSP) |
| url | https://ieeexplore.ieee.org/document/10508492/ |
| work_keys_str_mv | AT yukisano acceleratinggroveradaptivesearchqubitandgatecountreductionstrategieswithhigherorderformulations AT kosukemitarai acceleratinggroveradaptivesearchqubitandgatecountreductionstrategieswithhigherorderformulations AT naokiyamamoto acceleratinggroveradaptivesearchqubitandgatecountreductionstrategieswithhigherorderformulations AT naokiishikawa acceleratinggroveradaptivesearchqubitandgatecountreductionstrategieswithhigherorderformulations |