Unbounded-error One-way Classical and Quantum Communication Complexity

Details Unbounded-error One-way Classical and Quantum Communication Complexity Unbounded-error One-way Classical and Quantum Communication Complexity

2007-06-22

arxiv.org/abs/0706.3265v1

Proc. of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), LNCS 4596 pages 110 -- 121

Physics

Quantum Physics

9 pages. To appear in Proc. ICALP 2007

Scientific paper

10.1007/978-3-540-73420-8_12

This paper studies the gap between quantum one-way communication complexity $Q(f)$ and its classical counterpart $C(f)$, under the {\em unbounded-error} setting, i.e., it is enough that the success probability is strictly greater than 1/2. It is proved that for {\em any} (total or partial) Boolean function $f$, $Q(f)=\lceil C(f)/2 \rceil$, i.e., the former is always exactly one half as large as the latter. The result has an application to obtaining (again 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 $\geq p$. We can prove that $(m,n,>1/2)$-QRAC exists if and only if $m\leq 2^{2n}-1$. Previously, only the construction of QRAC using one qubit, the existence of $(O(n),n,>1/2)$-RAC, and the non-existence of $(2^{2n},n,>1/2)$-QRAC were known.

Affiliated with

Also associated with

No associations

Rating

Unbounded-error One-way Classical and Quantum Communication Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Unbounded-error One-way Classical and Quantum Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unbounded-error One-way Classical and Quantum Communication Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-187473