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?



1 Answer 1


This paper proves the results you have described:

Ashwin Nayak and Julia Salzman. Limits on the Ability of Quantum States to Convey Classical Messages. Journal of the ACM, 53(1): 184-206, 2006.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.