Quantum Algorithm for the Fixed-Radius Neighbor Search
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915702565240832 |
|---|---|
| author | Cappelli, Luca Sanavio, Claudio Zecchi, Alessandro Andrea Murante, Giuseppe Succi, Sauro |
| author_facet | Cappelli, Luca Sanavio, Claudio Zecchi, Alessandro Andrea Murante, Giuseppe Succi, Sauro |
| contents | Neighbor search is a computationally demanding problem, usually both time- and memory-consuming. The main problem of this kind 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 linear query complexity with the number of particles $N$. The quantum circuit returns the list of all the neighbors' pairs within the fixed radius, together with their distance, avoiding the slow down given by cache miss.
We analyzed the gate and the query complexity of the circuit. Our FRANS algorithm presents a query complexity of $\mathcal{O}(N/\sqrt{M})$, where $M$ is the number of solutions, reaching the optimal lower bound of the Grover's algorithm. 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 $\mathcal{O}(q_1)$, where $2^{q_1}$ 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$\times$ width) of $\mathcal{O}(N\log(N))$. This unfavorable scaling can be brought down to $\mathcal{O}(\text{poly}(\log N))$ in case of structured datasets. We proposed a stopping criterion based on Bayes interference and tested its validity on $1D$ simulations. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03445 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Algorithm for the Fixed-Radius Neighbor Search Cappelli, Luca Sanavio, Claudio Zecchi, Alessandro Andrea Murante, Giuseppe Succi, Sauro Quantum Physics Neighbor search is a computationally demanding problem, usually both time- and memory-consuming. The main problem of this kind 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 linear query complexity with the number of particles $N$. The quantum circuit returns the list of all the neighbors' pairs within the fixed radius, together with their distance, avoiding the slow down given by cache miss. We analyzed the gate and the query complexity of the circuit. Our FRANS algorithm presents a query complexity of $\mathcal{O}(N/\sqrt{M})$, where $M$ is the number of solutions, reaching the optimal lower bound of the Grover's algorithm. 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 $\mathcal{O}(q_1)$, where $2^{q_1}$ 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$\times$ width) of $\mathcal{O}(N\log(N))$. This unfavorable scaling can be brought down to $\mathcal{O}(\text{poly}(\log N))$ in case of structured datasets. We proposed a stopping criterion based on Bayes interference and tested its validity on $1D$ simulations. 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. |
| title | Quantum Algorithm for the Fixed-Radius Neighbor Search |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2507.03445 |