論文の概要: Deterministic Grover search with a restricted oracle
- arxiv url: http://arxiv.org/abs/2201.00091v3
- Date: Mon, 14 Nov 2022 16:02:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-02 17:22:12.562594
- Title: Deterministic Grover search with a restricted oracle
- Title(参考訳): 限定オラクルを用いた決定論的グローバー探索
- Authors: Tanay Roy, Liang Jiang, David I. Schuster
- Abstract要約: グロバーの量子探索アルゴリズムは古典的アルゴリズムよりも二次的な量子的優位性を提供する。
量子探索オラクルをユーザが制御することなく、正しい結果を返すための修正版を提示する。
- 参考スコア(独自算出の注目度): 2.976027966501599
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Grover's quantum search algorithm provides a quadratic quantum advantage over
classical algorithms across a broad class of unstructured search problems. The
original protocol is probabilistic, returning the desired result with
significant probability on each query, but in general, requiring several
iterations of the algorithm. We present a modified version to return the
correct result with certainty without having user control over the quantum
search oracle. Our deterministic, two-parameter "D2p" protocol utilizes
generalized phase rotations replacing the phase inversions after a standard
oracle query. The D2p protocol achieves a 100% success rate in no more than one
additional iteration compared to the optimal number of steps in the original
Grover's search enabling the same quadratic speed up. We also provide a
visualization using the Bloch sphere for enhanced geometric intuition.
- Abstract(参考訳): グローバーの量子探索アルゴリズムは、非構造化探索問題の幅広いクラスにわたる古典的アルゴリズムに対する二次量子優位性を提供する。
元のプロトコルは確率的であり、各クエリで所望の結果をかなりの確率で返すが、一般にアルゴリズムの繰り返しを必要とする。
我々は,量子検索オラクルをユーザが制御することなく,正しい結果を確実に返すための修正版を提案する。
我々の決定論的2パラメータ"D2p"プロトコルは、標準的なオラクルクエリの後に位相反転を置き換える一般化位相回転を利用する。
d2pプロトコルは、元のグローバー探索の最適なステップ数に比べて1回以上のイテレーションで100%の成功率を達成し、同じ二次的なスピードアップを実現している。
また,Bloch球を用いた幾何学的直観の可視化も行った。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible
Permutations [55.2480439325792]
スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムの新たなクラスである。
ウンルーが提唱した「二重側ゼロ探索」予想を証明する。
また、ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要であることも示している。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - Replicable Learning of Large-Margin Halfspaces [50.330457600322084]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳(メタデータ) (2024-02-21T15:06:51Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳(メタデータ) (2023-11-07T04:59:02Z) - Hybrid classical-quantum text search based on hashing [0.0]
非順序データベースにおける古典的な検索クエリの複雑さは、テキストの長さと与えられた値の長さにおいて線形であることが知られている。
本稿ではGroverの検索を実装した古典量子ハイブリッドアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-11-02T13:16:07Z) - Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
本稿では,従来のサンプリング型モーションプランナを,量子探索アルゴリズムを用いて解くことのできるデータベース・オーラル構造として,新しい定式化を提案する。
より単純なスパース環境では、量子完全経路探索アルゴリズム (Quantum Full Path Search Algorithm, Q-FPS) を定式化し、完全なランダムパス解の重ね合わせを生成する。
密集した非構造環境において、親子接続の量子重ね合わせを生成する量子高速探索ランダムツリーアルゴリズム q-RRT を定式化する。
論文 参考訳(メタデータ) (2023-04-10T19:12:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - 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) - Optimizing Quantum Search with a Binomial Version of Grover's Algorithm [4.220030262107688]
Groverの検索アルゴリズムの重要なコンポーネントである振幅増幅は、1つまたは複数のターゲット状態の確率を体系的に増加させるために反復的アプローチを使用する。
状態をクラスに分割することで増幅手順を強化するための新しい戦略を提案する。
論文 参考訳(メタデータ) (2020-07-21T15:36:35Z) - 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) - Multi-layer quantum search and inclusion of NP into BQP [6.362434591714693]
本稿では,Groverのアルゴリズムを指数的に高速化する多層量子探索法を提案する。
その結果、量子回路の高速化はユビキタスであり、Groverの探索は実証されたよりもはるかに強力であることがわかった。
論文 参考訳(メタデータ) (2020-04-23T17:44:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。