Quantum Algorithm for the Fixed-Radius Neighbor Search

• URL: http://arxiv.org/abs/2507.03445v1
• Date: Fri, 04 Jul 2025 10:01:10 GMT
• Title: Quantum Algorithm for the Fixed-Radius Neighbor Search
• Authors: Luca Cappelli, Claudio Sanavio, Alessandro Andrea Zecchi, Giuseppe Murante, Sauro Succi,
• Abstract summary: We propose a quantum algorithm for the Fixed RAdius Neighbor Search problem (FRANS) based on the fixed-point version of Grover's algorithm.<n>We derive an efficient circuit for solving the FRANS with linear query complexity with the number of particles $N$.<n>We assess the resilience of the model to the readout error, suggesting an error correction-free strategy to check the accuracy of the results.
• Score: 39.58317527488534
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The 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 derive 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 explicitly write the Grover's operator and analyze its gate complexity. The whole algorithm has complexity of $\mathcal{O}(M^{\frac{1}{2}}N^{2})$ in the worst-case scenario, where $M$ is the number of neighboring pairs, and uses $\mathcal{O}(\log N)$ number of qubits. By employing extra ancilla qubits the depth of the circuit can be brought down to $\mathcal{O}(N\log N)$ at the cost of $\mathcal{O}(N)$ qubits for unstructured dataset, or $\mathcal{O}(\text{poly}(\log N))$ qubits for structured datasets. Finally we assess the resilience of the model to the readout error, suggesting an error correction-free strategy to check the accuracy of the results.

Related papers

• Quantum Search on Computation Trees [0.0]
  We show a generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC)<n>This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms.
  arXiv  Detail & Related papers  (2025-05-28T14:35:18Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  We present a quantum $tildeO(sqrtnk+k2)$-time algorithm that uses $tildeO(sqrtnz)$ queries, where $tildeO(cdot)$ hides polylogarithmic factors. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $tildeO(sqrtnz)$.
  arXiv  Detail & Related papers  (2023-11-03T09:09:23Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Fast and Efficient Matching Algorithm with Deadline Instances [6.969116920943907]
  We introduce a market model with $mathrmdeadline$ first.<n>We present our two optimized algorithms (textscFastGreedy and textscFastPostponedGreedy)<n>At the same time, our algorithms run faster than the original two algorithms.
  arXiv  Detail & Related papers  (2023-05-15T05:21:20Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
  arXiv  Detail & Related papers  (2021-05-18T06:51:11Z)
• Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
  Lexicographically minimal string rotation (LMSR) is a problem to find the minimal one among all rotations of a string in the lexicographical order. We propose an $O(n3/4)$ quantum query algorithm for LMSR.
  arXiv  Detail & Related papers  (2020-12-17T03:13:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Resonant Quantum Search with Monitor Qubits [0.0]
  We present an algorithm for the generalized search problem (searching $k$ marked items among $N$ items) based on a continuous Hamiltonian and exploiting resonance. This resonant algorithm has the same time complexity $O(sqrtN/k)$ as the Grover algorithm.
  arXiv  Detail & Related papers  (2020-02-21T19:31:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.