|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Unbounded-error One-way Classical and Quantum Communication Complexity | | Kazuo Iwama
; Harumichi Nishimura
; Rudy Raymond
; Shigeru Yamashita
; | | Date: |
22 Jun 2007 | | 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
ceil$, 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
$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. | | Source: | arXiv, arxiv.0706.3265 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER