A new exponential separation between quantum and classical one-way communication complexity

Ashley Montanaro

We present a new example of a partial boolean function whose one-way quantum communication complexity is exponentially lower than its one-way classical communication complexity. Th…