論文の概要: Quantum Algorithms for String Processing
- arxiv url: http://arxiv.org/abs/2012.00372v1
- Date: Tue, 1 Dec 2020 09:59:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-22 12:18:51.006211
- Title: Quantum Algorithms for String Processing
- Title（参考訳）: 文字列処理のための量子アルゴリズム
- Authors: Farid Ablayev, Marat Ablayev, Kamil Khadiev, Nailya Salihova and
Alexander Vasiliev
- Abstract要約: 既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。
第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
- 参考スコア（独自算出の注目度）: 58.720142291102135
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the paper, we investigate two problems on strings. The first one is the
String matching problem, and the second one is the String comparing problem. We
provide a quantum algorithm for the String matching problem that uses
exponentially less quantum memory than existing ones. The algorithm uses the
hashing technique for string matching, quantum parallelism, and ideas of
Grover's search algorithm. Using the same ideas, we provide two algorithms for
the String comparing problem. These algorithms also use exponentially less
quantum memory than existing ones. Additionally, the second algorithm works
exponentially faster than the existing one.
- Abstract（参考訳）: 本稿では,弦の2つの問題について考察する。
1つ目は文字列マッチング問題、もう1つは文字列比較問題である。
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
このアルゴリズムは、文字列マッチング、量子並列性、グローバー探索アルゴリズムのアイデアのためのハッシュ技術を用いる。
同じアイデアを用いて,文字列比較問題に対する2つのアルゴリズムを提案する。
これらのアルゴリズムは、既存のものよりも指数的に少ない量子メモリを使用する。
さらに、第2のアルゴリズムは既存のアルゴリズムよりも指数関数的に高速に動作する。
関連論文リスト
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Hybrid classical-quantum text search based on hashing [0.0]
非順序データベースにおける古典的な検索クエリの複雑さは、テキストの長さと与えられた値の長さにおいて線形であることが知られている。
本稿ではGroverの検索を実装した古典量子ハイブリッドアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-11-02T13:16:07Z) - Quantum counting, and a relevant sign [0.0]
量子コンピューティングの入門コースで必須となる2つのアルゴリズムは、グロバーの探索アルゴリズムと量子位相推定である。
我々はこれらのアルゴリズムを概観し、上記のサインを強調した。
論文 参考訳（メタデータ） (2023-10-11T12:29:31Z) - Quantum multi-programming for Grover's search [6.359294579761927]
本稿では,Grover 探索のための量子マルチプログラミング (QMP) アルゴリズムを提案する。
本アルゴリズムは,部分拡散演算子によりGroverのアルゴリズムを分解し,QMPにより並列に分解回路を実行する。
このアルゴリズムはGrover演算子の回転角を増大させ、その結果、成功確率を増大させる。
論文 参考訳（メタデータ） (2022-07-29T04:05:46Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Near-Optimal Quantum Algorithms for String Problems [0.5736353542430439]
ほぼ最適なクエリ複雑度と時間複雑度を持つ基本文字列問題に対する量子アルゴリズムを提案する。
これらの問題には、Longest Common Substring、Lexicographically Minimal String Rotation、Longest Square Substringが含まれる。
我々の手法は、Longest Repeated Substring、Longest Lyndon Substring、Minimmal Suffixといった他の関連する文字列問題に自然に拡張する。
論文 参考訳（メタデータ） (2021-10-19T02:32:18Z) - 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) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Quantum Algorithms for the Most Frequently String Search, Intersection
of Two String Sequences and Sorting of Strings Problems [0.0]
弦の3つの問題を解くアルゴリズムについて研究する。
1つ目は、最も頻度の高い文字列検索問題である。
2つ目は、2つの弦列の交叉である。
第三の問題は長さ$k$の$n$文字列をソートすることだ。
論文 参考訳（メタデータ） (2020-01-07T07:22:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。