論文の概要: Quantum Algorithm for Searching of Two Sets Intersection
- arxiv url: http://arxiv.org/abs/2312.16897v1
- Date: Thu, 28 Dec 2023 08:38:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-29 16:46:45.192972
- Title: Quantum Algorithm for Searching of Two Sets Intersection
- Title(参考訳): 2組断面積探索のための量子アルゴリズム
- Authors: Kamil Khadiev, Elizaveta Krendeleva
- Abstract要約: 2つの集合の交わりから要素を見つける量子アルゴリズムを提案する。
このアルゴリズムはGroverの検索の単純な適用よりも高速である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the paper, we investigate Two Sets Intersection problem. Assume that we
have two sets that are subsets of n objects. Sets are presented by two
predicates that show which of n objects belong to these sets. We present a
quantum algorithm that finds an element from the two sets intersection. It is a
modification of the well-known Grover's search algorithm that uses two Oracles
with access to the predicates. The algorithm is faster than the naive
application of Grover's search.
- Abstract(参考訳): 本稿では,2つの集合断面積問題について検討する。
n 個の対象の部分集合である 2 つの集合があると仮定する。
集合は、これらの集合に属する n 個のオブジェクトのどれかを示す2つの述語によって表される。
2つの集合の交叉から1つの要素を見つける量子アルゴリズムを提案する。
これは有名なGroverの検索アルゴリズムの修正であり、2つのOracleを使って述語にアクセスしている。
このアルゴリズムはGroverの検索の単純な適用よりも高速である。
関連論文リスト
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳(メタデータ) (2024-05-02T10:29:06Z) - 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) - Quantum counting, and a relevant sign [0.0]
量子コンピューティングの入門コースで必須となる2つのアルゴリズムは、グロバーの探索アルゴリズムと量子位相推定である。
我々はこれらのアルゴリズムを概観し、上記のサインを強調した。
論文 参考訳(メタデータ) (2023-10-11T12:29:31Z) - Concomitant Group Testing [49.50984893039441]
肯定的なテストが複数種類の項目の組み合わせを必要とするという考え方を捉えたグループテストの問題のバリエーションを紹介した。
目標は、可能な限り少数のテストを使用して、半欠陥セットをすべて確実に識別することである。
我々のアルゴリズムは、(i)決定性(ゼロエラー)かランダム化(小エラー)か、(ii)非適応性(非適応性)、完全適応性(完全適応性)、あるいは限定適応性(限定適応性)かによって区別される。
論文 参考訳(メタデータ) (2023-09-08T09:11:12Z) - 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) - Quantum search in sets with prior knowledge [0.0]
量子探索アルゴリズムは、$O(sqrtN)$のステップのみを使用して、$N$要素を持つ集合の探索問題を解くことで大きな影響を与えた。
量子探索アルゴリズムの修正版を用いることで、そのような集合に対して期待されるイテレーション数を削減できることが示されている。
論文 参考訳(メタデータ) (2022-07-21T21:45:17Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳(メタデータ) (2021-06-14T13:01:46Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - Quantum Algorithms for String Processing [58.720142291102135]
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。
第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
論文 参考訳(メタデータ) (2020-12-01T09:59:06Z) - Quantum Search with Prior Knowledge [15.384459603233978]
本稿では,Grover の探索アルゴリズムの新たな一般化を提案する。
提案アルゴリズムは,クエリ数が固定された場合の解を見つけるための最適成功確率を実現する。
論文 参考訳(メタデータ) (2020-09-18T09:50:33Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。