Quantum algorithm for the Fixed-Radius Neighbor Search
International Journal of Modern Physics C · 30.10.2026
DOI: 10.1142/s0129183127501658 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Modern Physics C, online erschienen am 30.10.2026. Verfasst von Luca Cappelli und 5 weiteren Autor:innen. Die Arbeit nennt 63 Literaturangaben. Gefördert von: Italian National Center for HPC, Big Data and Quantum Computing.
Abstract (Originalsprache)
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 N. 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 M 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 [Formula: see text] 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.
Förderung
- Italian National Center for HPC, Big Data and Quantum Computing
Zitieren
APA
Cappelli, L., Sanavio, C., Zecchi, A. A., Mocz, P., Murante, G., & Succi, S. (2026). Quantum algorithm for the Fixed-Radius Neighbor Search. International Journal of Modern Physics C. https://doi.org/10.1142/s0129183127501658
Vancouver
Cappelli L, Sanavio C, Zecchi AA, Mocz P, Murante G, Succi S. Quantum algorithm for the Fixed-Radius Neighbor Search. International Journal of Modern Physics C. 2026. doi:10.1142/s0129183127501658
BibTeX
@article{Cappelli2026,
author = {Cappelli, Luca and Sanavio, Claudio and Zecchi, Alessandro Andrea and Mocz, Philip and Murante, Giuseppe and Succi, Sauro},
title = {Quantum algorithm for the Fixed-Radius Neighbor Search},
journal = {International Journal of Modern Physics C},
year = {2026},
doi = {10.1142/s0129183127501658}
}
EUVIMED