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 time for 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 run time and high fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as with distance . In particular, near unit fidelity is achieved for and, in the limit , we find a continuous transition from a region where optimal spatial search does exist () to where it does not (). Numerically, we show that spatial search is robust to dephasing noise and that, for reasonable chain lengths, should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.
- Received 29 October 2020
- Revised 9 April 2021
- Accepted 7 May 2021
DOI:https://doi.org/10.1103/PhysRevLett.126.240502
© 2021 American Physical Society