Quantum search by continuous-time quantum walk on t-designs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913776929865728 |
|---|---|
| author | Lugão, Pedro H. G. Portugal, Renato |
| author_facet | Lugão, Pedro H. G. Portugal, Renato |
| contents | This work examines the time complexity of quantum search algorithms on combinatorial $t$-designs with multiple marked elements using the continuous-time quantum walk. Through a detailed exploration of $t$-designs and their incidence matrices, we identify a subset of bipartite graphs that are conducive to success compared to random-walk-based search algorithms. These graphs have adjacency matrices with eigenvalues and eigenvectors that can be determined algebraically and are also suitable for analysis in the multiple-marked vertex scenario. We show that the continuous-time quantum walk on certain symmetric $t$-designs achieves an optimal running time of $O(\sqrt{n})$, where $n$ is the number of points and blocks, even when accounting for an arbitrary number of marked elements. Upon examining two primary configurations of marked elements distributions, we observe that the success probability is consistently $o(1)$, but it approaches 1 asymptotically in certain scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_14141 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Quantum search by continuous-time quantum walk on t-designs Lugão, Pedro H. G. Portugal, Renato Quantum Physics Computational Complexity Combinatorics This work examines the time complexity of quantum search algorithms on combinatorial $t$-designs with multiple marked elements using the continuous-time quantum walk. Through a detailed exploration of $t$-designs and their incidence matrices, we identify a subset of bipartite graphs that are conducive to success compared to random-walk-based search algorithms. These graphs have adjacency matrices with eigenvalues and eigenvectors that can be determined algebraically and are also suitable for analysis in the multiple-marked vertex scenario. We show that the continuous-time quantum walk on certain symmetric $t$-designs achieves an optimal running time of $O(\sqrt{n})$, where $n$ is the number of points and blocks, even when accounting for an arbitrary number of marked elements. Upon examining two primary configurations of marked elements distributions, we observe that the success probability is consistently $o(1)$, but it approaches 1 asymptotically in certain scenarios. |
| title | Quantum search by continuous-time quantum walk on t-designs |
| topic | Quantum Physics Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2310.14141 |