論文の概要: The quantum query complexity of composition with a relation
- arxiv url: http://arxiv.org/abs/2004.06439v1
- Date: Tue, 14 Apr 2020 12:07:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 08:47:37.263887
- Title: The quantum query complexity of composition with a relation
- Title（参考訳）: 関係を持つ合成の量子的クエリ複雑性
- Authors: Aleksandrs Belovs and Troy Lee
- Abstract要約: Belovs は負の重み付け逆法の修正版 $mathrmADV_relpm(f)$ を与えた。
関係が効率よく検証できる:$mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$。
- 参考スコア（独自算出の注目度）: 78.55044112903148
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The negative weight adversary method, $\mathrm{ADV}^\pm(g)$, is known to
characterize the bounded-error quantum query complexity of any Boolean function
$g$, and also obeys a perfect composition theorem $\mathrm{ADV}^\pm(f \circ
g^n) = \mathrm{ADV}^\pm(f) \mathrm{ADV}^\pm(g)$. Belovs gave a modified version
of the negative weight adversary method, $\mathrm{ADV}_{rel}^\pm(f)$, that
characterizes the bounded-error quantum query complexity of a relation $f
\subseteq \{0,1\}^n \times [K]$, provided the relation is efficiently
verifiable. A relation is efficiently verifiable if $\mathrm{ADV}^\pm(f_a) =
o(\mathrm{ADV}_{rel}^\pm(f))$ for every $a \in [K]$, where $f_a$ is the Boolean
function defined as $f_a(x) = 1$ if and only if $(x,a) \in f$. In this note we
show a perfect composition theorem for the composition of a relation $f$ with a
Boolean function $g$ \[ \mathrm{ADV}_{rel}^\pm(f \circ g^n) =
\mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) \enspace . \] For an efficiently
verifiable relation $f$ this means $Q(f \circ g^n) = \Theta(
\mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) )$.
- Abstract（参考訳）: 負重み逆法、$\mathrm{adv}^\pm
(g)$は任意のブール関数$g$の有界エラー量子クエリ複雑性を特徴づけることが知られており、完全合成定理$\mathrm{ADV}^\pm(f \circ g^n) = \mathrm{ADV}^\pmに従う。
(f) \mathrm{ADV}^\pm
(g)$。
belovs は、負の重み逆法である $\mathrm{adv}_{rel}^\pm の修正版を与えた。
(f)$は、関係が効率よく検証できるならば、関係$f \subseteq \{0,1\}^n \times [K]$の有界エラー量子クエリ複雑性を特徴付ける。
関係が効率よく検証できるのは、$\mathrm{ADV}^\pm(f_a) = o(\mathrm{ADV}_{rel}^\pm
(f))$ for every $a \in [k]$, ここで$f_a$ は$f_a(x) = 1$ if and only if $(x,a) \in f$ と定義されるブール関数である。
この注記では、ブール函数 {g$ \[ \mathrm{adv}_{rel}^\pm(f \circ g^n) = \mathrm{adv}_{rel}^\pm を持つ関係の合成に対する完全合成定理を示す。
(f) \mathrm{ADV}^\pm
(g) 空間 。
これは$q(f \circ g^n) = \theta( \mathrm{adv}_{rel}^\pm を意味する。
(f) \mathrm{ADV}^\pm
(g)$。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳（メタデータ） (2023-02-26T02:42:39Z) - Matching upper bounds on symmetric predicates in quantum communication
complexity [0.0]
共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。
我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
論文 参考訳（メタデータ） (2023-01-01T08:30:35Z) - $\mathcal{P}\mathcal{T}$-symmetric $-g\varphi^4$ theory [0.0]
エルミート理論は次のようになる: $log ZmathcalPmathcalT(g)=textstylefrac12 log Z_rm Herm(-g+rm i 0+rm i 0+$。
ユークリッド分割関数 $ZmathcalPmathcalT$-symmetric theory と $lambda varphi4$ の $Z_rm Herm(lambda)$ の新たな導出関係が提示される。
論文 参考訳（メタデータ） (2022-09-16T12:44:00Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Degree vs. Approximate Degree and Quantum Implications of Huang's
Sensitivity Theorem [4.549831511476248]
すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。
f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
論文 参考訳（メタデータ） (2020-10-23T19:21:28Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。