Advertisement
Published in:
2007 | OriginalPaper | Chapter
Unbounded-Error One-Way Classical and Quantum Communication Complexity
Authors : Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
2
n
− 1. Previously, only the non-existence of (2
2
n
,
n
, > 1/2)-QRAC was known.