論文の概要: Longest Common Substring and Longest Palindromic Substring in
$\tilde{\mathcal{O}}(\sqrt{n})$ Time
- arxiv url: http://arxiv.org/abs/2309.01250v1
- Date: Sun, 3 Sep 2023 19:27:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-06 20:32:11.232103
- Title: Longest Common Substring and Longest Palindromic Substring in
$\tilde{\mathcal{O}}(\sqrt{n})$ Time
- Title（参考訳）: $\tilde{\mathcal{O}}(\sqrt{n})$ Timeにおける最も長い共通部分弦と最も長いパリンドロミック部分弦
- Authors: Domenico Cantone, Simone Faro, Arianna Pavone and Caterina Viola
- Abstract要約: LCS(Longest Common Substring)とLPS(Longest Palindromic Substring)は、コンピュータ科学における古典的な問題である。
計算回路モデルにおいて, LCS と LPS の双方に対する量子アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS)
are classical problems in computer science, representing fundamental challenges
in string processing. Both problems can be solved in linear time using a
classical model of computation, by means of very similar algorithms, both
relying on the use of suffix trees. Very recently, two sublinear algorithms for
LCS and LPS in the quantum query model have been presented by Le Gall and
Seddighin~\cite{GallS23}, requiring $\tilde{\mathcal{O}}(n^{5/6})$ and
$\tilde{\mathcal{O}}(\sqrt{n})$ queries, respectively. However, while the query
model is fascinating from a theoretical standpoint, its practical applicability
becomes limited when it comes to crafting algorithms meant for actual execution
on real hardware. In this paper we present, for the first time, a
$\tilde{\mathcal{O}}(\sqrt{n})$ quantum algorithm for both LCS and LPS working
in the circuit model of computation. Our solutions are simpler than previous
ones and can be easily translated into quantum procedures. We also present
actual implementations of the two algorithms as quantum circuits working in
$\mathcal{O}(\sqrt{n}\log^5(n))$ and $\mathcal{O}(\sqrt{n}\log^4(n))$ time,
respectively.
- Abstract（参考訳）: LCS(Longest Common Substring)とLPS(Longest Palindromic Substring)は、コンピュータ科学における古典的な問題であり、文字列処理における根本的な課題を表している。
どちらも接尾辞木(suffix tree)の使用に依存する、非常に類似したアルゴリズムを用いて、古典的な計算モデルを用いて線形時間に解くことができる。
量子クエリモデルにおける LCS と LPS の2つのサブ線形アルゴリズムが Le Gall と Seddighin~\cite{GallS23} によって提示され、それぞれ $\tilde{\mathcal{O}}(n^{5/6})$ と $\tilde{\mathcal{O}}(\sqrt{n})$ のクエリを必要とする。
しかし、クエリモデルは理論的には魅力的だが、実際のハードウェア上で実際に実行するためのアルゴリズムを開発する場合、実用性は限られている。
本稿では,計算回路モデルにおけるLCSとLCSの両方に対する$\tilde{\mathcal{O}}(\sqrt{n})$量子アルゴリズムを初めて提示する。
我々の解は以前の解よりも単純であり、量子手続きに容易に変換できる。
また、2つのアルゴリズムの実際の実装を、それぞれ$\mathcal{O}(\sqrt{n}\log^5(n))$と$\mathcal{O}(\sqrt{n}\log^4(n))$timeで動作する量子回路として提示する。
関連論文リスト
- 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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - 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) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms
for String Problems [5.490993287665715]
最も長いコモン(LCS)、長いパリンドローム(LPS)、そしてウルム距離(UL)は、古典的に線形に近い時間で解くことができる3つの基本弦問題である。
これらの問題に対する線形時間量子アルゴリズムと量子下界について述べる。
論文 参考訳（メタデータ） (2020-10-23T01:00:50Z) - Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文 参考訳（メタデータ） (2020-05-28T22:44:01Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。