Quantum Communication Complexity of Distribution Testing

• URL: http://arxiv.org/abs/2006.14870v1
• Date: Fri, 26 Jun 2020 09:05:58 GMT
• Title: Quantum Communication Complexity of Distribution Testing
• Authors: Aleksandrs Belovs, Arturo Castellanos, Fran\c{c}ois Le Gall, Guillaume Malod and Alexander A. Sherstov
• Abstract summary: Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
• Score: 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.

Related papers

• Distributed Quantum Hypothesis Testing under Zero-rate Communication Constraints [14.29947046463964]
  We study a distributed binary hypothesis testing problem to infer a bipartite quantum state shared between two remote parties. As our main contribution, we derive an efficiently computable single-letter formula for the Stein's exponent of this problem. As a key tool for proving the converse direction of our results, we develop a quantum version of the blowing-up lemma.
  arXiv  Detail & Related papers  (2024-10-11T16:03:10Z)
• Communication Complexity of Common Randomness Generation with Isotropic States [5.312109949216557]
  The paper considers two communication models -- one-way classical communication and one-way quantum communication. We show that in the case of classical communication, quantum isotropic states have no advantage over noisy classical correlation. In the case of quantum communication, we demonstrate that the common randomness rate can be increased by using superdense coding on quantum isotropic states.
  arXiv  Detail & Related papers  (2023-11-08T14:48:15Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
  We study the impact of quantum computation on the fundamental problem of testing the property of distributions. We propose the currently best quantum algorithms for this problem under the metrics of $l1$-distance and $l2$-distance.
  arXiv  Detail & Related papers  (2023-02-13T04:03:59Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Distributed quantum inner product estimation [14.222887950206658]
  A benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. No quantum communication can be performed between the two physical platforms due to hardware constraints. We show that the sample complexity must be at least $Omega(max1/varepsilon2,sqrtd/varepsilon)$, even in the strongest setting.
  arXiv  Detail & Related papers  (2021-11-05T05:35:03Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.