Unbounded-Error One-Way Classical and Quantum Communication Complexity

DOI10.1007/978-3-540-73420-8_12MaRDI QIDQ5428802zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(10)

• One-Shot Capacity Bounds on the Simultaneous Transmission of Classical and Quantum Information
• Limitations of Quantum Advice and One-Way Communication
• Unbounded-Error Classical and Quantum Communication Complexity
• Unbounded-error quantum query complexity
• Some algebraic properties of measure-once two-way quantum finite automata
• Unbounded-Error Quantum Query Complexity
• 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)