Limits on the ability of quantum states to convey classical messages

Abstract

We revisit the problem of conveying classical messages by transmitting quantum states, and derive new, optimal bounds on the number of quantum bits required for this task. Much of the previous work on this problem, and on other communication tasks in the setting of bounded error entanglement-assisted communication, is based on sophisticated information theoretic arguments. Our results are derived from first principles, using a simple linear algebraic technique. A direct consequence is a tight lower bound for the Inner Product function that has found applications to privacy amplification in quantum key distribution protocols.

References

1. Ambainis, A., Nayak, A., Ta-Shma, A., and Vazirani, U. 2002. Dense quantum coding and quantum finite automata. J. ACM 49, 4 (July), 1--16.]]
2. Ambainis, A., Schulman, L. J., Ta-Shma, A., Vazirani, U., and Wigderson, A. 2003. Quantum communication complexity of sampling. SIAM J. Comput. 32, 1570--1585.]]
3. Bar-Yossef, Z., Jayram, T. S., and Kerenidis, I. 2004. Exponential separation of quantum and classical one-way communication complexity. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. ACM, New York, 128--137.]]
4. Ben-Or, M. 1999. Simple security proof for quantum key distribution. Unpublished. (See talk given during the MSRI special semester on quantum computation in 2002: http://www.msri.org/publications/ln/msri/2002/qip/ben-or/1/index.html.)]]
5. Bennett, C. H., and Brassard, G. 1984. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. IEEE Computer Society, Press, Los Alamitos, CA, 175.]]
6. Bennett, C. H., Brassard, G., Crépeau, C., Jozsa, R., Peres, A., and Wootters, W. K. 1993. Teleporting an unknown quantum state via dual classical and Einstein--Podolsky--Rosen channels. Phys. Rev. Lett. 70, 1895--1899.]]
7. Bennett, C. H., and Shor, P. W. 1998. Quantum information theory. IEEE Trans. Inf. Theory IT-44, 6, 2724--2742.]]
8. Bennett, C. H., and Wiesner, S. J. 1992. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Phys. Rev. Lett. 69, 2881--2884.]]
9. Bernstein, E., and Vazirani, U. V. 1997. Quantum complexity theory. SIAM J. Comput. 26, 5, 1411--1473.]]
10. Buhrman, H., Cleve, R., and Wigderson, A. 1998. Quantum vs. classical communication and computation. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM Press, New York, 63--68.]]
11. Buhrman, H., and de Wolf, R. 2001. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity. IEEE Press, Los Alamitos, CA, 120--130.]]
12. Cleve, R., and Buhrman, H. 1997. Substituting quantum entanglement for communication. Phys. Rev. A 56, 2, 1201--1204.]]
13. Cleve, R., van Dam, W., Nielsen, M., and Tapp, A. 1998. Quantum entanglement and the communication complexity of the inner product function. In Quantum Computing and Quantum Communications, Proceedings of the 1st NASA International Conference. Lecture Notes in Computer Science, vol. 1509. Springer-Verlag, Heidelberg, Germany, 61--74.]]
14. Cover, T. M., and Thomas, J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications. Wiley, New York.]]
15. de Wolf, R. 2005. Lower bounds on matrix rigidity via a quantum argument. Tech. rep., Arxiv.org Preprint Archive. (Available at http://www.arxiv.org/abs/quant-ph/0505188.)]]
16. Goldreich, O. 1995. Three XOR-lemmas---An exposition. Tech. Rep. TR95-056, Electronic Colloquium on Computational Complexity. (Available at http://eccc.uni-trier.de/eccc/.)]]
17. Holevo, A. 1973. Some estimates of the information transmitted by quantum communication channels. Prob. Inf. Trans. 9, 3, 177--183. (Russian version in Problemy Peredachi Informatsii 9 (1973), 3--11.)]]
18. Kerenidis, I., and de Wolf, R. 2004. Exponential lower bound for 2-query locally decodable codes. J. Comput. Syst. Sci. 69, 3, 395--420. (Special issue for STOC 2003.)]]
19. Klauck, H. 2000. On quantum and probabilistic communication: Las Vegas and one-way protocols. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. ACM, New York, 644--651.]]
20. Klauck, H. 2001a. Lower bounds for quantum communication complexity. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 288--297.]]
21. Klauck, H. 2001b. One-way communication complexity and the Neciporuk lower bound on formula size. Tech. rep., Arxiv.org Preprint Archive. (Available at http://www.arxiv.org/abs/cs.CC/0111062.)]]
22. Klauck, H., Nayak, A., Ta-Shma, A., and Zuckerman, D. 2001. Interaction in quantum communication and the complexity of Set Disjointness. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, New York, 124--133.]]
23. Kremer, I. 1995. Quantum communication. M.S. thesis, The Hebrew University of Jerusalem, Jerusalem, Israel.]]
24. Kushilevitz, E., and Nisan, N. 1997. Communication Complexity. Cambridge University Press, Cambridge, UK.]]
25. Lo, H.-K., and Chau, H. F. 1997. Is quantum bit commitment really possible? Phys. Rev. Lett. 78, 3410--3413.]]
26. Mayers, D. 1997. Unconditionally secure quantum bit commitment is impossible. Phys. Rev. Lett. 78, 17, 3414--3417.]]
27. Nayak, A. 1999. Lower bounds for quantum computation and communication. Ph.D. thesis, University of California, Berkeley.]]
28. Nielsen, M. A., and Chuang, I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK.]]
29. Preskill, J. 1998. Quantum computation. Lecture Notes, available at http://www.theory.caltech.edu/people/preskill/ph229/, California Institute of Technology, Pasadena, CA.]]
30. Raz, R. 1999. Exponential separation of quantum and classical communication complexity. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing. ACM, New York, 358--367.]]
31. Raz, R. 2005. Quantum information and the PCP theorem. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 459--468.]]
32. Razborov, A. 2003. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics 67, 1, 145--159. (Russian version in Izvestiya Rossiiskoi Academii Nauk (seriya matematicheskaya) 67 (2003), 1, 159--176.)]]
33. van Dam, W., and Hayden, P. 2002. Renyi-entropic bounds on quantum communication. Tech. rep., Arxiv.org Preprint Archive. Available at http://www.arxiv.org/abs/quant-ph/0204093.]]
34. Yao, A. C.-C. 1993. Quantum circuit complexity. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 352--361.]]

Index Terms

• Theory of computation

  • Design and analysis of algorithms