論文の概要: Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer
- arxiv url: http://arxiv.org/abs/2210.04664v2
- Date: Wed, 12 Oct 2022 00:42:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-23 01:09:25.306955
- Title: Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer
- Title（参考訳）: ハイブリッド量子古典型計算機上での深さ優先探索アルゴリズム
- Authors: Haoxiang Guo
- Abstract要約: Depth-First SearchとGroverのアルゴリズムを組み合わせてDepth-First Grover Search(DFGS)を生成する
DFGSは未知の解数で非構造化データベース上の複数解探索問題を処理する。
新しいアルゴリズムは$mathcalO(msqrtN)$の平均複雑さを達成し、通常のGrover Searchと同じくらい効率的に機能する。
- 参考スコア（独自算出の注目度）: 2.487445341407889
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We demonstrated the detailed construction of the hybrid quantum-classical
computer. Based on this architecture, the useful concept of amplitude
interception is illustrated. It is then embedded into a combination of
Depth-First Search and Grover's algorithm to generate a novel approach, the
Depth-First Grover Search(DFGS), to handle multi-solution searching problems on
unstructured databases with an unknown number of solutions. Our new algorithm
attains an average complexity of $\mathcal{O}(m\sqrt{N})$ which performs as
efficient as a normal Grover Search, and a $\mathcal{O}(\sqrt{p}N)$ complexity
with a manually determined constant $p$ for the case with all elements are
solutions, where a normal Grover Search will degenerate to
$\mathcal{O}(N\sqrt{N})$. The DFGS algorithm is more robust and stable in
comparison.
- Abstract（参考訳）: 量子古典型ハイブリッドコンピュータの詳細な構成を実証した。
このアーキテクチャに基づいて、振幅インターセプションの有用な概念が説明される。
その後、深さ優先探索とグローバーのアルゴリズムの組み合わせに組み込まれ、未知数の解を持つ非構造化データベースの多重解探索問題を扱う新しいアプローチである深さ優先グローバー探索(dfgs)を生成する。
新しいアルゴリズムは、通常のグローバー探索と同じくらい効率的である$\mathcal{o}(m\sqrt{n})$の平均複雑性を達成し、すべての要素に対して手動で決定された定数$p$を持つ$\mathcal{o}(\sqrt{p}n)$は解であり、通常のグローバー探索は$\mathcal{o}(n\sqrt{n})$となる。
DFGSアルゴリズムはより堅牢で安定である。
関連論文リスト
- Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。
本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
論文 参考訳（メタデータ） (2024-08-11T10:28:49Z) - A Bi-directional Quantum Search Algorithm [30.62704006898929]
本稿では、パーシャルグローバーの探索アルゴリズムと双方向探索を組み合わせて、高速グローバーの量子探索アルゴリズムを作成する。
両方向探索手法をGrover部分探索に組み込み,初期状態と1つのマーク付き状態を並列に比較した。
提案したBDGSアルゴリズムは、最先端のDepth-First Grover's Search (DFGS) とジェネリックGrover's Search (GS) の実装を2〜20ドルでベンチマークする。
論文 参考訳（メタデータ） (2024-04-24T03:11:10Z) - Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。
マッチング条件の各ビットに個別のオラクルを関連付け、独立にテスト可能な複数の部分的なオラクル関数を得るという考え方を探求する。
アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。
論文 参考訳（メタデータ） (2024-03-19T11:32:02Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Distributed exact quantum algorithms for Bernstein-Vazirani and search
problems [9.146620606615889]
我々は、$t$の計算ノードを持つ分散Bernstein-Vaziraniアルゴリズム(DBVA)と、未順序データベースの1つのターゲット項目で探索問題を解決する分散型Grover'sアルゴリズム(DEGA)を提供する。
我々は、MindQuantum(量子ソフトウェア)上でDBVAとDEGAの状況を提供し、我々の手法の正確性と実践性を検証する。
論文 参考訳（メタデータ） (2023-03-19T14:18:49Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。