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.
Type: | Article |
---|---|
Title: | Optimal Quantum Spatial Search with One-Dimensional Long-Range Interactions |
Location: | United States |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1103/PhysRevLett.126.240502 |
Publisher version: | http://dx.doi.org/10.1103/PhysRevLett.126.240502 |
Language: | English |
Additional information: | This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions. |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Physics and Astronomy |
URI: | https://discovery.ucl.ac.uk/id/eprint/10130666 |



1. | ![]() | 6 |
2. | ![]() | 5 |
3. | ![]() | 3 |
4. | ![]() | 2 |
5. | ![]() | 1 |
6. | ![]() | 1 |
7. | ![]() | 1 |
8. | ![]() | 1 |
9. | ![]() | 1 |
Archive Staff Only
![]() |
View Item |