1.2k citations · 3k across the 55 of their papers we have counts for
4 papers · 1 filter
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…
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…
Succinct quantum proofs for properties of finite groups
John Watrous
In this paper we consider a quantum computational variant of nondeterminism based on the notion of a quantum proof, which is a quantum state that plays a role similar to a certific…
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…