論文の概要: A note about claw function with a small range
- arxiv url: http://arxiv.org/abs/2103.16390v1
- Date: Tue, 30 Mar 2021 14:30:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-06 03:41:03.512636
- Title: A note about claw function with a small range
- Title(参考訳): 狭い範囲の爪関数についての一考察
- Authors: Andris Ambainis, Kaspars Balodis, J\=anis Iraids
- Abstract要約: この問題の量子クエリの複雑さは、$Omegaleft(n1/2k1/6right)$と$Oleft(n1/2+varepsilonk1/4right)$の間である。
- 参考スコア(独自算出の注目度): 1.2246649738388389
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the claw detection problem we are given two functions $f:D\rightarrow R$
and $g:D\rightarrow R$ ($|D|=n$, $|R|=k$), and we have to determine if there is
exist $x,y\in D$ such that $f(x)=g(y)$. We show that the quantum query
complexity of this problem is between $\Omega\left(n^{1/2}k^{1/6}\right)$ and
$O\left(n^{1/2+\varepsilon}k^{1/4}\right)$ when $2\leq k<n$.
- Abstract(参考訳): 爪検出問題では、$f:D\rightarrow R$と$g:D\rightarrow R$(|D|=n$, $|R|=k$)の2つの関数が与えられ、$f が存在するかどうかを判断する必要がある。
(x)=g
(y)$。
この問題の量子クエリの複雑さは、$Omega\left(n^{1/2}k^{1/6}\right)$と$O\left(n^{1/2+\varepsilon}k^{1/4}\right)$の間にある。
関連論文リスト
- On the quantum Guerra-Morato Action Functional [0.0]
トーラス上のmathbbR$に対して滑らかなポテンシャル W:mathrmTn が与えられたとき、量子ゲラ・モラート作用函数はスモールスキップによって与えられる。
臨界解の第二変量に対する表現は、スモールスキップによって与えられることを示す。
論文 参考訳(メタデータ) (2024-03-09T10:30:21Z) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳(メタデータ) (2024-02-23T12:22:03Z) - Matrix concentration inequalities and efficiency of random universal
sets of quantum gates [0.0]
ランダム集合 $mathcalS の部分集合 U(d)$ に対して、$mathcalS$ が $delta$-approximate $t$-design となる確率の有界性を与える。
正確な$t$-designから引き出された$mathcalS$に対して、$delta$-approximate $t$-designが不等式$mathbbPleft(delta geq x right)leq 2D_tを満たす確率を示す。
論文 参考訳(メタデータ) (2022-02-10T23:44:09Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳(メタデータ) (2021-09-21T13:19:04Z) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳(メタデータ) (2021-06-25T19:14:45Z) - Breaking The Dimension Dependence in Sparse Distribution Estimation
under Communication Constraints [18.03695167610009]
サンプルサイズ$n$が最低しきい値$n*(s, d, b)$を超えると、$Oleft( fracsn2bright)$の$ell$推定誤差を達成できることを示す。
対話的な設定のために,新しい木に基づく推定手法を提案し,次元自由収束を実現するために必要な最小サンプルサイズを,さらに$n*(s, d, b)$に縮めることを示した。
論文 参考訳(メタデータ) (2021-06-16T07:52:14Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳(メタデータ) (2021-03-17T18:18:57Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳(メタデータ) (2020-02-17T18:41:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。