論文の概要: Quantum Algorithms for the Most Frequently String Search, Intersection
of Two String Sequences and Sorting of Strings Problems
- arxiv url: http://arxiv.org/abs/2001.01914v1
- Date: Tue, 7 Jan 2020 07:22:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-13 21:19:01.682810
- Title: Quantum Algorithms for the Most Frequently String Search, Intersection
of Two String Sequences and Sorting of Strings Problems
- Title（参考訳）: 最も頻度の高い文字列探索、二つの文字列列の交叉、文字列問題のソートのための量子アルゴリズム
- Authors: Kamil Khadiev and Artem Ilikaev
- Abstract要約: 弦の3つの問題を解くアルゴリズムについて研究する。
1つ目は、最も頻度の高い文字列検索問題である。
2つ目は、2つの弦列の交叉である。
第三の問題は長さ$k$の$n$文字列をソートすることだ。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study algorithms for solving three problems on strings. The first one is
the Most Frequently String Search Problem. The problem is the following. Assume
that we have a sequence of $n$ strings of length $k$. The problem is finding
the string that occurs in the sequence most often. We propose a quantum
algorithm that has a query complexity $\tilde{O}(n \sqrt{k})$. This algorithm
shows speed-up comparing with the deterministic algorithm that requires
$\Omega(nk)$ queries. The second one is searching intersection of two sequences
of strings. All strings have the same length $k$. The size of the first set is
$n$ and the size of the second set is $m$. We propose a quantum algorithm that
has a query complexity $\tilde{O}((n+m) \sqrt{k})$. This algorithm shows
speed-up comparing with the deterministic algorithm that requires
$\Omega((n+m)k)$ queries. The third problem is sorting of $n$ strings of length
$k$. On the one hand, it is known that quantum algorithms cannot sort objects
asymptotically faster than classical ones. On the other hand, we focus on
sorting strings that are not arbitrary objects. We propose a quantum algorithm
that has a query complexity $O(n (\log n)^2 \sqrt{k})$. This algorithm shows
speed-up comparing with the deterministic algorithm (radix sort) that requires
$\Omega((n+d)k)$ queries, where $d$ is a size of the alphabet.
- Abstract（参考訳）: 我々は弦の3つの問題を解決するアルゴリズムを勉強する。
1つ目は、文字列検索の最も頻繁な問題である。
問題は以下のとおりである。
長さ$k$の$n$文字列列があると仮定する。
問題は、シーケンスで最も頻繁に発生する文字列を見つけることだ。
我々は,クエリの複雑性$\tilde{o}(n \sqrt{k})$を持つ量子アルゴリズムを提案する。
このアルゴリズムは$\omega(nk)$クエリを必要とする決定論的アルゴリズムと比較するスピードアップを示す。
2つ目は、2つの弦列の交叉である。
すべての文字列は同じ長さの$k$を持つ。
最初のセットのサイズは$n$で、2番目のセットのサイズは$m$である。
クエリ複雑性を$\tilde{O}((n+m) \sqrt{k})$とする量子アルゴリズムを提案する。
このアルゴリズムは、$\Omega((n+m)k)$クエリを必要とする決定論的アルゴリズムと比較したスピードアップを示す。
第3の問題は、長さ$k$の文字列をソートすることだ。
一方、量子アルゴリズムは古典的アルゴリズムよりも漸近的に高速に物体を分類できないことが知られている。
一方、任意のオブジェクトではない文字列のソートに重点を置いている。
我々は,クエリの複雑性$o(n (\log n)^2 \sqrt{k})$を持つ量子アルゴリズムを提案する。
このアルゴリズムは、$d$がアルファベットのサイズである$\omega((n+d)k)$クエリを必要とする決定論的アルゴリズム(radix sort)と比較するスピードアップを示す。
関連論文リスト
- 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) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - 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) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Quantum Algorithms for String Processing [58.720142291102135]
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。
第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
論文 参考訳（メタデータ） (2020-12-01T09:59:06Z) - 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) - Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文 参考訳（メタデータ） (2020-05-28T22:44:01Z) - Resonant Quantum Search with Monitor Qubits [0.0]
連続的ハミルトニアンと共振を利用した一般化探索問題($N$項目中$k$マークされた項目を探索する)のアルゴリズムを提案する。
この共振アルゴリズムはGroverアルゴリズムと同じ時間複雑性$O(sqrtN/k)$を持つ。
論文 参考訳（メタデータ） (2020-02-21T19:31:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。