This paper studies the gap between quantum one-way communication complexity Q(f) and its classical counterpart C(f), under the unbounded-error setting, i.e., it is enough that the success probability is strictly greater than 1 2. It is proved that for any (total or partial) Boolean function f, Q(f) = ⌈C(f) 2⌉, i.e., the former is always exactly one half as large as the latter. The result has an application to obtaining an exact bound for the existence of (m, n, p)-QRAC which is the n-qubit random access coding that can recover any one of m original bits with success probability ≥ p. We can prove that (m, n, > 1 2)-QRAC exists if and only if m ≤ 22n - 1. Previously, only the non-existence of (22n, n,> 1 2)-QRAC was known.
Private-coin Public-coin Models. The exponential quantum classical separations in @cite_13 and @cite_11 still hold under the public-coin model where Alice and Bob share random coins, since the one-way classical public-coin model can be simulated by the one-way classical private-coin model with additional @math -bit communication @cite_19 . However, exponential quantum classical separation for total functions remains open for all of the bounded-error two-way, one-way and SMP models. Note that the public-coin model is too powerful in the unbounded-error model: we can easily see that the unbounded-error one-way (classical or quantum) communication complexity of any function (or relation) is @math with prior shared randomness.
@cite_19 @cite_13 @cite_11
2088263428 203155997 2148488235
Abstract We investigate the relative power of the common random string model vs. the private random string model in communication complexity. We show that the models are essentially equal. We give an exponential separation between one-way quantum and classical communication protocols for twopartial Boolean functions, both of which are variants of the Boolean Hidden Matching Problem of Bar- Earlier such an exponential separation was known only for a relational version of the Hidden Matching Problem. Our proofs use the Fourier coefficients inequality of Kahn, Kalai, and Linial. We give a number of applications of this separation. In particular, in the bounded-storage model of cryptography we exhibita scheme that is secure against adversaries with a certain amount of classical storage, but insecure against adversaries with a similar (or even much smaller) amount of quantum storage; in the setting of privacy amplification, we show that there are strong extractors that yield a classically secure key, but are insecure against a quantum adversary.