Multimarked Spatial Search by Continuous-Time Quantum Walk
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916540486516736 |
|---|---|
| author | Lugão, Pedro H. G. Portugal, Renato Sabri, Mohamed Tanaka, Hajime |
| author_facet | Lugão, Pedro H. G. Portugal, Renato Sabri, Mohamed Tanaka, Hajime |
| contents | The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix $M$, the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of $M$. We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is $O(\sqrt{N})$ with an asymptotic probability of $1+o(1)$, where $N$ is the number of vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_14384 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Multimarked Spatial Search by Continuous-Time Quantum Walk Lugão, Pedro H. G. Portugal, Renato Sabri, Mohamed Tanaka, Hajime Quantum Physics Computational Complexity The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix $M$, the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of $M$. We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is $O(\sqrt{N})$ with an asymptotic probability of $1+o(1)$, where $N$ is the number of vertices. |
| title | Multimarked Spatial Search by Continuous-Time Quantum Walk |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2203.14384 |