論文の概要: Matching upper bounds on symmetric predicates in quantum communication complexity

• arxiv url: http://arxiv.org/abs/2301.00370v1
• Date: Sun, 1 Jan 2023 08:30:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-09 01:20:54.696411
• Title: Matching upper bounds on symmetric predicates in quantum communication complexity
• Title（参考訳）: 量子通信複雑性における対称述語上界のマッチング
• Authors: Daiki Suruga
• Abstract要約: 共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。 我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we focus on the quantum communication complexity of functions of the form $f \circ G = f(G(X_1, Y_1), \ldots, G(X_n, Y_n))$ where $f: \{0, 1\}^n \to \{0, 1\}$ is a symmetric function, $G: \{0, 1\}^j \times \{0, 1\}^k \to \{0, 1\}$ is any function and Alice (resp. Bob) is given $(X_i)_{i \leq n}$ (resp. $(Y_i)_{i \leq n}$). Recently, Chakraborty et al. [STACS 2022] showed that the quantum communication complexity of $f \circ G$ is $O(Q(f)\mathrm{QCC}_\mathrm{E}(G))$ when the parties are allowed to use shared entanglement, where $Q(f)$ is the query complexity of $f$ and $\mathrm{QCC}_\mathrm{E}(G)$ is the exact communication complexity of $G$. In this paper, we first show that the same statement holds \emph{without shared entanglement}, which generalizes their result. Based on the improved result, we next show tight upper bounds on $f \circ \mathrm{AND}_2$ for any symmetric function $f$ (where $\textrm{AND}_2 : \{0, 1\} \times \{0, 1\} \to \{0, 1\}$ denotes the 2-bit AND function) in both models: with shared entanglement and without shared entanglement. This matches the well-known lower bound by Razborov~[Izv. Math. 67(1) 145, 2003] when shared entanglement is allowed and improves Razborov's bound when shared entanglement is not allowed.
• Abstract（参考訳）: 本稿では、f \circ g = f(g(x_1, y_1), \ldots, g(x_n, y_n))$ where $f: \{0, 1\}^n \to \{0, 1\}$ is a symmetric function, $g: \{0, 1\}^j \times \{0, 1\}^k \to \{0, 1\}$ is any function and alice (resp. bob) は $(x_i)_{i \leq n}$ (resp.bob) を与える。 y_i)_{i \leq n}$)である。 最近、Chakrabortyら。 [STACS 2022] は、$f \circ G$の量子通信複雑性が$O(Q(f)\mathrm{QCC}_\mathrm{E}(G))$であることを示した。 本稿では、最初に、同じ文が、結果の一般化である \emph{without shared entanglement} を持つことを示す。 改良された結果に基づき、次に、任意の対称関数に対して$f \circ \mathrm{AND}_2$(ここで $\textrm{AND}_2 : \{0, 1\} \times \{0, 1\} \to \{0, 1\}$ は 2-bit AND を両モデルで表す:共有絡み付き、共有絡みなし)に対して、厳密な上界を示す。 これは、共有の絡み合いが許されているとき、razborov~[izv. math. 67(1) 145, 2003]でよく知られた下限と一致し、共有の絡み合いが許されていないときに、razborovの束縛を改善する。

関連論文リスト

• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Complexity and Avoidance [0.0]
  適切な$f$と$p$に対して$q$と$g$があり、$mathrmLUA(q) leq_mathrms mathrmCOMPLEX(f)$と$q$と$g$の成長率があることを示す。 シフト複雑性に関して、$$$q$が$rmLUA(q)$の任意のメンバに対して、$delta$-shift複素列を計算するためにどれだけ遅くなるかという明示的な境界が与えられる。
  論文  参考訳（メタデータ） (2022-04-24T14:36:38Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• On relating one-way classical and quantum communication complexities [6.316693022958221]
  通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。 量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
  論文  参考訳（メタデータ） (2021-07-24T14:35:09Z)
• 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)
• $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)
• The quantum query complexity of composition with a relation [78.55044112903148]
  Belovs は負の重み付け逆法の修正版 $mathrmADV_relpm(f)$ を与えた。 関係が効率よく検証できる:$mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$。
  論文  参考訳（メタデータ） (2020-04-14T12:07:20Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• 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)

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

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