Unbounded-error One-way Classical and Quantum Communication Complexity

Simple item page
dc.creatorIwama, Kazuo
dc.creatorNishimura, Harumichi
dc.creatorRaymond, Rudy
dc.creatorYamashita, Shigeru
dc.date2007-06-22
dc.date.accessioned2026-07-07T08:29:47Z
dc.date.available2026-07-07T08:29:47Z
dc.descriptionThis 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.
dc.description9 pages. To appear in Proc. ICALP 2007
dc.identifierhttps://arxiv.org/abs/0706.3265
dc.identifierhttp://arxiv.org/abs/0706.3265
dc.identifierProc. of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), LNCS 4596 pages 110 -- 121
dc.identifierdoi:10.1007/978-3-540-73420-8_12
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/138059
dc.subjectQuantum Physics
dc.titleUnbounded-error One-way Classical and Quantum Communication Complexity
dc.typetext

Files

Collections

arXiv