論文の概要: Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching

• arxiv url: http://arxiv.org/abs/2410.06808v1
• Date: Wed, 9 Oct 2024 12:05:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-01 03:30:47.224030
• Title: Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
• Title（参考訳）: 近似パターンマッチングのための準最適時間量子アルゴリズム
• Authors: Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz,
• Abstract要約: パターンマッチングにおけるハミング距離と、編集によるパターンマッチングにおける編集距離の2つを考える。 時間的複雑性は$tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatchesと$hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Editsである。
• 参考スコア（独自算出の注目度）: 2.4167127333650202
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold $k$, the task is to identify the fragments of $T$ that are at distance at most $k$ to $P$. We consider the two most common distances: Hamming distance (the number of character substitutions) in Pattern Matching with Mismatches and edit distance (the minimum number of character insertions, deletions, and substitutions) in Pattern Matching with Edits. We revisit the complexity of these two problems in the quantum setting. Our recent work [STOC'24] shows that $\hat{O}(\sqrt{nk})$ quantum queries are sufficient to solve (the decision version of) Pattern Matching with Edits. However, the quantum time complexity of the underlying solution does not provide any improvement over classical computation. On the other hand, the state-of-the-art algorithm for Pattern Matching with Mismatches [Jin and Nogler; SODA'23] achieves query complexity $\hat{O}(\sqrt{nk^{3/2}})$ and time complexity $\tilde{O}(\sqrt{nk^2})$, falling short of an unconditional lower bound of $\Omega(\sqrt{nk})$ queries. In this work, we present quantum algorithms with a time complexity of $\tilde{O}(\sqrt{nk}+\sqrt{n/m}\cdot k^2)$ for Pattern Matching with Mismatches and $\hat{O}(\sqrt{nk}+\sqrt{n/m}\cdot k^{3.5})$ for Pattern Matching with Edits; both solutions use $\hat{O}(\sqrt{nk})$ queries. The running times are near-optimal for $k\ll m^{1/3}$ and $k\ll m^{1/6}$, respectively, and offer advantage over classical algorithms for $k\ll (mn)^{1/4}$ and $k\ll (mn)^{1/7}$, respectively. Our solutions can also report the starting positions of approximate occurrences of $P$ in $T$ (represented as collections of arithmetic progressions); in this case, the unconditional lower bound and the complexities of our algorithms increase by a $\Theta(\sqrt{n/m})$ factor.
• Abstract（参考訳）: 近似パターンマッチングは、最も基本的な文字列処理タスクの一つである。 テキスト$T$ of length $n$、パターン$P$ of length $m$、しきい値$k$が与えられたら、そのタスクは、最大$k$から$P$までの距離にある$T$の断片を特定することである。 パターンマッチングにおけるハミング距離(文字置換数)と編集距離(最小文字挿入数、削除数、置換数)である。 量子環境におけるこれらの2つの問題の複雑さを再考する。 我々の最近の研究[STOC'24]は、$\hat{O}(\sqrt{nk})$ 量子クエリが(編集によるパターンマッチングの)解決に十分であることを示している。 しかし、基礎となる解の量子時間複雑性は、古典的な計算よりもいかなる改善も与えない。 一方、Pattern Matching with Mismatches [Jin and Nogler; SODA'23] の最先端のアルゴリズムは、クエリの複雑さを$\hat{O}(\sqrt{nk^{3/2}})$とtimeの複雑さを$\tilde{O}(\sqrt{nk^2})$で達成している。 この研究では、時間複雑性が $\tilde{O}(\sqrt{nk}+\sqrt{n/m}\cdot k^2)$ for Pattern Matching with Mismatches と $\hat{O}(\sqrt{nk}+\sqrt{n/m}\cdot k^{3.5})$ for Pattern Matching with Edits を提示する。 ランニング時間は、それぞれ$k\ll m^{1/3}$と$k\ll m^{1/6}$に最適であり、それぞれ$k\ll (mn)^{1/4}$と$k\ll (mn)^{1/7}$に有利である。 我々の解はまた、$P$ in $T$(算術進行の集合として表される)の概算発生の開始位置を報告し、この場合、無条件の下限とアルゴリズムの複雑さは$\Theta(\sqrt{n/m})$ factorによって増加する。

関連論文リスト

• Quantum Algorithm for the Multiple String Matching Problem [0.0]
  我々は$m$文字列のシーケンスを$S$と表現し、それを辞書と呼ぶ。 目的は、テキスト内の辞書から文字列のすべてのインスタンスを特定することである。 我々は,$O(n+sqrtmLlog nlog n)$クエリ複雑性と$O(n+sqrtmLlog n)=O*(n+sqrtmL)$タイム複雑性を持つ量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-22T10:50:43Z)
• On the Communication Complexity of Approximate Pattern Matching [2.4167127333650202]
  上界が$O(n/m cdot k log2 m)$ bitsであることを証明する。 また、$O(n/m cdot k log2 m)$ bits は、$k$-error 発生毎に$P$ in $T$ のエンコードを可能にする。
  論文  参考訳（メタデータ） (2024-03-27T17:57:16Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。 2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
  論文  参考訳（メタデータ） (2023-11-03T09:09:23Z)
• 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)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。 本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
  論文  参考訳（メタデータ） (2021-05-18T06:51:11Z)
• 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)
• Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees [0.19573380763700712]
  木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。 Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。 本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-08-01T14:21:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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