Abstract
We consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an a priori supply of particles in an entangled quantum state. We prove linear lower bounds for both exact protocols, as well as for protocols that determine the answer with bounded-error probability. Our proofs employ a novel kind of “quantum„ reduction from a quantum information theory problem to the problem of computing the inner product. The communication required for the former problem can then be bounded by an application of Holevo’s theorem. We also give a speciffic example of a probabilistic scenario where entanglement reduces the communication complexity of the inner product function by one bit.
Research initiated while visiting the Université de Montréal and supported in part by Canada’s NSERC.
Research supported in part by Canada’s NSERC.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Araki and E.H. Lieb, “Entropy inequalities„, Commun. Math. Phys., Vol. 18, 1970, pp. 160–170.
C.H. Bennett, E. Bernstein, G. Brassard, U. Vazirani, “Strengths and weaknesses of quantum computing„, SIAM J. on Comput., Vol. 26, No. 5, 1997, pp. 1510–1523.
C.H. Bennett, G. Brassard, C. Crépeau, R. Josza, A. Peres, W.K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels„, Phys. Rev. Lett., Vol. 70, 1993, pp. 1895–1899.
C.H. Bennett and S.J. Wiesner, “Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states„, Phys. Rev. Lett., Vol. 69, No. 20, 1992, pp. 2881–2884.
E. Bernstein, U. Vazirani, “Quantum Complexity Theory„, SIAM J. Comput., Vol. 26, No. 5, 1997, pp. 1411–1473.
H. Buhrman, R. Cleve, and W. van Dam, “Quantum Entanglement and Communication Complexity„, preprint available from the LANL quant-ph archive 9705033, 1997.
B. Chor and O. Goldreich, “Unbiased bits from weak sources of randomness and probabilistic communication complexity„, SIAM J. on Comput., Vol. 17, No. 2, pp. 230–261, 1988.
R. Cleve and H. Buhrman, “Substituting quantum entanglement for communication„, Phys. Rev. A, Vol. 56, No. 2, pp. 1201–1204, 1997.
T.M. Cover and J.A. Thomas, Elements of Information Theory, John Wiley and Sons, 1991.
A. Einstein, B. Podolsky, and N. Rosen, “Can quantum-mechanical description of physical reality be complete?„, Phys. Rev., Vol. 47, 1935, pp. 777–780.
A.S. Holevo, “Bounds for the Quantity of Information Transmitted by a Quantum Communication Channel„, Problemy Peredachi Informatsii, Vol. 9, No. 3, 1973, pp. 3–11. English translation Problems of Information Transmission, Vol. 9, 1973, pp. 177–183.
I. Kremer, “Quantum Communication„, Master’s Thesis, The Hebrew University of Jerusalem, 1995.
E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge University Press, 1997.
B.M. Terhal and J.A. Smolin, “Superfast quantum algorithms for coin weighing and binary search problems„, preprint available from the LANL quant-ph archive 9705041, 1997.
B. Schumacher, M. Westmoreland and W. K.Wootters, “Limitation on the amount of accessible information in a quantum channel„, Phys. Rev. Lett., Vol. 76, 1996, pp. 3453–3456.
A.C. Yao, “Some complexity questions related to distributed computing„, Proc. of the 11th Ann. ACM Symp. on Theory of Computing, 1979, pp. 209–213.
A.C. Yao, “Quantum circuit complexity„, Proc. of the 34th Ann. IEEE Symp. on Foundations of Computer Science, 1993, pp. 352–361.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cleve, R., van Dam, W., Nielsen, M., Tapp, A. (1999). Quantum Entanglement and the Communication Complexity of the Inner Product Function. In: Williams, C.P. (eds) Quantum Computing and Quantum Communications. QCQC 1998. Lecture Notes in Computer Science, vol 1509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49208-9_4
Download citation
DOI: https://doi.org/10.1007/3-540-49208-9_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65514-5
Online ISBN: 978-3-540-49208-5
eBook Packages: Springer Book Archive