Sharp Quantum vs. Classical Query Complexity Separations

J. Niel de Beaudrap, Richard Cleve, John Watrous

We obtain the strongest separation between quantum and classical query complexity known to date -- specifically, we define a black-box problem that requires exponentially many quer…