TY - GEN
T1 - Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
AU - Sinha, Makrand
AU - De Wolf, Ronald
N1 - †Supported by the Netherlands Organization for Scientific Research, Grant Number 617.001.351. ∗Partially supported by ERC Consolidator Grant 615307-QPROGRESS and by QuantERA project QuantAlgo 680-91-034.
PY - 2019/11
Y1 - 2019/11
N2 - 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.
AB - 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.
KW - Approximate rank
KW - Log-rank conjecture
KW - Quantum Communication
UR - http://www.scopus.com/inward/record.url?scp=85078495602&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078495602&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2019.00062
DO - 10.1109/FOCS.2019.00062
M3 - Conference contribution
AN - SCOPUS:85078495602
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 966
EP - 981
BT - Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PB - IEEE Computer Society
T2 - 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Y2 - 9 November 2019 through 12 November 2019
ER -