Quantum Algorithm for the Fixed-Radius Neighbor Search

Abstract

Neighbor search is a computationally demanding problem, usually both time- and memory-consuming. The main problem of these kinds of algorithms is the long execution time due to cache misses. In this work, we propose a quantum algorithm for the Fixed–Radius Neighbor Search problem (FRANS) based on the fixed-point version of Grover’s algorithm. We propose an efficient circuit for solving the FRANS with query complexity linear in the number of particles [Formula: see text]. The quantum circuit returns the list of all the neighbor pairs within the fixed radius, together with their distance, avoiding the slowdown caused by cache misses. We analyzed the gate and query complexity of the circuit. Our FRANS algorithm achieves a total query complexity of [Formula: see text] to recover all [Formula: see text] solutions of the problem. We propose different implementations of the oracle, which must be chosen depending on the precise structure of the database. Among these, we present an implementation using the Chebyshev distance with depth [Formula: see text], where [Formula: see text] is the number of grid points used to discretize a spatial dimension. State-of-the-art algorithms for state preparation allow for a trade-off between depth and width of the circuit, with a volume (depth× width) of [Formula: see text]. This unfavorable scaling can be brought down to [Formula: see text] in case of structured datasets. To ensure that all target pairs are measured, we implemented in QFRANS a stopping criterion based on Bayesian inference and tested it on a 1D grid. We verified that, with an appropriate choice of [Formula: see text], the algorithm reliably recovers all solutions, with only rare exceptions in a small fraction of trials. Finally, we accounted for the readout complexity and assessed the resilience of the model to the readout error, suggesting an error correction-free strategy to check the accuracy of the results.