Chattopadhyay, Mande and Sherif (to appear in STOC 2019)
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 of Computing 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.
Joint work with Ronald de Wolf.