講演抄録/キーワード |
講演名 |
2019-11-18 13:50
[ポスター講演]Quantum Communication Complexity of Distribution Testing Aleksandrs Belovs(Univ. of Latvia)・○Arturo Castellanos(Kyoto Univ.)・Francois Le Gall・Guillaume Malod(Nagoya Univ.) |
抄録 |
(和) |
We study the quantum version of the closeness testing problem in communication complexity, in the case where Alice and Bob distributions are uniform on some subset of [n]. More precisely, Alice and Bob receive t samples from distributions a and b respectively, under the promise that they are either equal or e-far in the l1 distance for some fixed e> 0. While in the classical setting recent work have shown a communication complexity of O~((n/te^2)^2) bits, in the quantum setting we manage to gain a quadratic advantage. |
(英) |
We study the quantum version of the closeness testing problem in communication complexity, in the case where Alice and Bob distributions are uniform on some subset of [n]. More precisely, Alice and Bob receive t samples from distributions a and b respectively, under the promise that they are either equal or e-far in the l1 distance for some fixed e> 0. While in the classical setting recent work have shown a communication complexity of O~((n/te^2)^2) bits, in the quantum setting we manage to gain a quadratic advantage. |
キーワード |
(和) |
Distribution testing / Quantum communication complexity / / / / / / |
(英) |
Distribution testing / Quantum communication complexity / / / / / / |
文献情報 |
信学技報 |
資料番号 |
|
発行日 |
|
ISSN |
|
PDFダウンロード |
|