論文の概要: 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)最長の共通部分列。
関連論文リスト
- Quantum Algorithm for the Multiple String Matching Problem [0.0]
我々は$m$文字列のシーケンスを$S$と表現し、それを辞書と呼ぶ。
目的は、テキスト内の辞書から文字列のすべてのインスタンスを特定することである。
我々は,$O(n+sqrtmLlog nlog n)$クエリ複雑性と$O(n+sqrtmLlog n)=O*(n+sqrtmL)$タイム複雑性を持つ量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-22T10:50:43Z) - 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) - 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) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language [0.0]
本稿では,2つのパリンドロムを結合した文脈自由言語を認識するための量子特性試験アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-17T07:19:20Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。