論文の概要: Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

• arxiv url: http://arxiv.org/abs/2107.11806v1
• Date: Sun, 25 Jul 2021 13:52:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-20 23:39:17.670912
• Title: Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error
• Title（参考訳）: 誤りの少ない等式ランダム化・量子通信複雑性のためのタイト境界
• Authors: Nikhil S. Mande, Ronald de Wolf
• Abstract要約: 誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。 量子モデルでは、(1)コスト$log(n/epsilon)+4$の一方のプロトコルを示し、純粋な状態のみを使用し、$n$-bit Equality関数を計算して$epsilon$をエラーする。 純粋な状態のみを使用する$n$-bit Equalityのための$epsilon$-errorワンウェイプロトコルは、少なくとも$log(n/epsilon)-log(1/epsilon)を通信する。
• 参考スコア（独自算出の注目度）: 0.90238471756546
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $\epsilon$, getting the optimal constant factors in the leading terms in a number of different models. In the randomized model, 1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newman's theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. 2) Using this we obtain a $(\log(n/\epsilon^2)+4)$-cost private-coin communication protocol that computes the $n$-bit Equality function, to error $\epsilon$. This improves upon the $\log(n/\epsilon^3)+O(1)$ upper bound implied by Newman's theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive $\log\log(1/\epsilon)+O(1)$. In the quantum model, 1) we exhibit a one-way protocol of cost $\log(n/\epsilon)+4$, that uses only pure states and computes the $n$-bit Equality function to error $\epsilon$. This bound was implicitly already shown by Nayak [PhD thesis'99]. 2) We show that any $\epsilon$-error one-way protocol for $n$-bit Equality that uses only pure states communicates at least $\log(n/\epsilon)-\log\log(1/\epsilon)-O(1)$ qubits. 3) We exhibit a one-way protocol of cost $\log(\sqrt{n}/\epsilon)+3$, that uses mixed states and computes the $n$-bit Equality function to error $\epsilon$. This is also tight up to an additive $\log\log(1/\epsilon)+O(1)$, which follows from Alon's result. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix. This also implies improved upper bounds on these measures for the distributed SINK function, which was recently used to refute the randomized and quantum versions of the log-rank conjecture.
• Abstract（参考訳）: 誤差確率$\epsilon$ の十分に研究された等式関数のランダム化と量子コミュニケーションの複雑さを調べ、多くの異なるモデルにおいて先頭項における最適な定数係数を得る。 ランダム化モデルでは,(1)小さな乗算誤差を伴って,公開coinプロトコルをプライベートcoinプロトコルに変換する一般的な手法を,添加コストで提供する。 これは、ニューマンの定理 [Inf. Proc. Let.'91] の誤差パラメータへの依存性の改善である。 2) これを用いて$(\log(n/\epsilon^2)+4)$コストのプライベートコイン通信プロトコルを取得し、$n$-bit Equality関数を計算し、$\epsilon$をエラーする。 これは、ニューマンの定理に示唆される$\log(n/\epsilon^3)+o(1)$の上界を改良し、アロン [comb. prob. comput.'09] から$\log\log(1/\epsilon)+o(1)$ まで続く最もよく知られた下界に一致する。 量子モデルでは、1)コスト$\log(n/\epsilon)+4$の一方のプロトコルを示し、純粋な状態のみを使用し、$n$-bit Equality関数を計算してエラー$\epsilon$とする。 この境界はすでに Nayak [PhDthesis'99] によって暗黙的に示されていた。 2) 純状態のみを使用するn$-bit平等のための$\epsilon$-error one-wayプロトコルは、少なくとも$\log(n/\epsilon)-\log\log(1/\epsilon)-o(1)$ qubits と通信する。 3)$\log(\sqrt{n}/\epsilon)+3$の一方通行プロトコルを示し,混合状態を使い,$n$-bit等式関数を計算して$\epsilon$をエラーする。 これは加法 $\log\log(1/\epsilon)+O(1)$ にも強くなり、これはアロンの結果に従う。 我々の上界もまた、等式行列の近似階数と関連する測度について上界を得る。 これはまた、ログランク予想のランダム化および量子化バージョンを反論するために最近使われた分散シンク関数のこれらの測度の上界の改善も含んでいる。

関連論文リスト

• Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation [16.499689832762765]
  未知の$n$-qubit state $rho$のコピーが与えられたとき、与えられたクラス$C$の何らかの状態を持つフィデリティ$tau$を持ち、そのフィデリティ$ge tau - epsilon$と$rho$を持つ状態を見つける。 我々は,このタスクのための計算効率の良いプロトコルを設計するための新しいフレームワークである安定化器ブートストラッピングを提供し,これを用いて,安定化器状態と離散積状態という,次のクラスに対する新しい非依存トモグラフィープロトコルを得る。
  論文  参考訳（メタデータ） (2024-08-13T15:23:17Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。 我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
  論文  参考訳（メタデータ） (2024-04-16T00:56:36Z)
• Efficient Pauli channel estimation with logarithmic quantum memory [9.275532709125242]
  a protocol can estimated the eigen values of a Pauli channel to error $epsilon$ using only $O(log n/epsilon2)$ ancilla and $tildeO(n2/epsilon2)$ measured。 我々の知識によれば、量子メモリの対数的に多くの量子ビットが指数統計上の優位性のために十分である最初の量子学習タスクである。
  論文  参考訳（メタデータ） (2023-09-25T17:53:12Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
  サンプルの複雑さを$(k/epsilon2)cdot textpolylog (1/epsilon)$に削減する新しい定数メモリスキームを提供する。 これは$textpolylog (1/epsilon)$ factorまで最適であると推測する。
  論文  参考訳（メタデータ） (2022-05-19T18:51:28Z)
• 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)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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