Unbounded-Error One-Way Classical and Quantum Communication Complexity

摘要

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 ≤ 2~(2n) - 1. Previously, only the non-existence of (2~(2n),n, ＞ 1/2)-QRAC was known.