<p>This paper proves the results you have described:</p>

<blockquote>
  <p>Ashwin Nayak and Julia Salzman. <a href="http://www.math.uwaterloo.ca/~anayak/papers/NayakS06.pdf">Limits on the Ability of Quantum
  States to Convey Classical Messages.</a> Journal of the ACM, 53(1):
  184-206, 2006.</p>
</blockquote>

CC BY-SA 3.0
2012-07-01T14:08:19.143Z
2012-07-01T14:08:19.143Z
John Watrous
<p>Alice wants to communicate an arbitrary $x \in \{0 ,1\}^n$ to Bob. Alice and Bob communicate
in rounds, in each round Alice (or Bob) applies a unitary transformation on his/her part and
transmits a qubit to the other side, until at the end Bob measures his state and tries to infer
x. The protocol is successful if for every $x \in \{0,1\}^n$ Bob succeeds with probability 1. Let
$n_A / n_B$ be the number of messages sent by Alice / Bob respectively.</p>

<p>Now I want to show that for any successful protocol we must have $n_A \geq  \lceil n/2 \rceil $, and $n_A+n_B \geq n$, and I need to show that the same argument above follows also for p-successful protocols, i.e if there's a p-successful protocol then the ineqaulities above should also follow for this protocol; a p-successful protocol is one in which Bob succeeds with probability p.</p>

<p>Any hints or prefereably bibliography where this or similar problem is disscused?</p>

<p>Thanks.</p>

<quantum-computing><quantum-information>
Communicating a string of zeros and ones quantumly
MathematicalPhysicist
# Communicating a string of zeros and ones quantumly

(Asked by: username_0 on 2012-07-01)

Alice wants to communicate an arbitrary $x \in \{0 ,1\}^n$ to Bob. Alice and Bob communicate
in rounds, in each round Alice (or Bob) applies a unitary transformation on his/her part and
transmits a qubit to the other side, until at the end Bob measures his state and tries to infer
x. The protocol is successful if for every $x \in \{0,1\}^n$ Bob succeeds with probability 1. Let
$n\_A / n\_B$ be the number of messages sent by Alice / Bob respectively.

Now I want to show that for any successful protocol we must have $n\_A \geq \lceil n/2 \rceil $, and $n\_A+n\_B \geq n$, and I need to show that the same argument above follows also for p-successful protocols, i.e if there's a p-successful protocol then the ineqaulities above should also follow for this protocol; a p-successful protocol is one in which Bob succeeds with probability p.

Any hints or prefereably bibliography where this or similar problem is disscused?

Thanks.

**Tags:** quantum-computing, quantum-information

---

## 1 answers

### Answer by username_1 on 2012-07-01. Score: 8 | Accepted answer

This paper proves the results you have described:

> Ashwin Nayak and Julia Salzman. [Limits on the Ability of Quantum
> States to Convey Classical Messages.](http://www.math.uwaterloo.ca/~anayak/papers/NayakS06.pdf) Journal of the ACM, 53(1):
> 184-206, 2006.


---

