論文の概要: 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モデルの制限された変形についてさらなる結果を与え、モデルの限界に関する洞察を与える。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - 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) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳(メタデータ) (2023-06-02T17:49:35Z) - 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) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳(メタデータ) (2022-01-06T03:10:53Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳(メタデータ) (2020-12-03T14:03:20Z) - 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) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳(メタデータ) (2020-02-25T19:18:36Z) - What limits the simulation of quantum computers? [5.22339562024796]
実際の量子コンピュータは、完全量子コンピュータに必要なわずかなコストでシミュレートできることを実証する。
我々のアルゴリズムは、行列積状態(MPS)を用いて量子波動関数の表現を圧縮し、低から中程度の絡み合いの状態を非常に正確に捉える。
N=54$ qubits の2次元配列と Control-Z ゲートを持つ回路では、最先端のデバイスよりも数時間でエラー率を得ることができる。
論文 参考訳(メタデータ) (2020-02-18T17:00:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。