論文の概要: Quantum Algorithm for the Multiple String Matching Problem

• arxiv url: http://arxiv.org/abs/2411.14850v1
• Date: Fri, 22 Nov 2024 10:50:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-25 15:02:53.296983
• Title: Quantum Algorithm for the Multiple String Matching Problem
• Title（参考訳）: 複数文字列マッチング問題の量子アルゴリズム
• Authors: Kamil Khadiev, Danil Serov,
• Abstract要約: 我々は$m$文字列のシーケンスを$S$と表現し、それを辞書と呼ぶ。 目的は、テキスト内の辞書から文字列のすべてのインスタンスを特定することである。 我々は,$O(n+sqrtmLlog nlog n)$クエリ複雑性と$O(n+sqrtmLlog n)=O*(n+sqrtmL)$タイム複雑性を持つ量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Let us consider the Multiple String Matching Problem. In this problem, we consider a long string, denoted by $t$, of length $n$. This string is referred to as a text. We also consider a sequence of $m$ strings, denoted by $S$, which we refer to as a dictionary. The total length of all strings from the dictionary is represented by the variable L. The objective is to identify all instances of strings from the dictionary within the text. The standard classical solution to this problem is Aho-Corasick Algorithm that has $O(n+L)$ query and time complexity. At the same time, the classical lower bound for the problem is the same $\Omega(n+L)$. We propose a quantum algorithm with $O(n+\sqrt{mL\log n}+m\log n)$ query complexity and $O(n+\sqrt{mL\log n}\log b+m\log n)=O^*(n+\sqrt{mL})$ time complexity, where $b$ is the maximal length of strings from the dictionary. This improvement is particularly significant in the case of dictionaries comprising long words. Our algorithm's complexity is equal to the quantum lower bound $O(n + \sqrt{mL})$, up to a log factor. In some sense, our algorithm can be viewed as a quantum analogue of the Aho-Corasick algorithm.
• Abstract（参考訳）: 複数文字列マッチングの問題について考えてみましょう。 この問題では、長さ$n$の長い文字列を$t$で表す。 この文字列をテキストと呼ぶ。 また、$m$文字列のシーケンスを$S$と表現し、辞書として参照する。 目的は、テキスト内の辞書から文字列のすべてのインスタンスを特定することである。 この問題の標準的な古典的解法は、O(n+L)$クエリと時間複雑性を持つAho-Corasick Algorithmである。 同時に、問題の古典的下界は同じ$\Omega(n+L)$である。 我々は,$O(n+\sqrt{mL\log n}+m\log n)$クエリ複雑性と$O(n+\sqrt{mL\log n}\log b+m\log n)=O^*(n+\sqrt{mL})$タイム複雑性を提案する。 この改良は、長い単語からなる辞書の場合、特に重要である。 我々のアルゴリズムの複雑さは、対数係数までの量子下界$O(n + \sqrt{mL})$と等しい。 ある意味では、我々のアルゴリズムはAho-Corasickアルゴリズムの量子アナログと見なすことができる。

関連論文リスト

• Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings [0.8057006406834466]
  2つのラン長符号化(RLE)文字列間の最長コモン(LCS)問題に対して、近似量子アルゴリズムを提案する。 我々のアルゴリズムのコストは$tildemathcalO(n2/3/d1/6-o(1)cdotmathrmpolylog(tilden))$ timeであるのに対し、問題のクエリの下限は$tildeOmega(n2/3/d1/6)$である。
  論文  参考訳（メタデータ） (2024-10-21T15:52:08Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings [0.951828574518325]
  ラン長符号化(RLE)入力に対して,最長共通(LCS)問題に対するサブ線形量子アルゴリズムを提案する。 我々のアルゴリズムは$tildeO(n5/6)cdot O(mathrmpolylog(tilden))$ timeで、$n$と$tilden$はそれぞれ入力のエンコードされた長さとデコードされた長さである。
  論文  参考訳（メタデータ） (2023-10-02T08:14:34Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems [11.048346250166073]
  テキスト集合問題の2つのバージョンについて考察する。 文字列のシーケンスは$s1,dots,sn$ of total length $L$ that is a dictionary, string $t$ of length $m$ that is textsです。 どちらの問題に対しても、従来の量子アルゴリズムよりもうまく動作する新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-18T14:16:49Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
  辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。 この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
  論文  参考訳（メタデータ） (2020-05-28T22:44:01Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。