We provide a tight analysis of Grover's algorithm for quantum database searching. We give
a simple closed‐form formula for the probability of success after any given number of …

We give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O(3√N/r)
expected evaluations of the function, where N is the cardinality of the domain. …

Quantum information processing is at the crossroads of physics, mathematics and computer
science. It is concerned with what we can and cannot do with quantum information that goes …

Consider a Boolean function x: X→{0, 1} that partitions set X between its good and bad
elements, where a is good if x (a)= 1 and bad other-wise. Consider also a quantum algorithm A …

We study some extensions of Grover's quantum searching algorithm. First, we generalize the
Grover iteration in the light of a concept called amplitude amplification. Then, we show that …

Bell proved that quantum entanglement enables two spacelike separated parties to exhibit
classically impossible correlations. Even though these correlations are stronger than anything …

Authentication is a well-studied area of classical cryptography: a sender A and a receiver B
sharing a classical secret key want to exchange a classical message with the guarantee that …

We investigate the amount of communication that must augment classical local hidden variable
models in order to simulate the behavior of entangled quantum systems. We consider the …

We investigate how a classical private key can be used by two players, connected by an
insecure one-way quantum channel, to perform private communication of quantum information. …

In a pseudotelepathy game, communication can be entirely replaced by quantum entanglement.
We provide, for the first proposed arid simplest two-player game of this type, the proof …