Spatial search on a two-dimensional lattice with long-range interactions
| Autor: | Tomo Osada, Kae Nemoto, Kaoru Sanaka, William J. Munro |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Physical Review A. 97 |
| ISSN: | 2469-9934 2469-9926 |
| DOI: | 10.1103/physreva.97.062319 |
| Popis: | Quantum-walk-based algorithms that search a marked location among $N$ locations on a $d$-dimensional lattice succeeds in time $O(\sqrt{N})$ for $dg2$, while this is not found to be possible when $d=2$. In this paper, we consider a spatial search algorithm using continuous-time quantum walk on a two-dimensional square lattice with the existence of additional long-range edges. We examined such a search on a probabilistic graph model where an edge connecting non-nearest-neighbor lattice points $i$ and $j$ apart by a distance $|i\ensuremath{-}j|$ is added by probability ${p}_{ij}={|i\ensuremath{-}j|}^{\ensuremath{-}\ensuremath{\alpha}}\phantom{\rule{1em}{0ex}}(\ensuremath{\alpha}\ensuremath{\ge}0)$. Through numerical analysis, we found that the search succeeds in time $O(\sqrt{N})$ when $\ensuremath{\alpha}\ensuremath{\le}{\ensuremath{\alpha}}_{c}=2.4\ifmmode\pm\else\textpm\fi{}0.1$. For $\ensuremath{\alpha}g2$, the expectation value of the additional long-range edges on each node scales as a constant when $N\ensuremath{\rightarrow}\ensuremath{\infty}$, which means that search time of $O(\sqrt{N})$ is achieved on a graph with average degree scaling as a constant. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|