836 citations · 837 across the 2 of their papers we have counts for
10 papers
Classical and quantum fingerprinting with shared randomness and one-sided error
Rolf T. Horn, A. J. Scott, Jonathan Walgate +3
Within the simultaneous message passing model of communication complexity, under a public-coin assumption, we derive the minimum achievable worst-case error probability of a classi…
Exponential algorithmic speedup by quantum walk
Andrew M. Childs, Richard Cleve, Enrico Deotto +3
We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a c…
A quantum Goldreich-Levin theorem with cryptographic applications
Mark Adcock, Richard Cleve
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the p…
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…
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…
The query complexity of order-finding
Richard Cleve
We consider the problem where P is an unknown permutation on {0,1,...,2^n - 1}, y is an element of {0,1,...,2^n - 1}, and the goal is to determine the minimum r > 0 such that P^r(y…