論文の概要: $k$-Forrelation Optimally Separates Quantum and Classical Query
Complexity
- arxiv url: http://arxiv.org/abs/2008.07003v3
- Date: Tue, 17 Nov 2020 14:51:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-06 03:10:51.097625
- Title: $k$-Forrelation Optimally Separates Quantum and Classical Query
Complexity
- Title（参考訳）: k$-forrelationは量子と古典的なクエリの複雑さを最適に分離する
- Authors: Nikhil Bansal and Makrand Sinha
- Abstract要約: 我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。
我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
- 参考スコア（独自算出の注目度）: 3.4984289152418753
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Aaronson and Ambainis (SICOMP `18) showed that any partial function on $N$
bits that can be computed with an advantage $\delta$ over a random guess by
making $q$ quantum queries, can also be computed classically with an advantage
$\delta/2$ by a randomized decision tree making
${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries. Moreover, they conjectured the
$k$-Forrelation problem -- a partial function that can be computed with $q =
\lceil k/2 \rceil$ quantum queries -- to be a suitable candidate for exhibiting
such an extremal separation.
We prove their conjecture by showing a tight lower bound of
$\widetilde{\Omega}(N^{1-1/k})$ for the randomized query complexity of
$k$-Forrelation, where the advantage $\delta = 2^{-O(k)}$. By standard
amplification arguments, this gives an explicit partial function that exhibits
an $O_\epsilon(1)$ vs $\Omega(N^{1-\epsilon})$ separation between bounded-error
quantum and randomized query complexities, where $\epsilon>0$ can be made
arbitrarily small. Our proof also gives the same bound for the closely related
but non-explicit $k$-Rorrelation function introduced by Tal (FOCS `20).
Our techniques rely on classical Gaussian tools, in particular, Gaussian
interpolation and Gaussian integration by parts, and in fact, give a more
general statement. We show that to prove lower bounds for $k$-Forrelation
against a family of functions, it suffices to bound the $\ell_1$-weight of the
Fourier coefficients between levels $k$ and $(k-1)k$. We also prove new
interpolation and integration by parts identities that might be of independent
interest in the context of rounding high-dimensional Gaussian vectors.
- Abstract（参考訳）: Aaronson and Ambainis (SICOMP `18) は、$N$ビット上の任意の部分関数が、$q$の量子クエリによってランダムな推測よりも$\delta$で計算できることを示し、また、${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$クエリをランダム化された決定ツリーによって$\delta/2$で古典的に計算できることを示した。
さらに彼らは、$k$-forrelation問題($q = \lceil k/2 \rceil$ 量子クエリで計算できる部分関数)を、そのような極値分離を示すのに適した候補として予想した。
この予想は、$\delta = 2^{-o(k)}$ という利点を持つ、$k$-forrelation のランダム化されたクエリ複雑性に対して、$\widetilde{\omega}(n^{1-1/k})$ という厳密な下限を示して証明する。
標準的な増幅引数により、$O_\epsilon(1)$ vs $\Omega(N^{1-\epsilon})$境界量子とランダム化されたクエリ複雑度の間の分離を示す明示的な部分関数が得られ、$\epsilon>0$は任意に小さくすることができる。
この証明はまた、tal (focs `20) によって導入された密接な関係があるが非説明の $k$-rorrelation 関数に対する同じ境界を与える。
我々の手法は古典ガウス的ツール、特にガウス的補間とガウス的部分積分に依存しており、実際にはより一般的な記述を与える。
関数の族に対する$k$-Forrelationの低い境界を証明するために、$k$と$(k-1)k$の間のフーリエ係数の$\ell_1$-weightを束縛することが十分であることを示す。
また、高次元ガウスベクトルの丸めの文脈において独立した関心を持つ部分の同一性による新たな補間と積分も証明する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Classical shadows of fermions with particle number symmetry [0.0]
我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。
ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
論文 参考訳（メタデータ） (2022-08-18T17:11:12Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - 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) - Lower Bounds for XOR of Forrelations [7.510385608531827]
我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。
また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
論文 参考訳（メタデータ） (2020-07-07T17:05:09Z) - 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) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
論文 参考訳（メタデータ） (2019-12-29T01:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。