Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Makrand Sinha, Ronald De Wolf

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Chattopadhyay, Mande and Sherif (CMS19) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-Approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-Approximate-rank conjecture. Our lower bound is based on the fooling distribution method introduced by Rao and Sinha (Theory Comput., 2018) for the classical case and extended by Anshu, Touchette, Yao and Yu (STOC, 2017) for the quantum case. We also give a new proof of the classical lower bound using the fooling distribution method.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Pages966-981
Number of pages16
ISBN (Electronic)9781728149523
DOIs
StatePublished - Nov 2019
Externally publishedYes
Event60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States
Duration: Nov 9 2019Nov 12 2019

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2019-November
ISSN (Print)0272-5428

Conference

Conference60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Country/TerritoryUnited States
CityBaltimore
Period11/9/1911/12/19

Keywords

  • Approximate rank
  • Log-rank conjecture
  • Quantum Communication

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Exponential Separation between Quantum Communication and Logarithm of Approximate Rank'. Together they form a unique fingerprint.

Cite this