Optimal quantum spatial search with one-dimensional long-range interactions

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 ($\alpha <1.5$) to where it does not ($\alpha >1.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.

arXiv comment16 pages, 6 figures; accepted version

References in corpus (32)

• Quantum Computing in the NISQ era and beyond
• Quantum Simulation
• Strengths and Weaknesses of Quantum Computing
• Many-Body Physics with Individually-Controlled Rydberg Atoms
• Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
• A toolbox for lattice spin models with polar molecules
• Realizing a lattice spin model with polar molecules
• Non-local propagation of correlations in long-range interacting quantum systems
• Spatial search by quantum walk
• Observation of Entangled States of a Fully Controlled 20-Qubit System
• Entanglement and Tunable Spin-Spin Couplings Between Trapped Ions Using Multiple Transverse Modes
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Efficient tomography of a quantum many-body system
• Spatial search by quantum walk is optimal for almost all graphs
• Continuous symmetry breaking and a new universality class in 1D long-range interacting quantum systems
• Finite speed of quantum scrambling with long range interactions
• Strictly linear light cones in long-range interacting systems of arbitrary dimensions
• Hierarchy of linear light cones with long-range interactions
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Locality and digital quantum simulation of power-law interactions
• Photonic Simulation of Entanglement Growth After a Spin Chain Quench
• Fast State Transfer and Entanglement Renormalization Using Long-Range Interactions
• Optimal quantum spatial search on random temporal networks
• Spatial search by continuous-time quantum walks on crystal lattices
• On the optimality of spatial search by continuous-time quantum walk
• Versatile microwave-driven trapped ion spin system for quantum information processing
• Generalized Grover's algorithm for multiple phase inversion states
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Error bounds for the asymptotic expansion of the Hurwitz zeta function
• Environment-assisted analog quantum search
• Quantum Walk Search on Kronecker Graphs
• Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk