論文の概要: Quantum Algorithms for the Shortest Common Superstring and Text
Assembling Problems
- arxiv url: http://arxiv.org/abs/2306.10572v2
- Date: Sun, 31 Dec 2023 18:12:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-03 20:00:05.440995
- Title: Quantum Algorithms for the Shortest Common Superstring and Text
Assembling Problems
- Title（参考訳）: 最短共通スーパーストリングとテキスト集合問題に対する量子アルゴリズム
- Authors: Kamil Khadiev, Carlos Manuel Bosch Machado, Zeyu Chen, Junde Wu
- Abstract要約: テキスト集合問題の2つのバージョンについて考察する。
文字列のシーケンスは$s1,dots,sn$ of total length $L$ that is a dictionary, string $t$ of length $m$ that is textsです。
どちらの問題に対しても、従来の量子アルゴリズムよりもうまく動作する新しい量子アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 11.048346250166073
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider two versions of the Text Assembling problem. We
are given a sequence of strings $s^1,\dots,s^n$ of total length $L$ that is a
dictionary, and a string $t$ of length $m$ that is texts. The first version of
the problem is assembling $t$ from the dictionary. The second version is the
``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring
Problem''(SCS). In this case, $t$ is not given, and we should construct the
shortest string (we call it superstring) that contains each string from the
given sequence as a substring. These problems are connected with the sequence
assembly method for reconstructing a long DNA sequence from small fragments.
For both problems, we suggest new quantum algorithms that work better than
their classical counterparts. In the first case, we present a quantum algorithm
with $O(m+\log m\sqrt{nL})$ running time. In the case of SSP, we present a
quantum algorithm with running time $O(n^3 1.728^n +L
+\sqrt{L}n^{1.5}+\sqrt{L}n\log^2L\log^2n)$.
- Abstract（参考訳）: 本稿では,テキスト集合問題の2つのバージョンについて考察する。
文字列の列$s^1,\dots,s^n$ of total length $l$(辞書)と$t$ of length $m$(テキスト)が与えられます。
問題の最初のバージョンは、辞書から$t$を組み立てることである。
2番目のバージョンは ``Shortest Superstring Problem' (SSP) または ``Shortest Common Superstring Problem' (SCS) である。
この場合、$t$は与えられず、与えられたシーケンスから各文字列をサブストリングとして含む最短文字列(スーパーストリングと呼ぶ)を構築するべきです。
これらの問題は、小さな断片から長いDNA配列を再構成する配列アセンブリー法に関連付けられている。
どちらの問題に対しても、従来のアルゴリズムよりも優れた量子アルゴリズムを提案する。
最初のケースでは、$O(m+\log m\sqrt{nL})$ run time の量子アルゴリズムを示す。
SSP の場合、実行時間 $O(n^3 1.728^n +L +\sqrt{L}n^{1.5}+\sqrt{L}n\log^2L\log^2n)$ の量子アルゴリズムを示す。
関連論文リスト
- 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) - 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) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Quantum Algorithm for the Shortest Superstring Problem [0.0]
我々は、最短スーパーストリング問題(SSP)または最短共通スーパーストリング問題(SCS)を考える。
論文 参考訳（メタデータ） (2021-12-26T05:37:56Z) - Quantum Algorithms for String Processing [58.720142291102135]
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。
第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
論文 参考訳（メタデータ） (2020-12-01T09:59:06Z) - 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) - Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文 参考訳（メタデータ） (2020-05-28T22:44:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。