11 citations · 21 across the 4 of their papers we have counts for
Showing 2000 · quant-phShow all
3 papers · 2 filters
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
Quantum algorithms for solvable groups
John Watrous
In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing eq…
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…