論文の概要: Adaptive complete quantum search with unknown number of solutions
- arxiv url: http://arxiv.org/abs/2610.06364v1
- Date: Mon, 05 Oct 2026 14:01:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-09 08:51:32.57936
- Title: Adaptive complete quantum search with unknown number of solutions
- Title（参考訳）: 未知数の解をもつ適応完全量子探索
- Abstract要約: 非構造化データベース検索は、候補セット内の1つ以上の要素を見つける必要がある基本的な問題である。
古典, グローバー, 一般化された不動点量子探索インスタンスの様々な組み合わせについて考察する。
我々はこれらを適応的なアプローチに統一し、単体実行時間当たりの成功確率を最大化する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Unstructured database search is a fundamental problem that requires finding one or more elements satisfying a specific property within a set of candidates. While Grover's algorithm provides a quadratic speedup for finding a marked element when the number of solutions is known, finding all solutions when their number is unknown presents additional challenges. In this paper, we thoroughly analyze this problem by considering all the different regimes of combinations of classical, Grover and generalized fixed-point quantum search instances. We unify these into an adaptive Bayesian approach that maximizes the expected success probability per unit execution time at each searching instance. For a problem with a known number of solutions, much lower than the database size, we prove that our proposed approach is asymptotically optimal within the considered search model. Furthermore, we prove that for any probability distribution characterizing the likely number of solutions, in regimes where the classical verification time is at most 25% of the quantum amplitude amplification time, hybrid classical and Grover approaches are preferred to generalized fixed-point. Outside of this regime, we derive an upper bound on the maximal improvement achievable by fixed-point search compared to the best Grover-based score. Additionally, we determine the optimal transition point between classical sampling and quantum searching using an integral approximation of the probability distribution of the number of solutions. The analytical results are also supported by numerical simulations of the proposed algorithm and by comparisons between the generalized fixed-point and Grover-based search policies.
- Abstract（参考訳）: 非構造化データベース探索は、候補のセット内で特定の特性を満たす1つ以上の要素を見つける必要がある基本的な問題である。
グロバーのアルゴリズムは、解の数を知っているときのマーク要素を見つけるための二次的なスピードアップを提供するが、その数が未知のときのすべての解を見つけることは、さらなる課題をもたらす。
本稿では,古典,グロバー,一般化された定点量子探索インスタンスの様々な組み合わせを考慮し,この問題を徹底的に解析する。
我々はこれらを適応ベイズ的アプローチに統一し、各検索インスタンスにおける単体実行時間当たりの成功確率を最大化する。
データベースサイズよりもはるかに低い既知の解数の問題に対して,提案手法が検索モデルにおいて漸近的に最適であることを示す。
さらに,古典的検証時間が量子振幅増幅時間の25%以上であるような状況下では,任意の確率分布において,一般化された固定点よりも古典的およびグローバー的アプローチが好ましいことを証明した。
この体制の外では、Grover を用いた最良のスコアと比較して、固定点探索により達成可能な最大改善値の上限を導出する。
さらに,古典的サンプリングと量子探索の間の最適遷移点を,解数の確率分布の積分近似を用いて決定する。
解析結果は,提案アルゴリズムの数値シミュレーションや,一般化された不動点とGroverに基づく探索ポリシーの比較によっても支持される。
関連論文リスト
- Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
我々は,バッテッチとエーデンベンツの以前の研究に基づいて,旅行販売問題のための国家準備ルーチンを構築した。
イテレーションでは、数回のイテレーションだけで妥当な近似比を達成することを目指しています。
論文 参考訳（メタデータ） (2026-02-09T09:21:04Z) - Enumeration algorithms for combinatorial problems using Ising machines: When should we stop exploring energy landscapes? [0.28675177318965045]
我々はIsingマシンを用いた最適化と制約満足度問題に対する列挙アルゴリズムを提案する。
我々のアルゴリズムは、列挙の失敗確率がユーザ指定値によって上限づけられていることを理論的に保証している。
提案アルゴリズムは, 従来の分岐結合アルゴリズムよりも高速に, 大規模で高密度なグラフに最大傾きを列挙する。
論文 参考訳（メタデータ） (2024-11-29T23:33:26Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
本稿では,従来のサンプリング型モーションプランナを,量子探索アルゴリズムを用いて解くことのできるデータベース・オーラル構造として,新しい定式化を提案する。
より単純なスパース環境では、量子完全経路探索アルゴリズム (Quantum Full Path Search Algorithm, Q-FPS) を定式化し、完全なランダムパス解の重ね合わせを生成する。
密集した非構造環境において、親子接続の量子重ね合わせを生成する量子高速探索ランダムツリーアルゴリズム q-RRT を定式化する。
論文 参考訳（メタデータ） (2023-04-10T19:12:25Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。
頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。
特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文 参考訳（メタデータ） (2022-01-18T11:16:40Z) - A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs [0.4925222726301578]
本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。
量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
論文 参考訳（メタデータ） (2021-03-29T08:59:26Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Quantum Search with Prior Knowledge [15.384459603233978]
本稿では,Grover の探索アルゴリズムの新たな一般化を提案する。
提案アルゴリズムは,クエリ数が固定された場合の解を見つけるための最適成功確率を実現する。
論文 参考訳（メタデータ） (2020-09-18T09:50:33Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。