Exponential separation of quantum communication and classical information

Anshu, A; Touchette, D; Yao, P; Yu, N

Exponential separation of quantum communication and classical information

Anshu, A Touchette, D Yao, P Yu, N

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the Annual ACM Symposium on Theory of Computing, 2017, Part F128415 pp. 277 - 288
Issue Date:: 2017-06-19

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download full textAdobe PDF (909.38 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Anshu, A	en_US
dc.contributor.author	Touchette, D	en_US
dc.contributor.author	Yao, P	en_US
dc.contributor.author	Yu, N https://orcid.org/0000-0003-1188-3032	en_US
dc.date.issued	2017-06-19	en_US
dc.identifier.citation	Proceedings of the Annual ACM Symposium on Theory of Computing, 2017, Part F128415 pp. 277 - 288	en_US
dc.identifier.isbn	9781450345286	en_US
dc.identifier.issn	0737-8017	en_US
dc.identifier.uri	http://hdl.handle.net/10453/127332
dc.description.abstract	© 2017 ACM. 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 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. Motivated by the celebrated results of Ganor, Kol and Raz [FOCS 14, pp. 557-566, STOC 15, pp. 977-986], and by Rao and Sinha [ECCC TR15-057], we use the Symmetric k-ary Pointer Jumping function, whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha. As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/2O(b) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.	en_US
dc.relation.ispartof	Proceedings of the Annual ACM Symposium on Theory of Computing	en_US
dc.relation.isbasedon	10.1145/3055399.3055401	en_US
dc.title	Exponential separation of quantum communication and classical information	en_US
dc.type	Conference Proceeding
utslib.citation.volume	Part F128415	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	Part F128415	en_US

Abstract:

© 2017 ACM. 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 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. Motivated by the celebrated results of Ganor, Kol and Raz [FOCS 14, pp. 557-566, STOC 15, pp. 977-986], and by Rao and Sinha [ECCC TR15-057], we use the Symmetric k-ary Pointer Jumping function, whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha. As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/2O(b) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/127332