2007/06/22 by Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Quantum Computing Algorithms and Architecture #quant-ph
paper · pdf · doi:10.1007/978-3-540-73420-8_12
published as Proc. of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), LNCS 4596 pages 110 -- 121 · 9 pages. To appear in Proc. ICALP 2007
arxiv created 2007/06/22 · openalex publication_date 2007/08/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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 ≥ p. We can prove that (m,n,>1/2)-QRAC exists if and only if m≤ 22n-1. Previously, only the construction of QRAC using one qubit, the existence of (O(n),n,>1/2)-RAC, and the non-existence of (22n,n,>1/2)-QRAC were known.