Optimal quantum spatial search with one-dimensional long-range interactions
Authors:
Preprint
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 $\mathcal 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-neighbour Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with $\mathcal O(\sqrt n)$ run time and large fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as $1/r^\alpha$ with distance $r$. In particular, near unit fidelity is achieved for $\alpha\approx 1$ and, in the limit $n\to\infty$, we find a continuous transition from a region where optimal spatial search does exist ($\alpha1.5$). Numerically, we show that spatial search is robust to dephasing noise and that, for realistic conditions, $\alpha \lesssim 1.2$ should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.
Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- Many-body physics with individually controlled Rydberg atomsNature Physics, 2020
- Observation of a many-body dynamical phase transition with a 53-qubit quantum simulatorNature, 2017
- Photonic simulation of entanglement growth and engineering after a spin chain quenchNature Communications, 2017
- Efficient tomography of a quantum many-body systemNature Physics, 2017
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular GraphsScientific Reports, 2015
- Non-local propagation of correlations in quantum systems with long-range interactionsNature, 2014
- Zeros of the derivatives of the Riemann zeta function onJournal of Number Theory, 2014
- Observation of dipolar spin-exchange interactions with lattice-confined polar moleculesNature, 2013
- A toolbox for lattice-spin models with polar moleculesNature Physics, 2006
- The finite group velocity of quantum spin systemsCommunications in Mathematical Physics, 1972