Article

Free access

Exponential separation of quantum and classical communication complexity

Author:

Ran RazAuthors Info & Claims

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

Pages 358 - 367

https://doi.org/10.1145/301250.301343

Published: 01 May 1999 Publication History

PDF eReader

References

[1]

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).

Google Scholar

[2]

N. Alon and J.H. Spencer, The Probabilistic Methods John Wiley & Sons Inc., 1992.

Google Scholar

[3]

A. Ambainis, L. Schulmaa, A. Ta-Shma, U. Vazirant and A. Wigderson, "The quantum communication complexity of sampling", Proc. of the 39th IEEE Syrup. Found. of Computer Science, 1998.

Digital Library

Google Scholar

[4]

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.

Google Scholar

[5]

H. Buhrman, R. Cleve and A. Wigderson, "Quantum vs. classical communication and computation', Proe. 30th Ann. A CM .qymp. Theor. Cornput., 1998. (Also in quant-ph/9802040).

Digital Library

Google Scholar

[6]

D. Bouwmeester, J-W. Pan, K. Mattle, H. Weinfurter and A. Zeilinger, "Experimental quantum teleportation", Nature, 390, pp.575-579, 1997.

Crossref

Google Scholar

[7]

E. Bernstein and U. Vazirani, "Quantum complexity theory", SIAM J. of Comput., 26 (5), pp.1411- 1473, 1997. (Also in STOC 1993).

Digital Library

Google Scholar

[8]

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).

Crossref

Google Scholar

[9]

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.

Google Scholar

[10]

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.

Crossref

Google Scholar

[11]

I. Kremer, Quantum Communication~ MSc Thesis, Computer Science Department, The Hebrew University, 1995.

Google Scholar

[12]

E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press, 1997.

Digital Library

Google Scholar

[13]

B. Kalyanasundaram and G. Schnitger, "The probabitistic communication complexity of set intersection'', SIAM J. on Disc. Math., 5 (4), pp. 545- 557, 1992. (Also in Structures in complexity theory 1987).

Digital Library

Google Scholar

[14]

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).

Crossref

Google Scholar

[15]

V.D. Milman and G. Schechtman, Asymptotic Theory of Finite Dimensional Norme~ Spaces, Springer-Verlag, 1986.

Digital Library

Google Scholar

[16]

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.

Crossref

Google Scholar

[17]

I. Newman, "Private vs. common random bits in communication complexity", Information Processing Letters, 39, pp.67-71, 1991.

Digital Library

Google Scholar

[18]

J. Preskill, Lecture notes on quantum information and quantum computation~ http://www.theory, caltech.edu/people/preskitl/ph229/

Google Scholar

[19]

A.A. Razborov, "On the Distributional Complexity of Disjointness", Theoretical Computer science, 106 (2), pp.385-390, 1992. (Also in ICALP 1990).

Digital Library

Google Scholar

[20]

P~W. Shot, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM d. o.f GomputJ, 26 (5), pp. 1484- 1509, 1997. (Also in FOCS 1994).

Digital Library

Google Scholar

[21]

A.C.C. Yao, "Some complexity questions related to distributive compu~ing~" Proc. 11~h Ann. A GM Syrup. Theor. Comput., 209-213, 1979.

Digital Library

Google Scholar

[22]

A.C.C. ~ao, "Quantum circuit complexity", Proc. of the 3~th IEEE Syrup. Fouad. of Computer Science, pp. 352-361, 1993.

Google Scholar

Cited By

View all

Rozema LStrömberg TCao HGuo YLiu BWalther P(2024)Experimental aspects of indefinite causal order in quantum mechanicsNature Reviews Physics10.1038/s42254-024-00739-86:8(483-499)Online publication date: 19-Jul-2024
https://doi.org/10.1038/s42254-024-00739-8
Banchi LPereira JJose SSimeone O(2024)Statistical Complexity of Quantum LearningAdvanced Quantum Technologies10.1002/qute.202300311Online publication date: 14-Apr-2024
https://doi.org/10.1002/qute.202300311
Arunachalam SGirish U(2023)Trade-Offs Between Entanglement and CommunicationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.25(1-23)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.25
Show More Cited By

