論文の概要: Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization

• arxiv url: http://arxiv.org/abs/2311.01793v1
• Date: Fri, 3 Nov 2023 09:09:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-06 14:32:40.163076
• Title: Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
• Title（参考訳）: 境界編集距離とLempel-Ziv因子分解のための近似量子アルゴリズム
• Authors: Daniel Gibney, Ce Jin, Tomasz Kociumaka, Sharma V. Thankachan
• Abstract要約: 我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。 2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
• 参考スコア（独自算出の注目度）: 2.684542790908823
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Classically, the edit distance of two length-$n$ strings can be computed in $O(n^2)$ time, whereas an $O(n^{2-\epsilon})$-time procedure would falsify the Orthogonal Vectors Hypothesis. If the edit distance does not exceed $k$, the running time can be improved to $O(n+k^2)$, which is near-optimal (conditioned on OVH) as a function of $n$ and $k$. Our first main contribution is a quantum $\tilde{O}(\sqrt{nk}+k^2)$-time algorithm that uses $\tilde{O}(\sqrt{nk})$ queries, where $\tilde{O}(\cdot)$ hides polylogarithmic factors. This query complexity is unconditionally optimal, and any significant improvement in the time complexity would resolve a long-standing open question of whether edit distance admits an $O(n^{2-\epsilon})$-time quantum algorithm. Our divide-and-conquer quantum algorithm reduces the edit distance problem to a case where the strings have small Lempel-Ziv factorizations. Then, it combines a quantum LZ compression algorithm with a classical edit-distance subroutine for compressed strings. The LZ factorization problem can be classically solved in $O(n)$ time, which is unconditionally optimal in the quantum setting. We can, however, hope for a quantum speedup if we parameterize the complexity in terms of the factorization size $z$. Already a generic oracle identification algorithm yields the optimal query complexity of $\tilde{O}(\sqrt{nz})$ at the price of exponential running time. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $\tilde{O}(\sqrt{nz})$. The key tool is a novel LZ-like factorization of size $O(z\log^2n)$ whose subsequent factors can be efficiently computed through a combination of classical and quantum techniques. We can then obtain the string's run-length encoded Burrows-Wheeler Transform (BWT), construct the $r$-index, and solve many fundamental string processing problems in time $\tilde{O}(\sqrt{nz})$.
• Abstract（参考訳）: 古典的には、2つの長さ=n$文字列の編集距離は$o(n^2)$時間で計算できるが、$o(n^{2-\epsilon})$-time 手順は直交ベクトル仮説を偽る。 もし編集距離が$k$を超えない場合、実行時間は$n$と$k$の関数としてほぼ最適(ovhで条件付)である$o(n+k^2)$に改善できる。 私たちの最初の貢献は、$\tilde{O}(\sqrt{nk}+k^2)$-timeアルゴリズムで、$\tilde{O}(\sqrt{nk})$クエリを使用します。 このクエリの複雑さは無条件で最適であり、編集距離が$O(n^{2-\epsilon})$-time量子アルゴリズムを許容するかどうかという長年にわたるオープンな疑問を、時間的複雑さで解決する。 我々の分母量子アルゴリズムは、編集距離問題を、文字列が小さなLempel-Ziv分解を持つケースに還元する。 そして、量子LZ圧縮アルゴリズムと圧縮文字列に対する古典的な編集距離サブルーチンを組み合わせる。 lz因子分解問題は古典的に o(n)$ 時間で解くことができ、量子設定では無条件に最適である。 しかし、因子化サイズ$z$という観点で複雑さをパラメータ化すれば、量子速度アップを期待できる。 一般的なオラクル識別アルゴリズムはすでに、指数的実行時間の価格で$\tilde{O}(\sqrt{nz})$の最適なクエリ複雑性が得られる。 2つ目の貢献は、$\tilde{O}(\sqrt{nz})$の最適時間複雑性を達成する量子アルゴリズムである。 鍵となるツールは、新しい lz-like factorization of size $o(z\log^2n)$ であり、それに続く因子は古典的手法と量子的手法の組み合わせによって効率的に計算できる。 次に、文字列の実行長エンコードされたBurrows-Wheeler変換(BWT)を取得し、$r$-indexを構築し、時間$\tilde{O}(\sqrt{nz})$で多くの基本的な文字列処理問題を解く。

関連論文リスト

• Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching [2.4167127333650202]
  パターンマッチングにおけるハミング距離と、編集によるパターンマッチングにおける編集距離の2つを考える。 時間的複雑性は$tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatchesと$hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Editsである。
  論文  参考訳（メタデータ） (2024-10-09T12:05:26Z)
• 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)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
  二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。 このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
  論文  参考訳（メタデータ） (2023-02-06T15: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)
• 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)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。 本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
  論文  参考訳（メタデータ） (2021-05-18T06:51:11Z)
• 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)
• 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)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。