Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929338832650240 |
|---|---|
| author | Lin, Honghong Shang, Yun |
| author_facet | Lin, Honghong Shang, Yun |
| contents | This paper presents a deterministic search algorithm on complete bipartite graphs. Our algorithm adopts the simple form of alternating iterations of an oracle and a continuous-time quantum walk operator, which is a generalization of Grover's search algorithm. We address the most general case of multiple marked states, so there is a problem of estimating the number of marked states. To this end, we construct a quantum counting algorithm based on the spectrum structure of the search operator. To implement the continuous-time quantum walk operator, we perform Hamiltonian simulation in the quantum circuit model. We achieve simulation in constant time, that is, the complexity of the quantum circuit does not scale with the evolution time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_01640 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk Lin, Honghong Shang, Yun Quantum Physics Data Structures and Algorithms This paper presents a deterministic search algorithm on complete bipartite graphs. Our algorithm adopts the simple form of alternating iterations of an oracle and a continuous-time quantum walk operator, which is a generalization of Grover's search algorithm. We address the most general case of multiple marked states, so there is a problem of estimating the number of marked states. To this end, we construct a quantum counting algorithm based on the spectrum structure of the search operator. To implement the continuous-time quantum walk operator, we perform Hamiltonian simulation in the quantum circuit model. We achieve simulation in constant time, that is, the complexity of the quantum circuit does not scale with the evolution time. |
| title | Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.01640 |