論文の概要: Quantum Communication Complexity of Distribution Testing

• arxiv url: http://arxiv.org/abs/2006.14870v1
• Date: Fri, 26 Jun 2020 09:05:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-12 11:41:11.814250
• Title: Quantum Communication Complexity of Distribution Testing
• Title（参考訳）: 分布テストの量子通信複雑性
• Authors: Aleksandrs Belovs, Arturo Castellanos, Fran\c{c}ois Le Gall, Guillaume Malod and Alexander A. Sherstov
• Abstract要約: 2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
• 参考スコア（独自算出の注目度）: 114.31181206328276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP'19). In this problem, two players each receive $t$ samples from one distribution over $[n]$, and the goal is to decide whether their two distributions are equal, or are $\epsilon$-far apart in the $l_1$-distance. In the present paper we show that the quantum communication complexity of this problem is $\tilde{O}(n/(t\epsilon^2))$ qubits when the distributions have low $l_2$-norm, which gives a quadratic improvement over the classical communication complexity obtained by Andoni, Malkin and Nosatzki. We also obtain a matching lower bound by using the pattern matrix method. Let us stress that the samples received by each of the parties are classical, and it is only communication between them that is quantum. Our results thus give one setting where quantum protocols overcome classical protocols for a testing problem with purely classical samples.
• Abstract（参考訳）: 離散分布の近接性をテストする古典的な通信複雑性は、最近Andoni, Malkin and Nosatzki (ICALP'19) によって研究されている。 この問題では、2人のプレイヤーが1つのディストリビューションから$t$のサンプルを$[n]$で受け取り、その2つのディストリビューションが等しいか、または$l_1$-distanceで$\epsilon$-farになるかを判断する。 本稿では,この問題における量子通信の複雑性は,分布が$l_2$-norm が低い場合に$\tilde{o}(n/(t\epsilon^2))$ qubitsであることを示す。 また,パターン行列法を用いて,一致した下界を求める。 それぞれのパーティから受け取ったサンプルは古典的であり、量子的であるそれらの間の通信のみである、と強調する。 その結果、量子プロトコルは、純粋に古典的サンプルを持つテスト問題に対して、古典的なプロトコルを克服する。

関連論文リスト

• Distributed Quantum Hypothesis Testing under Zero-rate Communication Constraints [14.29947046463964]
  本研究では,2つのリモートパーティ間で共有される二部量子状態を推定するために,分散二分仮説テスト問題について検討する。 我々の主な貢献として、この問題に対するスタインの指数に対して効率よく計算可能なシングルレター式を導出する。 結果の逆方向を証明するための鍵となるツールとして,爆発性レムマの量子バージョンを開発する。
  論文  参考訳（メタデータ） (2024-10-11T16:03:10Z)
• Communication Complexity of Common Randomness Generation with Isotropic States [5.312109949216557]
  本稿は、一方通行古典通信と一方通行量子通信の2つの通信モデルについて考察する。 古典的通信の場合、量子等方性状態はノイズのある古典的相関に勝らないことを示す。 量子通信の場合、量子等方性状態の超高密度符号化を用いることで、共通乱数率を増大させることができることを示す。
  論文  参考訳（メタデータ） (2023-11-08T14:48:15Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
  本研究では, 量子計算が分布特性の試験の基礎的問題に与える影響について検討する。 この問題に対して現在最高の量子アルゴリズムを$l1$-distanceと$l2$-distanceのメトリクスで提案する。
  論文  参考訳（メタデータ） (2023-02-13T04:03:59Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Distributed quantum inner product estimation [14.222887950206658]
  2つの量子コンピュータ上で準備された状態の忠実度を推定することを目的とした、クロスプラットフォーム検証として知られるベンチマークタスクが提案されている。 ハードウェアの制約により、2つの物理プラットフォーム間で量子通信を行うことはできない。 サンプルの複雑さは、最強の設定でも少なくとも$Omega(max1/varepsilon2,sqrtd/varepsilon)$でなければならない。
  論文  参考訳（メタデータ） (2021-11-05T05:35:03Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。 MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
  論文  参考訳（メタデータ） (2021-10-07T09:38:15Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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