Optimal spatial searches with long-range tunneling
arXiv:2501.08148 · doi:10.1103/cv26-dk1q
Abstract
A quantum walk on a lattice is a paradigm of a quantum search in a database. The database qubit strings are the lattice sites, qubit rotations are tunneling events, and the target site is tagged by an energy shift. For quantum walks on a continuous time, the walker diffuses across the lattice and the search ends when it localizes at the target site. The search time can exhibit Grover's optimal scaling with the lattice size , namely, , on an all-connected, complete lattice. For finite-range tunneling between sites, instead, Grover's optimal scaling is warranted when the lattice is a hypercube of dimensions. Here, we show that Grover's optimum can be reached in lower dimensions on lattices of long-range interacting particles, when the interaction strength scales algebraically with the distance as and . For the dynamics mimics the one of a globally connected graph. For , the quantum search on the graph can be mapped to a short-range model on a hypercube with spatial dimension , indicating that the search is optimal for . Our work identifies an exact relation between criticality of long-range and short-range systems, it provides a quantitative demonstration of the resources that long-range interactions provide for quantum technologies, and indicates when existing experimental platforms can implement efficient analog quantum search algorithms.
28 pages (5 pages + 23 appendixes); published version of manuscript
References in corpus (34)
- Quantum Computing in the NISQ era and beyond
- Logical quantum processor based on reconfigurable atom arrays
- Observation of entanglement propagation in a quantum many-body system
- Programmable Quantum Simulations of Spin Systems with Trapped Ions
- Non-local propagation of correlations in long-range interacting quantum systems
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Quantum spin dynamics and entanglement generation with hundreds of trapped ions
- Strongly Correlated Quantum Walks in Optical Lattices
- Dipolar physics: A review of experiments with magnetic quantum gases
- Quantum simulation and computing with Rydberg-interacting qubits
- Extended Bose-Hubbard Models with Ultracold Magnetic Atoms
- Long-range interacting quantum systems
- Quantum speedup for active learning agents
- Programmable Interactions and Emergent Geometry in an Atomic Array
- Spatial search by quantum walk is optimal for almost all graphs
- Relations between Short Range and Long Range Ising models
- Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
- Hierarchy of linear light cones with long-range interactions
- Global Symmetry is Unnecessary for Fast Quantum Search
- Connectivity is a Poor Indicator of Fast Quantum Search
- High-fidelity detection of large-scale atom arrays in an optical lattice
- Optimal quantum spatial search on random temporal networks
- Dynamical phase transitions in sampling complexity
- Spatial search by continuous-time quantum walks on crystal lattices
- On the optimality of spatial search by continuous-time quantum walk
- Quantum Walks with Dynamical Control: Graph Engineering, Initial State Preparation and State Transfer
- Optimal State Transfer and Entanglement Generation in Power-law Interacting Systems
- Number Partitioning with Grover's Algorithm in Central Spin Systems
- Quantum spatial search on graphs subject to dynamical noise
- Error bounds for the asymptotic expansion of the Hurwitz zeta function
- Quantum Walk Search on Kronecker Graphs
- Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
- Universal scaling in real dimension