Optimal spatial searches with long-range tunneling
Open Access
- 6 October 2025
- journal article
- Published by American Physical Society (APS) in Physical Review Research
- Vol. 7 (4)
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 T can exhibit Grover's optimal scaling with the lattice size N , namely, T ∼ N , 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 d > 4 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 r as 1 / r α and 0 < α < 3 d / 2 . For α < d the dynamics mimics the one of a globally connected graph. For d < α < d + 2 , the quantum search on the graph can be mapped to a short-range model on a hypercube with spatial dimension d s = 2 d / ( α − d ) , indicating that the search is optimal for d s > 4 . 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.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (429529648-TRR306)
- QuantERA (532771420)
- Bundesministerium für Forschung, Technologie und Raumfahrt (EXC 2004/1-390534769)
- National Science Foundation (NSF PHY-1748958, NSF PHY-2309135)
This publication has 56 references indexed in Scilit:
- Universal scaling in real dimensionNature Communications, 2024
- Logical quantum processor based on reconfigurable atom arraysNature, 2023
- A quantum processor based on coherent transport of entangled atom arraysNature, 2022
- Programmable interactions and emergent geometry in an array of atom cloudsNature, 2021
- Quasiparticle engineering and entanglement propagation in a quantum many-body systemNature, 2014
- Non-local propagation of correlations in quantum systems with long-range interactionsNature, 2014
- Density of states on fractals : « fractons »Journal de Physique Lettres, 1982
- The finite group velocity of quantum spin systemsCommunications in Mathematical Physics, 1972
- Three approaches to the quantitative definition of information*International Journal of Computer Mathematics, 1968
- A formal theory of inductive inference. Part IInformation and Control, 1964