Freiburg 2024 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

Q: Fachverband Quantenoptik und Photonik

Q 38: Poster IV

Q 38.46: Poster

Wednesday, March 13, 2024, 17:00–19:00, KG I Foyer

Spatial search via quantum walk on lattices with long-range hopping — •Moritz Linnebacher, Emma King, and Giovanna Morigi — Theoretische Physik, Universität des Saarlandes, D-66123 Saarbrücken, Germany

Spatial search forms the basis of many noteworthy classical and quantum algorithms. In some settings, quantum spatial search achieves runtimes of O(√N) compared to its classical counterpart with runtimes of O(N), where N is the size of the search space. In our work we implement spatial search via continuous-time quantum walk on lattices comprising N sites with long-range hopping. The hopping strength decays as 1/ℓ^α with inter-site distance ℓ and the exponent α∈ [0,∞). We focus on one- and two-dimensional lattices with d=1,2, where a rigorous numeric treatment shows that the search succeeds with high probability in O(√N) runtime for α ≤ d, even in d=1 spatial dimension. For lattices with nearest-neighbour interactions, corresponding to α→∞, the quadratic speedup over classical spatial search is lost. This highlights the importance of considering long-range interactions for search in low-dimensional lattices.

Keywords: spatial search; continuous-time quantum walks; long-range interacting systems; quantum algorithms; low-dimensional lattices