Lewis, D; Benhemou, A; Feinstein, N; Banchi, L; Bose, S; (2021) Optimal Quantum Spatial Search with One-Dimensional Long-Range Interactions. Physical Review Letters , 126 (24) , Article 240502. 10.1103/PhysRevLett.126.240502.

Preview

Text PhysRevLett.126.240502.pdf - Published Version Download (413kB) | Preview

Abstract

Continuous-time quantum walks can be used to solve the spatial search problem, which is an essential component for many quantum algorithms that run quadratically faster than their classical counterpart, in O(sqrt[n]) time for n entries. However, the capability of models found in nature is largely unexplored-e.g., in one dimension only nearest-neighbor Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with O(sqrt[n]) run time and high fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as 1/r^{α} with distance r. In particular, near unit fidelity is achieved for α≈1 and, in the limit n→∞, we find a continuous transition from a region where optimal spatial search does exist (α<1.5) to where it does not (α>1.5). Numerically, we show that spatial search is robust to dephasing noise and that, for reasonable chain lengths, α≲1.2 should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.

Download activity - last month

Export as JSONXMLCSV

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item