Fugu-MT 論文翻訳(概要): Quantum Algorithm for the Shortest Superstring Problem

論文の概要: Quantum Algorithm for the Shortest Superstring Problem

arxiv url: http://arxiv.org/abs/2112.13319v1
Date: Sun, 26 Dec 2021 05:37:56 GMT
ステータス: 処理完了
システム内更新日: 2021-12-28 16:47:49.204472
Title: Quantum Algorithm for the Shortest Superstring Problem
Title（参考訳）: 最短超弦問題に対する量子アルゴリズム
Authors: Kamil Khadiev and Carlos Manuel Bosch Machado
Abstract要約: 我々は、最短スーパーストリング問題(SSP)または最短共通スーパーストリング問題(SCS)を考える。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we consider the ``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring Problem''(SCS). The problem is as follows. For a positive integer $n$, a sequence of n strings $S=(s^1,\dots,s^n)$ is given. We should construct the shortest string $t$ (we call it superstring) that contains each string from the given sequence as a substring. The problem is connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. We present a quantum algorithm with running time $O^*(1.728^n)$. Here $O^*$ notation does not consider polynomials of $n$ and the length of $t$.
Abstract（参考訳）: 本稿では,「Shortest Superstring Problem」 (SSP) や「Shortest Common Superstring Problem」 (SCS) を考える。問題は次の通りである。正の整数 $n$ に対して、n 個の文字列の列 $S=(s^1,\dots,s^n)$ が与えられる。与えられたシーケンスの各文字列をサブ文字列として含む最も短い文字列$t$(superstringと呼ぶ)を構築するべきです。この問題は、小さな断片から長いDNA配列を再構成する配列組立法と関係している。実行時間$O^*(1.728^n)$とする量子アルゴリズムを提案する。ここで、$O^*$表記は$n$の多項式と$t$の長さを考慮しない。

関連論文リスト

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)
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)
Can You Solve Closest String Faster than Exhaustive Search? [4.963483138661772]
与えられた集合を表すのに最適な文字列を見つけるという根本的な問題を研究する。本稿では,最も近い文字列問題は,自明な網羅的探索アルゴリズムよりも高速なアルゴリズムを許容するかどうかを考察する。
論文参考訳（メタデータ） (2023-05-26T12:30:16Z)
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)
The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-19T16:04:40Z)
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 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)

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