Index Terms

Exponential separation of quantum and classical communication complexity
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Models of computation
    1. Probabilistic computation

Recommendations

Exponential separation of quantum communication and classical information
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP ...
Exponential separation of quantum and classical one-way communication complexity
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x ∈ (0, 1)ⁿ and Bob gets a perfect matching M ...
Exponential Separation of Quantum and Classical Online Space Complexity
Special Issue: Symposium on Parallelism in Algorithms and Architectures 2006; Guest Editors: Robert Kleinberg and Christian Scheideler

Although quantum algorithms realizing an exponential time speed-up over the best known classical algorithms exist, no quantum algorithm is known performing computation using less space resources than classical algorithms. In this paper, we study, for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

May 1999

790 pages

ISBN:1581130678

DOI:10.1145/301250

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC99

Sponsor:

SIGACT

STOC99: ACM Symposium on Theory of Computing

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
1,307
Total Downloads

Downloads (Last 12 months)274
Downloads (Last 6 weeks)25

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rozema LStrömberg TCao HGuo YLiu BWalther P(2024)Experimental aspects of indefinite causal order in quantum mechanicsNature Reviews Physics10.1038/s42254-024-00739-86:8(483-499)Online publication date: 19-Jul-2024
https://doi.org/10.1038/s42254-024-00739-8
Banchi LPereira JJose SSimeone O(2024)Statistical Complexity of Quantum LearningAdvanced Quantum Technologies10.1002/qute.202300311Online publication date: 14-Apr-2024
https://doi.org/10.1002/qute.202300311
Arunachalam SGirish U(2023)Trade-Offs Between Entanglement and CommunicationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.25(1-23)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.25
Renner MTavakoli AQuintino M(2023)Classical Cost of Transmitting a QubitPhysical Review Letters10.1103/PhysRevLett.130.120801130:12Online publication date: 22-Mar-2023
https://doi.org/10.1103/PhysRevLett.130.120801
Van Meter RSatoh RBenchasattabuse NTeramoto KMatsuo THajdusek MSatoh TNagayama SSuzuki S(2022)A Quantum Internet Architecture2022 IEEE International Conference on Quantum Computing and Engineering (QCE)10.1109/QCE53715.2022.00055(341-352)Online publication date: Sep-2022
https://doi.org/10.1109/QCE53715.2022.00055
Ho JMoreno GBrito SGraffitti FMorrison CNery RPickston AProietti MRabelo RFedrizzi AChaves R(2022)Entanglement-based quantum communication complexity beyond Bell nonlocalitynpj Quantum Information10.1038/s41534-022-00520-88:1Online publication date: 3-Feb-2022
https://doi.org/10.1038/s41534-022-00520-8
Girish URaz RTal A(2022)Quantum versus Randomized Communication Complexity, with Efficient PlayersComputational Complexity10.1007/s00037-022-00232-731:2Online publication date: 28-Oct-2022
https://dl.acm.org/doi/10.1007/s00037-022-00232-7
Rad F(2021)From Far East to Baltic SeaInternational Journal of Enterprise Information Systems10.4018/IJEIS.202110010517:4(85-97)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.4018/IJEIS.2021100105
Sherstov AStorozhenko AWu PKhuller SVassilevska Williams V(2021)An optimal separation of randomized and Quantum query complexityProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451019(1289-1302)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451019
Leung DNayak AShayeghi ATouchette DYao PYu N(2021)Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large AlphabetsIEEE Transactions on Information Theory10.1109/TIT.2021.308622167:8(5443-5490)Online publication date: Aug-2021
https://doi.org/10.1109/TIT.2021.3086221
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Exponential separation of quantum communication and classical information

Exponential separation of quantum and classical one-way communication complexity

Exponential Separation of Quantum and Classical Online Space Complexity