IQI Weekly Seminar

Series: Institute for Quantum Information (IQI) Weekly Seminar Series

Separating quantum communication complexity and approximate log-rank

Ankit Garg, Postdoctoral Scholar, Microsoft Research, New England,

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.

For more information, please contact Marcia Brown by phone at 626.395.4013 or by email at [email protected].