論文の概要: Circuit-depth optimization of quantum partial-search algorithms
- arxiv url: http://arxiv.org/abs/2609.28147v1
- Date: Wed, 23 Sep 2026 14:04:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-25 00:05:18.055709
- Title: Circuit-depth optimization of quantum partial-search algorithms
- Title（参考訳）: 量子部分探索アルゴリズムの回路深度最適化
- Abstract要約: 部分探索アルゴリズムはグローバルとローカルの2種類のGrover演算子を用いて実装され、前者は全探索のための標準Grover演算子であり、後者は探索部分空間に作用する拡散演算子を持つ。
本稿では,グローバルおよびローカルなGrover演算子の固定積を繰り返し適用することにより生成したGrover演算子の交互列が,GRKアルゴリズムよりも低い回路深さが得られることを示す。
- 参考スコア（独自算出の注目度）: 8.460141119038388
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Grover's algorithm is optimal in terms of oracle queries. We can trade accuracy for speed, which gives rise to the quantum partial-search algorithm. The partial-search algorithm is implemented using two kinds of Grover operators, global and local, where the former is the standard Grover operator for full search and the latter has a diffusion operator acting on the search subspace. The global-local-global sequence, also known as the Grover-Radhakrishnan-Korepin (GRK) algorithm, has been proved optimal in the oracle-query metric. In this work, we show that the alternating sequence of global and local Grover operators, formed by repeatedly applying a fixed product of global and local Grover operators, can achieve a lower expected circuit depth than the GRK algorithm. Through systematic analysis, we obtain its exact success probability, expected depth, and asymptotically optimal parameters. We derive the boundary, characterized by the ratio between the depths of the oracle and the global diffusion operator, separating the depth-optimal and oracle-optimal partial-search algorithms. When the depths of the oracle and the global diffusion operator are comparable, our proposed alternating partial-search sequence can reduce the minimum expected circuit depth by more than 20\% compared with the GRK algorithm.
- Abstract（参考訳）: グローバーのアルゴリズムはオラクルクエリーの点で最適である。
精度を速さで交換できるので、量子部分探索アルゴリズムが生まれます。
部分探索アルゴリズムはグローバルとローカルの2種類のGrover演算子を用いて実装され、前者はフルサーチの標準Grover演算子であり、後者はサーチサブスペースに作用する拡散演算子を持つ。
Grover-Radhakrishnan-Korepin (GRK) アルゴリズムとしても知られるグローバル・ローカル・グローバル・シーケンスは、オラクル・クエリー計量において最適であることが証明されている。
本研究では,グローバルおよびローカルなGrover演算子の固定積を繰り返し適用することにより生成したGrover演算子の交互列が,GRKアルゴリズムよりも低い回路深さが得られることを示す。
系統解析により、その正確な成功確率、予測深度、漸近的に最適なパラメータを得る。
我々は, オラクルの深さと大域拡散演算子の深さの比を特徴とする境界を導出し, 深度最適化アルゴリズムとオラクル最適部分探索アルゴリズムを分離する。
オラクルの深さと大域拡散演算子の深さが等しい場合、GRKアルゴリズムと比較して最小の回路深さを20倍以上減少させることができる。
関連論文リスト
- Random Grover Search [2.4664400883501956]
本研究では,制約オラクルを直接利用するランダムなグロバー探索アルゴリズムについて検討する。
偏りの強いサンプリング分布は, いまだにほぼユニット間の成功確率を達成可能であることを示す。
論文 参考訳（メタデータ） (2026-06-10T07:34:05Z) - Palindromic structure of depth-efficient quantum search algorithms [10.743806550760121]
グロバーのアルゴリズムはクエリの複雑さにおいて最適であるが、回路深度では必ずしも最適ではない。
特に、ネストされた局所構造は、オラクルとグローバー拡散作用素が同等の深さを持つ場合、回路全体の深さを約40%削減する。
論文 参考訳（メタデータ） (2026-05-31T02:30:03Z) - Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm [8.110154079694063]
部分探索問題に対する最もよく知られた量子アルゴリズムは、Grover-Radhakrishnan-Korepin (GRK)アルゴリズムである。
大ブロック極限におけるGRKの最適性を証明する。
論文 参考訳（メタデータ） (2026-04-17T09:34:11Z) - Quantum Search without Global Diffusion [0.0]
量子探索は量子コンピューティングにおいて最も重要なアルゴリズムの一つである。
中心となるのは量子振幅増幅であり、古典的な探索よりも二次的なスピードアップを達成する技術である。
オラクルが唯一の大域演算子であるときに、このスピードアップを保存できることが示される。
論文 参考訳（メタデータ） (2026-04-16T18:00:27Z) - Exact bounds on quantum partial search algorithm and improving the parallel search [8.460141119038388]
グロバーのアルゴリズムは、非構造化データベースを探索する古典的なアルゴリズムを2次的に高速化する。
Grover-Radhakrishnan-Korepin (GRK)アルゴリズムは、このタスクの最適なプロトコルとして広く見なされている。
論文 参考訳（メタデータ） (2026-03-02T05:24:07Z) - Learning Regions of Interest for Bayesian Optimization with Adaptive
Level-Set Estimation [84.0621253654014]
本稿では,高信頼領域を適応的にフィルタするBALLETというフレームワークを提案する。
理論的には、BALLETは探索空間を効率的に縮小することができ、標準BOよりも厳密な後悔を示すことができる。
論文 参考訳（メタデータ） (2023-07-25T09:45:47Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。