論文の概要: Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification

• arxiv url: http://arxiv.org/abs/2606.28452v1
• Date: Fri, 26 Jun 2026 09:41:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-30 18:07:15.573556
• Title: Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification
• Title（参考訳）: 最悪の分岐:振幅増幅による量子木探索
• Abstract要約: 振幅増幅による量子木探索について検討する。 振幅増幅はグローバーのアルゴリズムを一般化する。 古典的認知アーキテクチャSoarにインスパイアされたルックアヘッドに基づく量子グリージー検索を導入する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we investigate quantum tree search via amplitude amplification. Amplitude amplification generalizes Grover's algorithm by replacing the Hadamard initialization with an arbitrary unitary $A$, with Grover's algorithm recovered as the special case of uniform initialization. We demonstrate the construction of a dynamic search tree of depth $m$ with query complexity $\sqrt{\left(b_{avg}\right)^m}$ where $b_{avg}$ denotes the average branching factor, improving upon the commonly assumed $\sqrt{\left(b_{max}\right)^m}$, where $b_{max}$ is the maximum branching factor. We further challenge the widespread assumption that amplitude amplification is inferior to quantum backtracking. In fact, quantum backtracking is unsuitable for problems that do not naturally admit a backtracking structure; in such cases, amplitude amplification yields improved query complexity. We observe that amplitude amplification constructs the search tree dynamically, rendering its internal structure inaccessible, a constraint that applies equally to quantum backtracking. To address this, we propose sampling-based methods to estimate the tree structure, under the assumption that it approximates a normal distribution with increasing depth. Finally, we introduce a quantum greedy search based on a lookahead heuristic inspired by the classical cognitive architecture Soar, which models human-like problem-solving strategies.
• Abstract（参考訳）: 本研究では,振幅増幅による量子木探索について検討する。 振幅増幅は、アダマールの初期化を任意のユニタリな$A$に置き換えることでグロバーのアルゴリズムを一般化する。 クエリ複雑性を持つ深度$m$の動的探索木の構築を実証する。 $\sqrt{\left(b_{avg}\right)^m}$ ここで、$b_{avg}$は平均分岐係数を表し、一般的に仮定される$\sqrt{\left(b_{max}\right)^m}$で改善される。 さらに、振幅増幅が量子バックトラックよりも劣るという広い仮定に挑戦する。 実際、量子バックトラックはバックトラック構造を自然に認めない問題には適さないが、そのような場合、振幅増幅によりクエリの複雑さが向上する。 我々は、振幅増幅が探索木を動的に構築し、内部構造が到達不能となり、量子バックトラックに等しく適用される制約が生じることを観察する。 そこで本研究では,木構造を推定するサンプリングベース手法を提案する。 最後に,人間のような問題解決戦略をモデル化した古典的認知アーキテクチャであるSoarに触発された,ルックアヘッドのヒューリスティックに基づく量子グリーディ探索を導入する。

関連論文リスト

• Ancilla-mediated fixed-point quantum search using Grover iterations [0.0]
  グロバーの量子探索アルゴリズムは、非構造化データセットの基本的な二次的スピードアップを提供する。 本稿では,ロバスト収束を実現するアンシラを用いた固定点量子探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-08-30T15:13:14Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• A Nested Amplitude Amplification Protocol for the Binary Knapsack Problem [0.0]
  Amplitude Amplification は、Grover Adaptive Search (GAS) によって最適化された、探索問題の証明可能な高速化を提供する。 本研究では,二分数knapsack問題に対するネスト振幅増幅プロトコルを提案し,決定木を深さで分割し,第1変数の部分増幅を行い,全探索空間上でグローバルGASを実行する。
  論文  参考訳（メタデータ） (2026-04-07T12:14:25Z)
• A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search [0.0]
  本稿では、パスフィニングタスクを構造化探索問題としてキャストすることで、完璧な迷路を解くための量子アルゴリズムを提案する。 グロバーの振幅増幅に基づいて、アルゴリズムは重ね合わせ中の全ての候補経路を符号化し、その目標に近接することを評価する。 グロバー互換のオラクルは、高い適合状態を示し、適応的なカットオフ戦略は、探索を反復的に洗練する。
  論文  参考訳（メタデータ） (2025-07-29T15:51:19Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。 各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
  論文  参考訳（メタデータ） (2025-02-16T16:12:01Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer [2.487445341407889]
  Depth-First SearchとGroverのアルゴリズムを組み合わせてDepth-First Grover Search(DFGS)を生成する DFGSは未知の解数で非構造化データベース上の複数解探索問題を処理する。 新しいアルゴリズムは$mathcalO(msqrtN)$の平均複雑さを達成し、通常のGrover Searchと同じくらい効率的に機能する。
  論文  参考訳（メタデータ） (2022-10-10T13:10:28Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  相関クラスタリングは多くのアプリケーションにおいて重要なクラスタリング問題である。 本研究では,ランダムノイズや対向的な修正によって崩壊した潜伏クラスタリングを再構築しようとする,この問題の再構築版について検討する。
  論文  参考訳（メタデータ） (2021-08-10T14:46:17Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• HighDist Framework: Algorithms and Applications [0.5584060970507505]
  量子回路の出力分布のモードが与えられた閾値よりも大きいかどうかを判定する問題を導入する。 空間複雑性が分布領域の大きさの対数的であるこれらの問題の有望バージョンに対する量子アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-03-16T13:06:36Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。 我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
  論文  参考訳（メタデータ） (2020-08-20T03:42:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。