4.3k citations · 13.4k across the 43 of their papers we have counts for
Showing 2000Show all
3 papers · 1 filter
quant-ph2000★ 12 cited
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★ 82 cited
Classical simulation of quantum entanglement without local hidden variables
Serge Massar, Dave Bacon, Nicolas Cerf +1
Recent work has extended Bell's theorem by quantifying the amount of communication required to simulate entangled quantum systems with classical information. The general scenario i…
quant-ph2000★ 79 cited
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…