論文の概要: Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model
- arxiv url: http://arxiv.org/abs/2112.13005v3
- Date: Mon, 6 Feb 2023 14:13:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-03 09:13:41.311557
- Title: Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model
- Title（参考訳）: ワードQRAMモデルを用いた距離編集のための量子線形アルゴリズム
- Authors: Massimo Equi, Arianne Meijer-van de Griend, Veli M\"akinen
- Abstract要約: 2次時間分解可能問題のビット並列性を、係数$n$でスピードアップできる量子アルゴリズムに変換する方法を示す。
まず、Myers (J. ACM, 1999) の有名な$O(n2/w)$ time bit-parallel アルゴリズムが算術+演算なしで動作するように調整可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many problems that can be solved in quadratic time have bit-parallel
speed-ups with factor $w$, where $w$ is the computer word size. For example,
edit distance of two strings of length $n$ can be solved in $O(n^2/w)$ time. In
a reasonable classical model of computation, one can assume $w=\Theta(\log n)$.
There are conditional lower bounds for such problems stating that speed-ups
with factor $n^\epsilon$ for any $\epsilon>0$ would lead to breakthroughs in
complexity theory. However, these conditional lower bounds do not cover quantum
models of computing. Indeed, Boroujeni et al. (J. ACM, 2021) showed that edit
distance can be approximated within a factor $3$ in sub-quadratic time
$O(n^{1.81})$ using quantum computing. They also showed that, in their chosen
model of quantum computing, the approximation factor cannot be improved using
sub-quadractic time.
To break through the aforementioned classical conditional lower bounds and
this latest quantum lower bound, we enrich the model of computation with a
quantum random access memory (QRAM), obtaining what we call the word QRAM
model. Under this model, we show how to convert the bit-parallelism of
quadratic time solvable problems into quantum algorithms that attain speed-ups
with factor $n$. The technique we use is simple and general enough to apply to
many bit-parallel algorithms that use Boolean logics and bit-shifts. To apply
it to edit distance, we first show that the famous $O(n^2/w)$ time bit-parallel
algorithm of Myers (J. ACM, 1999) can be adjusted to work without arithmetic +
operations. As a direct consequence of applying our technique to this variant,
we obtain linear time edit distance algorithm under the word QRAM model for
constant alphabet. We give further results on a restricted variant of the word
QRAM model to give more insights to the limits of the model.
- Abstract（参考訳）: 二次時間で解ける多くの問題は、ビット並列のスピードアップが$w$で、$w$はコンピュータワードサイズである。
例えば、長さ$n$の2つの文字列の編集距離は$O(n^2/w)$時間で解ける。
合理的な古典的計算モデルでは、$w=\theta(\log n)$ と仮定できる。
そのような問題には条件付き下限があり、任意の$\epsilon>0$に対して$n^\epsilon$のスピードアップは複雑性理論のブレークスルーにつながる。
しかし、これらの条件付き下限は計算の量子モデルには適用されない。
実際、Boroujeni et al. (J. ACM, 2021) は、量子コンピューティングを用いてサブクアッドレート時間$O(n^{1.81})$で編集距離を3ドル以内で近似できることを示した。
彼らはまた、選択した量子コンピューティングモデルでは、近似係数は準四次時間では改善できないことを示した。
上記の古典的条件付き下界と、この最新の量子的下界を分解するために、量子ランダムアクセスメモリ(QRAM)を用いて計算モデルを強化し、私たちが「QRAMモデル」と呼ぶものを得る。
このモデルでは、2次時間分解可能問題のビット並列性を、係数$n$で高速化できる量子アルゴリズムに変換する方法を示す。
Booleanロジックとビットシフトを使用する多くのビット並列アルゴリズムに適用するには,我々が使用するテクニックはシンプルで汎用的です。
これを編集距離に適用するために、Myers (J. ACM, 1999) の有名な$O(n^2/w)$ time bit-parallel アルゴリズムが算術+演算なしで動作できるように調整可能であることを示す。
この変種に我々の技術を適用する直接的な結果として、定数アルファベットに対する単語QRAMモデルの下で線形時間編集距離アルゴリズムを得る。
我々は、qramモデルの制限された変形についてさらなる結果を与え、モデルの限界に関する洞察を与える。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - 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 State Learning Implies Circuit Lower Bounds [2.2667044928324747]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv
Factorization [2.684542790908823]
我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。
2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
論文 参考訳（メタデータ） (2023-11-03T09:09:23Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - 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) - What limits the simulation of quantum computers? [5.22339562024796]
実際の量子コンピュータは、完全量子コンピュータに必要なわずかなコストでシミュレートできることを実証する。
我々のアルゴリズムは、行列積状態(MPS)を用いて量子波動関数の表現を圧縮し、低から中程度の絡み合いの状態を非常に正確に捉える。
N=54$ qubits の2次元配列と Control-Z ゲートを持つ回路では、最先端のデバイスよりも数時間でエラー率を得ることができる。
論文 参考訳（メタデータ） (2020-02-18T17:00:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。