Exponential separation of quantum and classical communication complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Exponential separation of quantum and classical communication complexity

Full text

Pdf (872 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 358 - 367

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Ran Raz

Department of Applied Mathematics and Computer Science, Weizmann Institute, Rehovot 76100, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 55, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301343 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Aha	D. Aharonov, "Quantum Computation", to appear in Annual Reviews of Computational Physics, ed. Dietrich Stauffer~ World Scientific, vol VI, 1998. (Also in quant-ph/9812037).
	AS	N. Alon and J.H. Spencer, The Probabilistic Methods John Wiley & Sons Inc., 1992.
	ASTVW	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
	BBCJPW	C.H. Bennett, G. Brassaxd, C. Cr~pe~u, R. Jozsa, A. Peres, and W.K. Wootters, "Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channells', Phys. Rev. Lett., 70, pp~1895-~898, 1993.
	BCW	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]
	BPMWZ	D. Bouwmeester, J-W. Pan, K. Mattle, H. Weinfurter and A. Zeilinger, "Experimental quantum teleportation", Nature, 390, pp.575-579, 1997.
	BV	Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
	Gro	L.K. Grover, "Quantum mechanics helps in searching for a needle in a haystack", Phys. Rev. Left., 79, pp.325-328~ 1997. (Also in quant-ph/9706033 a~d ST OC 1996).
	Hol	A.S. Holevo, "Bounds for the quantity of information transmitted by a quantum communication channel", Problemy Peredachi Informatsii, 9 (3) pp.3-11, 1973. English translation: Problems of Information Transmission, 9, pp.177-183, 1973.
	HADLMS	R.J. Hughes, D.M. Alde, P. Dyer, G.G. Luther, G.L. Morgan and M. Schauer, "Quantum cryptography'', Contemp. Phys., 36, pp.149-163, 1995.
	Kre	I. Kremer, Quantum Communication~ MSc Thesis, Computer Science Department, The Hebrew University, 1995.
	KN	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	KS	Bala Kalyanasundaram , Georg Schintger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, v.5 n.4, p.545-557, Nov. 1992 [doi>10.1137/0405044]
	KW	M. Kaxchmer and A. Wigderson, "Monotone circuits for connectivity require super-logarithmic depth", SIAM ,l. on Disc. Math., 3 (2), pp.255- 265, t990. (Also in STOC 1998).
	MS	Vitali D Milman , Gideon Schechtman, Asymptotic theory of finite dimensional normed spaces, Springer-Verlag New York, Inc., New York, NY, 1986
	MWKZ	K. Mattle, H. Weinfurter, P.G. Kwiat and A. Zeilinger, ':Dense coding in experimental quantum communication", Phys. I~ev. Lett., 76, pp.4656- 46597 1996.
	New	Ilan Newman, Private vs. common random bits in communication complexity, Information Processing Letters, v.39 n.2, p.67-71, July 31, 1991 [doi>10.1016/0020-0190(91)90157-D]
	Pre	J. Preskill, Lecture notes on quantum information and quantum computation~ http://www.theory, caltech.edu/people/preskitl/ph229/
	Razb	A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
	Sho	Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
	Yao1	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
	Yao2	A.C.C. ~ao, "Quantum circuit complexity", Proc. of the 3~th IEEE Syrup. Fouad. of Computer Science, pp. 352-361, 1993.

CITED BY 17

	Ashwin Nayak , Julia Salzman, On communication over an entanglement-assisted quantum channel, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Ronald de Wolf, Quantum communication and complexity, Theoretical Computer Science, v.287 n.1, p.337-353, 25 September 2002
	Jozef Gruska, Quantum entanglement as a new information processing resource, New Generation Computing, v.21 n.4, p.279-295, April 2003
	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
	Ziv Bar-Yossef , T. S. Jayram , Iordanis Kerenidis, Exponential separation of quantum and classical one-way communication complexity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Edith Hemaspaandra , Lane A. Hemaspaandra , Marius Zimand, Almost-everywhere superiority for Quantum polynomial time, Information and Computation, v.175 n.2, p.171-181, June 15, 2002
	Martin Sauerhoff , Detlef Sieling, Quantum branching programs and space-bounded nonuniform quantum complexity, Theoretical Computer Science, v.334 n.1-3, p.177-225, 11 April 2005
	Yaoyun Shi, Tensor norms and the classical communication complexity of nonlocal quantum measurement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ashwin Nayak , Julia Salzman, Limits on the ability of quantum states to convey classical messages, Journal of the ACM (JACM), v.53 n.1, p.184-206, January 2006
	John Watrous, PSPACE has constant-round quantum interactive proof systems, Theoretical Computer Science, v.292 n.3, p.575-588, 31 January 2003
	Scott Aaronson , Avi Wigderson, Algebrization: a new barrier in complexity theory, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Dmitry Gavinsky , Julia Kempe , Iordanis Kerenidis , Ran Raz , Ronald de Wolf, Exponential separations for one-way quantum communication complexity, with applications to cryptography, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Dmitry Gavinsky, Classical interaction cannot replace a quantum message, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Anne Broadbent , Alain Tapp, Can quantum mechanics help distributed computing?, ACM SIGACT News, v.39 n.3, September 2008
	Scott Aaronson , Avi Wigderson, Algebrization: A New Barrier in Complexity Theory, ACM Transactions on Computation Theory (TOCT), v.1 n.1, p.1-54, February 2009
	Iordanis Kerenidis, Quantum multiparty communication complexity and circuit lower bounds, Mathematical Structures in Computer Science, v.19 n.1, p.119-132, February 2009