Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.11633 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909777331748864 |
|---|---|
| author | Fujiwara, Shintaro Ishikawa, Naoki |
| author_facet | Fujiwara, Shintaro Ishikawa, Naoki |
| contents | This paper presents a novel approach to Grover adaptive search (GAS) for a combinatorial optimization problem whose objective function involves spin variables. While the GAS algorithm with a conventional design of a quantum dictionary subroutine handles a problem associated with an objective function with binary variables $\{0,1\}$, we reformulate the problem using spin variables $\{+1,-1\}$ to simplify the algorithm. Specifically, we introduce a novel quantum dictionary subroutine that is designed for this spin-based formulation. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit. We theoretically demonstrate that, for certain problems, our proposed approach can reduce the gate complexity from an exponential order to a polynomial order, compared to the conventional binary-based approach. This improvement has the potential to enhance the scalability and efficiency of GAS, particularly in larger quantum computations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_11633 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Grover Adaptive Search with Spin Variables Fujiwara, Shintaro Ishikawa, Naoki Quantum Physics Signal Processing This paper presents a novel approach to Grover adaptive search (GAS) for a combinatorial optimization problem whose objective function involves spin variables. While the GAS algorithm with a conventional design of a quantum dictionary subroutine handles a problem associated with an objective function with binary variables $\{0,1\}$, we reformulate the problem using spin variables $\{+1,-1\}$ to simplify the algorithm. Specifically, we introduce a novel quantum dictionary subroutine that is designed for this spin-based formulation. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit. We theoretically demonstrate that, for certain problems, our proposed approach can reduce the gate complexity from an exponential order to a polynomial order, compared to the conventional binary-based approach. This improvement has the potential to enhance the scalability and efficiency of GAS, particularly in larger quantum computations. |
| title | Grover Adaptive Search with Spin Variables |
| topic | Quantum Physics Signal Processing |
| url | https://arxiv.org/abs/2410.11633 |