論文の概要: Random Grover Search
- arxiv url: http://arxiv.org/abs/2606.11759v1
- Date: Wed, 10 Jun 2026 07:34:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-11 16:42:38.344365
- Title: Random Grover Search
- Title（参考訳）: ランダムグローバー探索
- Authors: Dekuan Dong, Jiaxin Ma, Yingzhou Li,
- Abstract要約: 本研究では,制約オラクルを直接利用するランダムなグロバー探索アルゴリズムについて検討する。
偏りの強いサンプリング分布は, いまだにほぼユニット間の成功確率を達成可能であることを示す。
- 参考スコア（独自算出の注目度）: 2.4664400883501956
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Grover's algorithm achieves a quadratic speedup for unstructured search given a global oracle for the target set. In many applications, however, the target set is specified as the intersection of multiple constraint sets. Constructing a global oracle for the intersection can be costly, whereas the individual constraint oracles are often much simpler to implement. We study a randomized Grover search algorithm that directly uses these constraint oracles. At each iteration, one of the corresponding Grover operators is selected at random. For the two-operator case with uniform sampling, we prove that the success probability approaches one after \[ Θ\left(\frac\pi4\sqrt{\frac{N}{r}}\right) \] iterations, where $r$ is the size of the intersection. Thus, the algorithm achieves the same asymptotic query complexity as standard Grover search but without requiring a global oracle. We then generalize the analysis to arbitrary sampling distributions and an arbitrary number of Grover operators through an auxiliary operator that approximates the expected Grover evolution, while retaining the same asymptotic complexity. We further show that highly biased sampling distributions can still achieve near-unit success probability, enabling cheaper Grover operators to be used more frequently. Finally, we prove asymptotic optimality and support the theoretical results with numerical simulations.
- Abstract（参考訳）: グローバーのアルゴリズムは、対象集合に対する大域オラクルが与えられた非構造探索の2次高速化を達成する。
しかし、多くの応用において、対象集合は複数の制約集合の交叉として指定される。
交差点のグローバルなオラクルの構築にはコストがかかるが、個々の制約のオラクルの実装はより簡単であることが多い。
本稿では,これらの制約オラクルを直接利用するランダムなグロバー探索アルゴリズムについて検討する。
各反復において、対応するグロバー作用素の1つがランダムに選択される。
一様サンプリングを持つ2つの演算子の場合、成功確率は \[(\frac\pi4\sqrt {\frac{N}{r}}\right) \] 反復の後に 1 に近づき、$r$ は交差点のサイズである。
したがって、このアルゴリズムはGrover検索と同じ漸近的なクエリ複雑性を実現するが、大域的なオラクルは必要としない。
次に、任意のサンプリング分布と任意の数のGrover演算子に解析を一般化し、予測されるGroverの進化を近似する補助演算子を通して、同じ漸近的複雑性を維持しながら、解析を行う。
さらに、高バイアスのサンプリング分布は、依然としてユニットに近い成功率を達成でき、より安価なGrover演算子をより頻繁に使用できることを示す。
最後に,漸近的最適性を証明し,数値シミュレーションによる理論的結果を支持する。
関連論文リスト
- Non-unitary extension of Grover's search algorithm [0.0]
我々はGroverの探索アルゴリズムの非単体拡張を開発する。
本アルゴリズムは,一意に大きい回転をすることで探索問題の解を求める。
論文 参考訳（メタデータ） (2026-04-25T17:13:50Z) - Exact bounds on quantum partial search algorithm and improving the parallel search [8.460141119038388]
グロバーのアルゴリズムは、非構造化データベースを探索する古典的なアルゴリズムを2次的に高速化する。
Grover-Radhakrishnan-Korepin (GRK)アルゴリズムは、このタスクの最適なプロトコルとして広く見なされている。
論文 参考訳（メタデータ） (2026-03-02T05:24:07Z) - A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Quantum algorithm for unstructured search of ranked targets [0.0]
グローバーの量子アルゴリズムは、どの古典的アルゴリズムよりも高速に、構造化されていないデータベースからマークされたアイテムを見つけることができる。
複数のマークされた項目間のコヒーレンスは、我々のオラクル演算子とグローバーのアルゴリズムで最も優先度の高い項目を見つける確率を高める傾向にあることを示す。
論文 参考訳（メタデータ） (2024-11-30T03:11:09Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳（メタデータ） (2023-05-22T17:43:34Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - Sampled Transformer for Point Sets [80.66097006145999]
スパース変換器は、連続列列列関数の普遍近似器でありながら、自己アテンション層の計算複雑性を$O(n)$に下げることができる。
我々は、追加の帰納バイアスを伴わずに点集合要素を直接処理できる$O(n)$複雑性サンプリング変換器を提案する。
論文 参考訳（メタデータ） (2023-02-28T06:38:05Z) - Deterministic Grover search with a restricted oracle [2.976027966501599]
グロバーの量子探索アルゴリズムは古典的アルゴリズムよりも二次的な量子的優位性を提供する。
量子探索オラクルをユーザが制御することなく、正しい結果を返すための修正版を提示する。
論文 参考訳（メタデータ） (2022-01-01T02:04:11Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳（メタデータ） (2021-06-14T13:01:46Z) - Grover's search algorithm for $n$ qubits with optimal number of
iterations [0.0]
グローバーの探索アルゴリズムは、グローバーの拡散操作に続くオラクルの合成操作の繰り返し数に依存する。
1leq M leq N$ターゲット状態を持つ$n$-qubit Groverの探索アルゴリズムを構築するための一般的なスキームを示す。
論文 参考訳（メタデータ） (2020-11-08T18:46:50Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。