Quantum communication complexity of distribution testing
| Autor: | Alexander A. Sherstov, François Le Gall, Guillaume Malod, Aleksandrs Belovs, Arturo Castellanos |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics Quantum Physics Nuclear and High Energy Physics Matching (graph theory) FOS: Physical sciences General Physics and Astronomy Statistical and Nonlinear Physics Computational Complexity (cs.CC) 01 natural sciences Upper and lower bounds Theoretical Computer Science Computer Science - Computational Complexity Distribution (mathematics) Quadratic equation Computational Theory and Mathematics Qubit 0103 physical sciences 010307 mathematical physics Quantum Physics (quant-ph) Communication complexity Quantum information science Quantum Mathematical Physics Mathematics |
| Zdroj: | Quantum Information and Computation. 21:1261-1273 |
| ISSN: | 1533-7146 |
| DOI: | 10.26421/qic21.15-16-1 |
| Popis: | 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. Comment: 11 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|