Unbounded-error One-way Classical and Quantum Communication Complexity

Abstract

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 $\ge p$. We can prove that $(m,n,>1/2)$-QRAC exists if and only if $m\le 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.

9 pages. To appear in Proc. ICALP 2007

References in corpus (10)

• Quantum fingerprinting
• Characterization of the Positivity of the Density Matrix in Terms of the Coherence Vector Representation
• Quantum communication complexity of symmetric predicates
• Optimal lower bounds for quantum automata and random access codes
• Quantum vs. Classical Communication and Computation
• (4,1)-Quantum Random Access Coding Does Not Exist
• Limitations of Quantum Advice and One-Way Communication
• Lower bounds for quantum communication complexity
• Unital quantum operators on the Bloch ball and Bloch region
• Strengths and Weaknesses of Quantum Fingerprinting

Cited by in corpus (7)

• Experimental Demonstration of Sequential Quantum Random Access Codes
• Quantum Random Access Codes for Boolean Functions
• Unbounded Error Quantum Query Complexity
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Unbounded-Error Classical and Quantum Communication Complexity
• The geometry of Bloch space in the context of quantum random access codes
• The One-Way Communication Complexity of Group Membership