On communication over an entanglement-assisted quantum channel

ABSTRACT

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

REFERENCES

• 1: A. Ambainis , L. J. Schulman , A. Ta-Shma , U. Vazirani , A. Wigderson, The Quantum Communication Complexity of Sampling, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.342, November 08-11, 1998
• 2: C. Bennett, C. Crépeau, R. Jozsa, A. Peres, and W. Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70:1895--1899, 1993.
• 3: C. Bennett and P. Shor. Quantum information theory. IEEE Transactions on Information Theory, IT-44(6):2724--2742, 1998.
• 4: C. Bennett and S. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Physical Review Letters, 69:2881--2884, 1992.
• 5: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 6: Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276713]
• 7: Harry Buhrman , Ronald de Wolf, Communication Complexity Lower Bounds by Polynomials, Proceedings of the 16th Annual Conference on Computational Complexity, p.120, June 18-21, 2001
• 8: Richard Cleve , Wim van Dam , Michael Nielsen , Alain Tapp, Quantum Entanglement and the Communication Complexity of the Inner Product Function, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.61-74, February 17-20, 1998
• 9: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 10: A. Holevo. Some estimates of the information transmitted by quantum communication channels. Problems of Information Transmission, 9:177--183, 1973.
• 11: Hartmut Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.644-651, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335396]
• 12: H. Klauck, Lower Bounds for Quantum Communication Complexity, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.288, October 14-17, 2001
• 13: Hartmut Klauck , Ashwin Nayak , Amnon Ta-Shma , David Zuckerman, Interaction in quantum communication and the complexity of set disjointness, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.124-133, July 2001, Hersonissos, Greece [doi>10.1145/380752.380786]
• 14: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 15: Ashwin V. Nayak , Umesh Vazirani, Lower bounds for quantum computation and communication, 1999
• 16: Ashwin Nayak, Optimal Lower Bounds for Quantum Automata and Random Access Codes, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.369, October 17-18, 1999
• 17: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 18: Ran Raz, Exponential separation of quantum and classical communication complexity, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.358-367, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301343]
• 19: W. van Dam and P. Hayden. Communication complexity of quantum state transformations. Manuscript, 2001.
• 20: A. C.-C. Yao. Quantum circuit complexity. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 352--361, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory

Keywords:
communication complexity, entanglement-assisted quantum channel, quantum communication