Unbounded-Error One-Way Classical and Quantum Communication Complexity

DOI10.1007/978-3-540-73420-8_12zbMATH Open1171.68483arXiv0706.3265OpenAlexW1929816335MaRDI QIDQ5428802FDOQ5428802

Authors: Harumichi Nishimura, Rudy Raymond, S. Yamasita, Kazuo Iwama 

Publication date: 28 November 2007

Published in: Automata, Languages and Programming (Search for Journal in Brave)

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)=lceilC(f)/2ceil$, 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 $geqp$. We can prove that $(m,n,>1/2)$-QRAC exists if and only if $mleq{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.

Full work available at URL: https://arxiv.org/abs/0706.3265

Recommendations

• Unbounded-Error Classical and Quantum Communication Complexity
• New bounds on classical and quantum one-way communication complexity
• Unbounded-error quantum query complexity
• Unbounded-Error Quantum Query Complexity
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (10)

• One-Shot Capacity Bounds on the Simultaneous Transmission of Classical and Quantum Information
• Unbounded-Error Classical and Quantum Communication Complexity
• Limitations of Quantum Advice and One-Way Communication
• Unbounded-error quantum query complexity
• Unbounded-Error Quantum Query Complexity
• Some algebraic properties of measure-once two-way quantum finite automata
• New bounds on classical and quantum one-way communication complexity
• The geometry of Bloch space in the context of quantum random access codes
• Expanding the sharpness parameter area based on sequential \(3 \rightarrow 1\) parity-oblivious quantum random access code
• Optimal bounds for parity-oblivious random access codes

This page was built for publication: Unbounded-Error One-Way Classical and Quantum Communication Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428802)