Optimal spatial searches with long-range tunneling

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 <α< 3d/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 ds = 2d/(α − d), indicating that the search is optimal for ds > 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.