Fugu-MT 論文翻訳(概要): Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems

論文の概要: Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems

arxiv url: http://arxiv.org/abs/2010.12122v2
Date: Tue, 24 May 2022 03:19:41 GMT
ステータス: 処理完了
システム内更新日: 2023-04-27 22:58:16.935298
Title: Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
Title（参考訳）: 量子はきめ細かい複雑さを満たす - 弦問題に対する部分線形時間量子アルゴリズム
Authors: Fran\c{c}ois Le Gall and Saeed Seddighin
Abstract要約: 最も長いコモン(LCS)、長いパリンドローム(LPS)、そしてウルム距離(UL)は、古典的に線形に近い時間で解くことができる3つの基本弦問題である。これらの問題に対する線形時間量子アルゴリズムと量子下界について述べる。
参考スコア（独自算出の注目度）: 5.490993287665715
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for LCS and LPS are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact $\tilde O(\sqrt{n})$ time algorithm for LPS, we prove that LCS needs at least time $\tilde \Omega(n^{2/3})$ even for 0/1 strings.
Abstract（参考訳）: 最も長いコモン・サブストリング(LCS)、長いパリンドローム・サブストリング(LPS)、ウルム距離(UL)は古典的に線形に近い時間で解くことができる3つの基本弦問題である。本研究では,これらの問題に対する線形時間量子アルゴリズムと量子下界について述べる。 LCSとLPSの古典的な解はほぼ同じ(接尾辞木による)が、それらの量子計算の複雑さは異なる。 LPS に対して正確な $\tilde O(\sqrt{n})$ time アルゴリズムを与えるが、LCS が 0/1 の弦に対してさえ少なくとも $\tilde \Omega(n^{2/3})$ を必要とすることを証明している。

関連論文リスト

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)
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)
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)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文参考訳（メタデータ） (2022-12-06T22:01:49Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文参考訳（メタデータ） (2022-05-26T20:32:36Z)
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 Algorithms for String Processing [58.720142291102135]
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
論文参考訳（メタデータ） (2020-12-01T09:59:06Z)
Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文参考訳（メタデータ） (2020-04-14T11:05:26Z)

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