Quantum walk search on a two-dimensional grid with extra edges
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929744293920768 |
|---|---|
| author | Giri, Pulak Ranjan |
| author_facet | Giri, Pulak Ranjan |
| contents | Quantum walk has been successfully used to search for targets on graphs with vertices identified as the elements of a database. This spacial search on a two-dimensional periodic grid takes $\mathcal{O}\left(\sqrt{N\log N}\right)$ oracle consultations to find a target vertex from $N$ number of vertices with $\mathcal{O}(1)$ success probability, while reaching optimal speed of $\mathcal{O}(\sqrt{N})$ on $d \geq 3$ dimensional square lattice. Our numerical analysis based on lackadaisical quantum walks searches $M$ vertices on a 2-dimensional grid with optimal speed of $\mathcal{O}(\sqrt{N/M})$, provided the grid is attached with additional long range edges. Based on the numerical analysis performed with multiple sets of randomly generated targets for a wide range of $N$ and $M$ we suggest that the optimal time complexity of $\mathcal{O}(\sqrt{N/M})$ with constant success probability can be achieved for quantum search on a two-dimensional periodic grid with long-range edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_04016 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum walk search on a two-dimensional grid with extra edges Giri, Pulak Ranjan Quantum Physics Quantum walk has been successfully used to search for targets on graphs with vertices identified as the elements of a database. This spacial search on a two-dimensional periodic grid takes $\mathcal{O}\left(\sqrt{N\log N}\right)$ oracle consultations to find a target vertex from $N$ number of vertices with $\mathcal{O}(1)$ success probability, while reaching optimal speed of $\mathcal{O}(\sqrt{N})$ on $d \geq 3$ dimensional square lattice. Our numerical analysis based on lackadaisical quantum walks searches $M$ vertices on a 2-dimensional grid with optimal speed of $\mathcal{O}(\sqrt{N/M})$, provided the grid is attached with additional long range edges. Based on the numerical analysis performed with multiple sets of randomly generated targets for a wide range of $N$ and $M$ we suggest that the optimal time complexity of $\mathcal{O}(\sqrt{N/M})$ with constant success probability can be achieved for quantum search on a two-dimensional periodic grid with long-range edges. |
| title | Quantum walk search on a two-dimensional grid with extra edges |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2503.04016 |