論文の概要: Near-Optimal Quantum Algorithms for String Problems
- arxiv url: http://arxiv.org/abs/2110.09696v2
- Date: Wed, 20 Oct 2021 23:47:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 02:14:35.175383
- Title: Near-Optimal Quantum Algorithms for String Problems
- Title（参考訳）: 文字列問題に対する近似量子アルゴリズム
- Authors: Shyan Akmal, Ce Jin
- Abstract要約: ほぼ最適なクエリ複雑度と時間複雑度を持つ基本文字列問題に対する量子アルゴリズムを提案する。
これらの問題には、Longest Common Substring、Lexicographically Minimal String Rotation、Longest Square Substringが含まれる。
我々の手法は、Longest Repeated Substring、Longest Lyndon Substring、Minimmal Suffixといった他の関連する文字列問題に自然に拡張する。
- 参考スコア（独自算出の注目度）: 0.5736353542430439
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study quantum algorithms for several fundamental string problems,
including Longest Common Substring, Lexicographically Minimal String Rotation,
and Longest Square Substring. These problems have been widely studied in the
stringology literature since the 1970s, and are known to be solvable by
near-linear time classical algorithms. In this work, we give quantum algorithms
for these problems with near-optimal query complexities and time complexities.
Specifically, we show that:
- Longest Common Substring can be solved by a quantum algorithm in $\tilde
O(n^{2/3})$ time, improving upon the recent $\tilde O(n^{5/6})$-time algorithm
by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk
framework, together with a careful combination of string synchronizing sets
(Kempa and Kociumaka, 2019) and generalized difference covers.
- Lexicographically Minimal String Rotation can be solved by a quantum
algorithm in $n^{1/2 + o(1)}$ time, improving upon the recent $\tilde
O(n^{3/4})$-time algorithm by Wang and Ying (2020). We design our algorithm by
first giving a new classical divide-and-conquer algorithm in near-linear time
based on exclusion rules, and then speeding it up quadratically using nested
Grover search and quantum minimum finding.
- Longest Square Substring can be solved by a quantum algorithm in $\tilde
O(\sqrt{n})$ time. Our algorithm is an adaptation of the algorithm by Le Gall
and Seddighin (2020) for the Longest Palindromic Substring problem, but uses
additional techniques to overcome the difficulty that binary search no longer
applies.
Our techniques naturally extend to other related string problems, such as
Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.
- Abstract（参考訳）: 本稿では,Longest Common Substring,Lexicographically Minimal String Rotation,Longest Square Substringなどの基本的な文字列問題に対する量子アルゴリズムについて検討する。
これらの問題は1970年代から弦学の文献で広く研究され、ほぼ線形の古典的アルゴリズムで解けることが知られている。
本研究では,これらの問題に対して,最適に近い問合せの複雑度と時間的複雑度を持つ量子アルゴリズムを与える。
特に、最も長い共通部分文字列は$\tilde o(n^{2/3})$ time の量子アルゴリズムによって解くことができ、le gall と seddighin (2020) による最近の$\tilde o(n^{5/6})$-timeアルゴリズムにより改善される。
我々のアルゴリズムは、MNRS量子ウォークフレームワークと、文字列同期セット(Kempa and Kociumaka, 2019)と一般化差分カバーの慎重に組み合わせたものである。
- 辞書学的に最小の弦回転は、wang and ying (2020)による最近の$\tilde o(n^{3/4})$-timeアルゴリズムの改善により、量子アルゴリズムによって解くことができる。
まず, 排他規則に基づく近似時間に新しい古典的除算・解法を付与し, ネストグローバー探索と量子最小探索を用いて二次的に解法を高速化する。
- 最長の平方部分文字列は、$\tilde o(\sqrt{n})$ time で量子アルゴリズムによって解くことができる。
提案アルゴリズムは,Longest Palindromic Substring問題に対するLe GallとSeddighin (2020)によるアルゴリズムの適応であるが,二分探索が適用しない難しさを克服するために追加手法を用いる。
我々の手法は、Longest Repeated Substring、Longest Lyndon Substring、Minimmal Suffixといった他の関連する文字列問題に自然に拡張する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - 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) - Longest Common Substring and Longest Palindromic Substring in
$\tilde{\mathcal{O}}(\sqrt{n})$ Time [0.0]
LCS(Longest Common Substring)とLPS(Longest Palindromic Substring)は、コンピュータ科学における古典的な問題である。
計算回路モデルにおいて, LCS と LPS の双方に対する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-03T19:27:57Z) - 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) - 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) - 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 Algorithms for String Processing [58.720142291102135]
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。
第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
論文 参考訳（メタデータ） (2020-12-01T09:59:06Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。