836 citations · 837 across the 2 of their papers we have counts for
Showing 2000Show all
2 papers · 1 filter
quant-ph2000
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…
quant-ph2000
Fast parallel circuits for the quantum Fourier transform
Richard Cleve, John Watrous
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log (1/epsilon)) on the circuit depth for computing an…