論文の概要: Quantum Search without Global Diffusion

• arxiv url: http://arxiv.org/abs/2604.15435v1
• Date: Thu, 16 Apr 2026 18:00:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-20 22:00:19.604717
• Title: Quantum Search without Global Diffusion
• Title（参考訳）: グローバル拡散を伴わない量子探索
• Authors: John Burke, Ciaran McGoldrick,
• Abstract要約: 量子探索は量子コンピューティングにおいて最も重要なアルゴリズムの一つである。 中心となるのは量子振幅増幅であり、古典的な探索よりも二次的なスピードアップを達成する技術である。 オラクルが唯一の大域演算子であるときに、このスピードアップを保存できることが示される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum search is among the most important algorithms in quantum computing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the $O(\sqrt{N})$ oracle complexity of Grover search when each partition contains at least $\log_2(\log_2 N)$ qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%-96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.
• Abstract（参考訳）: 量子探索は量子コンピューティングにおいて最も重要なアルゴリズムの一つである。 その中核は量子振幅増幅(quantum amplitude amplification)であり、ターゲットを示すオラクルと初期状態を反映する拡散演算子という2つの大域的な反射を組み合わせ、古典的な探索よりも2次的なスピードアップを達成する技術である。 このスピードアップは、オラクルが唯一のグローバル演算子であり、他の全ての操作が検索レジスタの非重複パーティション上でローカルに作用している場合に保存可能であることを示す。 我々は、初期状態と対象状態の両方がこれらの選択された分割に対してテンソル積として分解されると、アルゴリズムのダイナミクスに対して正確な閉形式解が認められる再帰的構成を示す。 これは、連続反射の間の主角における興味深い縮退によって実現され、単一の再帰的に定義された角度によって支配される2つの異なる値に崩壊する。 テンソル分解を自然に満足する問題である非構造探索に適用すると、各分割が少なくとも$\log_2(\log_2N)$ qubitsを含む場合、Grover Searchの$O(\sqrt{N})$ oracle complexityが残る。 18ビット探索問題では、2段階に分割することで、Groverと比較して最大51%-96%の回路深度が減少し、9%の追加のオラクルコールが必要になる。 より大きな問題サイズでは、このオラクルのオーバーヘッドは急速に減少し、拡散演算子よりもかなり深い場合、貴重な深さの低減が持続する。 より広範に、これらの結果は、量子探索において二次的なスピードアップを達成するために大域拡散作用素は必要ないことを示し、この基礎的アルゴリズムに対する新たな視点を提供する。 さらに,解析の中心にあるスカラー低減は,量子アルゴリズムの設計と評価において新たな方向性と革新を刺激し,動機づける。

関連論文リスト

• Exponential convergence dynamics in Grover's search algorithm [0.0]
  グロバーの探索アルゴリズムは、量子コンピューティングの多くの応用の基礎となっている。 我々はグロバーのアルゴリズムを修正して振動ダイナミクスを排除し、探索は解状態への指数的減衰として進行する。 基本的な考え方は、初期状態が非反射的に吸収されるようなアンシラ量子ビットを用いて、溶液状態を貯水池に変換することである。
  論文  参考訳（メタデータ） (2025-12-17T05:43:07Z)
• Deterministic Quantum Search via Recursive Oracle Expansion [0.0]
  本稿では,従来の確率論的探索手法の代替となる新しい決定論的量子探索アルゴリズムを提案する。 提案手法は,任意の位相回転に依存することなく,量子探索の本質的な不確実性を排除している。 クエリの複雑さが増大しているにもかかわらず、この設計は、少なくとも18キュービットまでの探索空間において、拡散に必要な2キュービットゲートの総数を1桁以上削減することを示した。
  論文  参考訳（メタデータ） (2025-07-21T16:57:15Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  QAMA(Quantum Annealing Multi-Head Attention)は、エネルギーベースのハミルトン最適化問題として注目を集める新しいドロップイン演算子である。 この枠組みでは、トークン相互作用を二項二項項に符号化し、低エネルギー構成の探索に量子アニールを用いる。 経験的に、自然言語と視覚のベンチマークによる評価は、タスク全体にわたって、標準的なマルチヘッドの注意から少なくとも2.7ポイントの精度が低下していることを示している。
  論文  参考訳（メタデータ） (2025-04-15T11:29:09Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Distributed Exact Generalized Grover's Algorithm [9.675088142486729]
  本稿では,汎用探索問題の解法として,分散Exactized Grover's Algorithm (DEGGA)を提案する。 我々のアルゴリズムは、目標状態が100%$の理論的確率で精度を保証します。 我々の方法は合計$n$ qubitsを必要とし、補助的なqubitsは不要である。
  論文  参考訳（メタデータ） (2024-05-11T09:17:11Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Deterministic Grover search with a restricted oracle [2.976027966501599]
  グロバーの量子探索アルゴリズムは古典的アルゴリズムよりも二次的な量子的優位性を提供する。 量子探索オラクルをユーザが制御することなく、正しい結果を返すための修正版を提示する。
  論文  参考訳（メタデータ） (2022-01-01T02:04:11Z)
• 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)

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

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