論文の概要: A Bi-directional Quantum Search Algorithm
- arxiv url: http://arxiv.org/abs/2404.15616v1
- Date: Wed, 24 Apr 2024 03:11:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-25 14:43:50.822826
- Title: A Bi-directional Quantum Search Algorithm
- Title(参考訳): 双方向量子探索アルゴリズム
- Authors: Debanjan Konar, Zain Hafeez, Vaneet Aggarwal,
- Abstract要約: 本稿では、パーシャルグローバーの探索アルゴリズムと双方向探索を組み合わせて、高速グローバーの量子探索アルゴリズムを作成する。
両方向探索手法をGrover部分探索に組み込み,初期状態と1つのマーク付き状態を並列に比較した。
提案したBDGSアルゴリズムは、最先端のDepth-First Grover's Search (DFGS) とジェネリックGrover's Search (GS) の実装を2〜20ドルでベンチマークする。
- 参考スコア(独自算出の注目度): 30.62704006898929
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Grover's search algorithms, including various partial Grover searches, experience scaling problems as the number of iterations rises with increased qubits, making implementation more computationally expensive. This paper combines Partial Grover's search algorithm and Bi-directional Search to create a fast Grover's quantum search algorithm, referred to as Bi-Directional Grover Search (BDGS). We incorporated a bi-directional search tactic with a partial Grover search, starting from an initial state and a single marked state in parallel. We have shown in this article that our novel approach requires $\frac{\pi}{4\sqrt{2}}\sqrt{N}(1-\sqrt{\frac{1}{b^{r/2k}}})$ iterations over regular Grover Search and Partial Grover Search (PGS), which takes $\frac{\pi}{4}\sqrt{N}\sqrt{1-\frac{1}{b}}$ (here, $N=2^r$ elements, $b$ is the branching factor of partial search, and $k= \lceil\log_2b \rceil$). The proposed BDGS algorithm is benchmarked against the state-of-the-art Depth-First Grover's Search (DFGS) and generic Grover's Search (GS) implementations for $2$ to $20$ qubits and provides promising results. The Qiskit Python implementation of the proposed BDGS algorithm is available on Github (https://github.com/hafeezzwiz21/DFGS-BDGS).
- Abstract(参考訳): グロバーの探索アルゴリズムは、様々な部分的なグロバー探索を含むが、量子ビットの増加に伴い反復数が増加し、実装がより計算コストが高くなるにつれて、スケーリングの問題を経験する。
本稿では, 部分グロバーの探索アルゴリズムと双方向探索を組み合わせることで, 高速グロバーの量子探索アルゴリズムをBDGS(Bi-Directional Grover Search)と呼ぶ。
両方向探索手法をGrover部分探索に組み込み,初期状態と1つのマーク付き状態とを並列に比較した。
この記事では、我々の新しいアプローチは、$\frac{\pi}{4\sqrt{2}}\sqrt{N}(1-\sqrt {\frac{1}{b^{r/2k}}})$ iterations over regular Grover Search and partial Grover Search (PGS)であり、$\frac{\pi}{4}\sqrt{N}\sqrt{1-\frac{1}{b}}$ (rere, $N=2^r$ elements, $b$ is a branching factor of partial search, $k= \lceil\log_2b \rceil$)であることを示した。
提案したBDGSアルゴリズムは、最先端のDepth-First Grover's Search (DFGS) とジェネリックGrover's Search (GS) の実装を2〜20ドルでベンチマークし、有望な結果を提供する。
提案されたBDGSアルゴリズムのQiskit Python実装はGithubで公開されている(https://github.com/hafeezzwiz21/DFGS-BDGS)。
関連論文リスト
- Implementing the Grover Algorithm in Homomorphic Encryption Schemes [0.25782420501870296]
我々はGroverのアルゴリズムに対して、復号数$T/Tdagger$-gatesの回路に適した量子同型暗号スキームを適用する。
また、Groverのアルゴリズムの$T/Tdagger$ゲート複雑性は、任意のGrover回路を効率的な方法で同型に評価できることを示すために分析される。
論文 参考訳(メタデータ) (2024-03-07T22:13:14Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳(メタデータ) (2024-02-09T19:01:48Z) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
論文 参考訳(メタデータ) (2023-12-05T21:15:09Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳(メタデータ) (2023-11-07T04:59:02Z) - 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) - Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。
目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
論文 参考訳(メタデータ) (2023-03-03T02:40:26Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳(メタデータ) (2023-02-13T22:51:07Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer [2.487445341407889]
Depth-First SearchとGroverのアルゴリズムを組み合わせてDepth-First Grover Search(DFGS)を生成する
DFGSは未知の解数で非構造化データベース上の複数解探索問題を処理する。
新しいアルゴリズムは$mathcalO(msqrtN)$の平均複雑さを達成し、通常のGrover Searchと同じくらい効率的に機能する。
論文 参考訳(メタデータ) (2022-10-10T13:10:28Z) - Grover's search algorithm for $n$ qubits with optimal number of
iterations [0.0]
グローバーの探索アルゴリズムは、グローバーの拡散操作に続くオラクルの合成操作の繰り返し数に依存する。
1leq M leq N$ターゲット状態を持つ$n$-qubit Groverの探索アルゴリズムを構築するための一般的なスキームを示す。
論文 参考訳(メタデータ) (2020-11-08T18:46:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。