論文の概要: Quantum Algorithm for the Fixed-Radius Neighbor Search
- arxiv url: http://arxiv.org/abs/2507.03445v1
- Date: Fri, 04 Jul 2025 10:01:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-08 15:46:34.737923
- Title: Quantum Algorithm for the Fixed-Radius Neighbor Search
- Title（参考訳）: 固定ラディウス近傍探索のための量子アルゴリズム
- Authors: Luca Cappelli, Claudio Sanavio, Alessandro Andrea Zecchi, Giuseppe Murante, Sauro Succi,
- Abstract要約: 本稿では,Grover アルゴリズムの固定点バージョンに基づく固定 RAdius Neighbor Search problem (FRANS) の量子アルゴリズムを提案する。
我々は,FRANSを,粒子数$N$の線形クエリ複雑性で解くための効率的な回路を導出する。
読み出し誤差に対するモデルのレジリエンスを評価し,結果の精度を確認するための誤り訂正フリー戦略を提案する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 隣接探索は計算に要求される問題であり、通常は時間とメモリ消費の両方である。
この種のアルゴリズムの主な問題は、キャッシュミスによる長い実行時間である。
本研究では,Grover アルゴリズムの固定点バージョンに基づく固定 RAdius Neighbor Search problem (FRANS) の量子アルゴリズムを提案する。
我々は,FRANSを,粒子数$N$の線形クエリ複雑性で解くための効率的な回路を導出する。
量子回路は、固定半径内にあるすべての隣人のペアのリストと距離を返し、キャッシュミスによるスローダウンを避ける。
我々はGroverの演算子を明示的に記述し、ゲートの複雑さを分析する。
アルゴリズム全体の複雑さは、最悪のシナリオでは$\mathcal{O}(M^{\frac{1}{2}}N^{2})$で、$M$は隣接するペアの数であり、$\mathcal{O}(\log N)$クォービットの数を使用する。
余分なアンシラ量子ビットを用いることで、回路の深さを$\mathcal{O}(N\log N)$、非構造化データセットの$\mathcal{O}(N)$ qubits、構造化データセットの$\mathcal{O}(\text{poly}(\log N)$ qubitsとすることができる。
最後に,読み出し誤差に対するモデルのレジリエンスを評価し,結果の精度を確認するための誤り訂正フリー戦略を提案する。
関連論文リスト
- Quantum Search on Computation Trees [0.0]
モンタナロ(ToC)によるバックトラック木探索のための量子ウォークアルゴリズムの一般化を示す。
このフレームワークは、変数時間探索、量子分割と圧縮、爆弾クエリアルゴリズムなど、他の多くの量子フレームワークを再定義するための、簡単で便利な方法を提供する。
論文 参考訳（メタデータ） (2025-05-28T14:35:18Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。
LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-17T03:13:45Z) - Resonant Quantum Search with Monitor Qubits [0.0]
連続的ハミルトニアンと共振を利用した一般化探索問題($N$項目中$k$マークされた項目を探索する)のアルゴリズムを提案する。
この共振アルゴリズムはGroverアルゴリズムと同じ時間複雑性$O(sqrtN/k)$を持つ。
論文 参考訳（メタデータ） (2020-02-21T19:31:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。