論文の概要: Deterministic Quantum Search via Recursive Oracle Expansion
- arxiv url: http://arxiv.org/abs/2507.15797v1
- Date: Mon, 21 Jul 2025 16:57:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-22 20:51:32.495072
- Title: Deterministic Quantum Search via Recursive Oracle Expansion
- Title（参考訳）: 再帰的なOracle拡張による決定論的量子探索
- Authors: John Burke, Ciaran McGoldrick,
- Abstract要約: 本稿では,従来の確率論的探索手法の代替となる新しい決定論的量子探索アルゴリズムを提案する。
提案手法は,任意の位相回転に依存することなく,量子探索の本質的な不確実性を排除している。
クエリの複雑さが増大しているにもかかわらず、この設計は、少なくとも18キュービットまでの探索空間において、拡散に必要な2キュービットゲートの総数を1桁以上削減することを示した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches. Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations, a key limitation of other deterministic methods. The algorithm achieves certainty by recursively expanding the base oracle so that it marks all states prefixed by the same two bits as the target, encompassing exactly one-quarter of the search space. This enables a step-by-step reduction of the superposition until the target state can be measured with certainty. The algorithm achieves deterministic success with a query complexity of $O(N^{\log_2(3)/2}) \approx O(N^{0.7925})$, falling between Grover's $O(\sqrt{N})$ scaling and the classical $O(N)$. Our approach relies exclusively on two-qubit nearest-neighbour diffusion operators, avoiding global diffusion entirely. We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits, with even greater advantages on hardware with limited qubit connectivity. The scheme's inherent determinism, reliance on simple nearest-neighbour, low-depth operations, and scalable recursive structure make it well-suited for hardware implementation. Additionally, we show that the algorithm naturally supports partial database search, enabling deterministic identification of selected target bits without requiring a full search, further broadening its applicability.
- Abstract（参考訳）: 本稿では,従来の確率論的探索手法の代替となる新しい決定論的量子探索アルゴリズムを提案する。
提案手法は、任意の位相回転に依存することなく、量子探索の本質的な不確実性を排除し、他の決定論的手法の鍵となる限界を解消する。
アルゴリズムは、ベースオラクルを再帰的に拡張して、ターゲットと同じ2ビットでプレフィックスされた全ての状態にマークし、探索空間の4分の1を正確に包含することで、確実性を達成する。
これにより、目標状態が確実に測定されるまで、重ね合わせを段階的に低減することができる。
このアルゴリズムは、クエリ複雑性$O(N^{\log_2(3)/2}) \approx O(N^{0.7925})$で決定論的に成功し、Groverの$O(\sqrt{N})$スケーリングと古典的な$O(N)$の間に落下する。
我々のアプローチは、大域的拡散を完全に回避し、2量子近傍拡散作用素にのみ依存する。
クエリの複雑さが増大しているにもかかわらず、この設計により、少なくとも18キュービットまでの探索空間において、拡散に必要な2キュービットゲートの総数は1桁以上減少し、また、量子ビット接続が制限されたハードウェアにさらに大きな利点があることが示される。
このスキーム固有の決定論、単純な最寄りの操作への依存、低深度演算、スケーラブルな再帰的構造は、ハードウェアの実装に適している。
さらに,本アルゴリズムは部分的データベース探索を自然にサポートし,全探索を必要とせずに選択した対象ビットの確定的識別を可能にし,適用性をさらに拡大することを示す。
関連論文リスト
- Deterministic Quantum Search for Arbitrary Initial Success Probabilities [0.0]
本研究では、任意の初期成功確率に対して効果的に動作する決定論的量子探索アルゴリズムを提案する。
提案手法は、確率的量子探索アルゴリズムが必要とする最適数を超える少なくとも1つの追加イテレーションを導入する。
論文 参考訳（メタデータ） (2025-05-21T13:35:42Z) - 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) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - Quantum Algorithm for Researching the Nearest (QARN) [0.0]
グローバーのアルゴリズムは量子コンピューティングに希望を与えた。
本稿では,最も近い値を求める確率を増大させるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-21T14:21:09Z) - Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
本稿では,従来のサンプリング型モーションプランナを,量子探索アルゴリズムを用いて解くことのできるデータベース・オーラル構造として,新しい定式化を提案する。
より単純なスパース環境では、量子完全経路探索アルゴリズム (Quantum Full Path Search Algorithm, Q-FPS) を定式化し、完全なランダムパス解の重ね合わせを生成する。
密集した非構造環境において、親子接続の量子重ね合わせを生成する量子高速探索ランダムツリーアルゴリズム q-RRT を定式化する。
論文 参考訳（メタデータ） (2023-04-10T19:12:25Z) - Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。