Lewis Dylan, Benhemou Asmae, Feinstein Natasha, Banchi Leonardo, Bose Sougato
Department of Physics and Astronomy, University College London, London WC1E 6BT, United Kingdom.
Department of Physics and Astronomy, University of Florence, via G. Sansone 1, I-50019 Sesto Fiorentino (Florence), Italy.
Phys Rev Lett. 2021 Jun 18;126(24):240502. doi: 10.1103/PhysRevLett.126.240502.
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.
