論文の概要: Quantum divide and conquer
- arxiv url: http://arxiv.org/abs/2210.06419v1
- Date: Wed, 12 Oct 2022 17:14:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-22 19:35:33.229921
- Title: Quantum divide and conquer
- Title(参考訳): 量子分割と征服
- Authors: Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram,
Daochen Wang
- Abstract要約: Divide-and-conquerフレームワークは、古典的なアルゴリズム設計で広く使われている。
C_Q(n) leq sqrta, C_Q(n/b) + O(Ctextrmaux_Q(n))$$ の類似反復関係を生じる量子分割・量子化フレームワークについて述べる。
- 参考スコア(独自算出の注目度): 6.527258283771695
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The divide-and-conquer framework, used extensively in classical algorithm
design, recursively breaks a problem of size $n$ into smaller subproblems (say,
$a$ copies of size $n/b$ each), along with some auxiliary work of cost
$C^{\textrm{aux}}(n)$, to give a recurrence relation $$C(n) \leq a \, C(n/b) +
C^{\textrm{aux}}(n)$$ for the classical complexity $C(n)$. We describe a
quantum divide-and-conquer framework that, in certain cases, yields an
analogous recurrence relation $$C_Q(n) \leq \sqrt{a} \, C_Q(n/b) +
O(C^{\textrm{aux}}_Q(n))$$ that characterizes the quantum query complexity. We
apply this framework to obtain near-optimal quantum query complexities for
various string problems, such as (i) recognizing regular languages; (ii)
decision versions of String Rotation and String Suffix; and natural
parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest
Common Subsequence.
- Abstract(参考訳): 古典的アルゴリズム設計で広く使われている分数分解フレームワークは、$n$の問題をより小さなサブプロブレムに再帰的に分解する(例:$a$ copy of size $n/b$ each)とともに、コスト$C^{\textrm{aux}}(n)$の補助的な作業により、古典的複雑性の$C(n)$に対して$C(n) \leq a \, C(n/b) + C^{\textrm{aux}}(n)$の繰り返し関係を与える。
我々は、ある場合において、類似の反復関係 $$c_q(n) \leq \sqrt{a} \, c_q(n/b) + o(c^{\textrm{aux}}_q(n))$$$ が量子クエリの複雑性を特徴付けるような量子分割・変換フレームワークを記述する。
このフレームワークを用いて,文字列問題に対する近似量子問合せの複雑度を求める。
(i)正規言語を認識すること
(ii)String RotationとString Suffixの決定バージョン、および自然パラメータ化バージョン
(iii)最長増分、及び
(iv)最長の共通部分列。
関連論文リスト
- 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-08-18T17:52:12Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳(メタデータ) (2023-06-02T17:49:35Z) - 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 Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - 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) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳(メタデータ) (2021-05-18T06:51:11Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳(メタデータ) (2021-04-29T14:50:03Z) - 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) - Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文 参考訳(メタデータ) (2020-05-28T22:44:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。