IQI Weekly Seminar

ABSTRACT: One of the best lower bound methods for the quantum communication complexity of a function H is the logarithm of the approximate rank of the communication matrix of H. It was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank.

In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. based on the cheat sheet framework of Aaronson et al. Our main technical result is a lower bound on the quantum communication complexity of a lookup function in terms of the discrepancy of the original function, which we do via quantum information theoretic arguments.

This is joint work with Anurag Anshu, Shalev Ben-David, Rahul Jain, Robin Kothari and Troy Lee.