論文の概要: Lower Bounds for XOR of Forrelations

• arxiv url: http://arxiv.org/abs/2007.03631v1
• Date: Tue, 7 Jul 2020 17:05:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-11 01:41:49.918485
• Title: Lower Bounds for XOR of Forrelations
• Title（参考訳）: forrelation の xor に対する下限
• Authors: Uma Girish, Ran Raz, Wei Zhan
• Abstract要約: 我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。 また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
• 参考スコア（独自算出の注目度）: 7.510385608531827
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Forrelation problem, introduced by Aaronson [A10] and Aaronson and Ambainis [AA15], is a well studied problem in the context of separating quantum and classical models. Variants of this problem were used to give exponential separations between quantum and classical query complexity [A10, AA15]; quantum query complexity and bounded-depth circuits [RT19]; and quantum and classical communication complexity [GRT19]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than $\approx 1/\sqrt{N}$, that is, the success probability is larger than $\approx 1/2 + 1/\sqrt{N}$. To achieve separations when the classical protocol has smaller advantage, we study in this work the XOR of $k$ independent copies of the Forrelation function (where $k\ll N$). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level $2k$ is bounded by $\alpha^k$, cannot compute the XOR of $k$ independent copies of the Forrelation function with advantage better than $O\left(\frac{\alpha^k}{{N^{k/2}}}\right)$. This is a strengthening of a result of [CHLT19], that gave a similar result for $k=1$, using the technique of [RT19]. As an application of our result, we give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol of cost $\mbox{polylog}(N)$ (when players share $\mbox{polylog}(N)$ EPR pairs), however, any classical interactive randomized protocol of cost at most $\tilde{o}(N^{1/4})$, has quasipolynomially small advantage over a random guess. We also give the first example of a partial Boolean function that has a quantum query algorithm of cost $\mbox{polylog}(N)$, and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess.
• Abstract（参考訳）: Aaronson [A10] と Aaronson and Ambainis [AA15] によって導入された Forrelation 問題は、量子モデルと古典モデルの分離という文脈においてよく研究されている問題である。 この問題の変種は、量子および古典的クエリ複雑性 [a10, aa15] 、量子クエリ複雑性と境界深い回路 [rt19] 、量子および古典的通信複雑性 [grt19] を指数関数的に分離するために使われた。 これらすべての分離において、古典モデルの下位境界は、プロトコルの利点(ランダムな推測よりも)が$\approx 1/\sqrt{N}$以上であるとき、すなわち、成功確率が$\approx 1/2 + 1/\sqrt{N}$より大きいときにのみ成り立つ。 古典的プロトコルの利点が小さい場合の分離を実現するため、Forrelation関数の$k$独立コピー($k\ll N$)のXORについて研究する。 我々は、制限の下で閉じたブール関数の族が、レベル 2k$ のフーリエ質量が$\alpha^k$ で有界であることを示し、$O\left(\frac{\alpha^k}{{N^{k/2}}} よりも有利に forrelation 関数の独立コピーの XOR を計算できないことを示す非常に一般的な結果を示す。 これは [CHLT19] の結果の強化であり、 [RT19] のテクニックを用いて、$k=1$ の同様の結果を与えた。 結果の適用例として、コスト$\mbox{polylog}(N)$ (プレーヤが$\mbox{polylog}(N)$ EPRペアを共有する場合) の同時メッセージ量子プロトコルで計算できる部分ブール関数の最初の例を挙げるが、任意の古典的対話的ランダム化プロトコルは、最大$\tilde{o}(N^{1/4})$で、ランダムな推測に対して準ポノミクス的に小さい利点を持つ。 また、量子クエリアルゴリズムがコスト$\mbox{polylog}(n)$である部分ブール関数の最初の例を示し、準多項サイズの定数深さ回路は、ランダムな推測よりも準多項的に小さい。

関連論文リスト

• Generalized Zurek's bound on the cost of an individual classical or quantum computation [0.8806033070373618]
  Zurekは、このコストは$K(xvert y)$、条件付きコルモゴロフ複雑性$x$$$$$$$$$$$によって与えられると提案した。 我々は、$K(xvert y)$が$x$から$y$にマッピングする最小のコストであることを示す。
  論文  参考訳（メタデータ） (2023-01-17T12:35:08Z)
• 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)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
  本稿では,Grier と Schaeffer の対話プロトコルに耐雑音性を加えるための戦略を示す。 この削減の重要な要素は、古典的なシミュレーションタスクにおける平均ケースの硬さを示すことである。 シュミレートするために$oplus$L-hardの量子タスクでさえそうであることを示す。
  論文  参考訳（メタデータ） (2021-02-13T00:54:45Z)
• 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)
• $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity [3.4984289152418753]
  我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。 我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
  論文  参考訳（メタデータ） (2020-08-16T21:26:46Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)
• Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem [0.05076419064097732]
  指数的古典量子通信分離を示す一方向モデルにおける最初の通信問題 効率的な通信プロトコルは、$f$の符号度に応じて提示される。
  論文  参考訳（メタデータ） (2020-01-15T21:05:32Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。