Bonn 2025 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
QI: Fachverband Quanteninformation
QI 12: Quantum Computing Theory II
QI 12.3: Talk
Tuesday, March 11, 2025, 11:45–12:00, HS IV
Quantum spatial searches with long-range hopping — •Emma King1, Moritz Linnebacher1, Peter Orth1, Matteo Rizzi2, and Giovanna Morigi1 — 1Theoretische Physik, Universität des Saarlandes, D-66123 Saarbrücken, Germany — 2Institut fuer Theoretische Physik, Universität zu Köln, D-50937 Köln, Germany
Grover’s search algorithm is paradigmatic for quantum computing, demonstrating how quantum coherence might lead to a supremacy of quantum over classical information processing. A continuous-time implementation of Grover search can be achieved with a quantum walk on a graph, where vertices represent the elements of the database and the target state is tagged by an energy shift. Defining optimal search as an algorithm achieving near unit fidelity in time T=O(√N), this analog realization of quantum search executed on d-dimensional hypercubic lattices with nearest-neighbor hopping is optimal when d>4. We extend these results to consider lattices with hopping terms scaling as a power law 1/rα with the intersite distance r. In the presence of this tuneable connectivity, we assess the requirements on the exponent α for which the spatial search can achieve Grover’s optimal scaling, and then relate the result to the spectral dimension ds. At ds=4 we identify a continuous transition from a region where optimal search exists to a region of suboptimality. Numerically, we demonstrate that the search is robust to disorder in the lattice onsite energy. These results enhance our understanding of analog quantum search in low spatial dimensions and could be accessible experimentally using trapped ultracold atoms.
Keywords: Quantum search; Continuous-time quantum walk; Long-range hopping; Time complexity