論文の概要: From Bit-Parallelism to Quantum String Matching for Labelled Graphs
- arxiv url: http://arxiv.org/abs/2302.02848v2
- Date: Fri, 14 Apr 2023 12:40:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-17 16:16:44.820395
- Title: From Bit-Parallelism to Quantum String Matching for Labelled Graphs
- Title（参考訳）: ビットパラレルからラベリンググラフの量子文字列マッチングへ
- Authors: Massimo Equi, Arianne Meijer - van de Griend, Veli M\"akinen
- Abstract要約: 二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
- 参考スコア（独自算出の注目度）: 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. A classic
example is computing the edit distance of two strings of length $n$, which can
be solved in $O(n^2/w)$ time. In a reasonable classical model of computation,
one can assume $w=\Theta(\log n)$, and obtaining significantly better speed-ups
is unlikely in the light of conditional lower bounds obtained for such
problems. In this paper, we study the connection of bit-parallelism to quantum
computation, aiming to see if a bit-parallel algorithm could be converted to a
quantum algorithm with better than logarithmic speed-up. We focus on string
matching in labeled graphs, the problem of finding an exact occurrence of a
string as the label of a path in a graph. This problem admits a quadratic
conditional lower bound under a very restricted class of graphs (Equi et al.
ICALP 2019), stating that no algorithm in the classical model of computation
can solve the problem in time $O(|P||E|^{1-\epsilon})$ or
$O(|P|^{1-\epsilon}|E|)$. We show that a simple bit-parallel algorithm on such
restricted family of graphs (level DAGs) can indeed be converted into a
realistic quantum algorithm that attains subquadratic time complexity
$O(|E|\sqrt{|P|})$.
- Abstract（参考訳）: 二次時間で解ける多くの問題は、ビット並列のスピードアップが$w$で、$w$はコンピュータワードサイズである。
古典的な例は長さ$n$の2つの文字列の編集距離を計算し、これは$O(n^2/w)$時間で解ける。
合理的な古典的計算モデルでは、$w=\theta(\log n)$ と仮定でき、そのような問題に対して条件付き下界を考えると、より優れたスピードアップが得られる可能性は低い。
本稿では,ビット並列アルゴリズムが対数的高速化よりも優れた量子アルゴリズムに変換できるかどうかを確かめるため,ビット並列と量子計算の関連性を検討する。
我々は,グラフ内のパスのラベルとして文字列の正確な発生を見つける問題であるラベル付きグラフにおける文字列マッチングに注目した。
この問題は、非常に制限されたグラフのクラス(Equi et al. ICALP 2019)の下での二次条件付き下界を認めており、古典的な計算モデルにおけるアルゴリズムは、時間$O(|P||E|^{1-\epsilon})$または$O(|P|^{1-\epsilon}|E|)$でこの問題を解くことができない。
このような制限付きグラフ群(レベル dag)上の単純なビット並列アルゴリズムは、実際、準二次時間複雑性$o(|e|\sqrt{|p|})$となるような現実的な量子アルゴリズムに変換できる。
関連論文リスト
- Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - 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) - 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) - 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) - Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model [0.0]
2次時間分解可能問題のビット並列性を、係数$n$でスピードアップできる量子アルゴリズムに変換する方法を示す。
まず、Myers (J. ACM, 1999) の有名な$O(n2/w)$ time bit-parallel アルゴリズムが算術+演算なしで動作するように調整可能であることを示す。
論文 参考訳（メタデータ） (2021-12-24T09:26:55Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Classical algorithms for Forrelation [2.624902795082451]
1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。
この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。
グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
論文 参考訳（メタデータ） (2021-02-13T17:25:41Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。