A protocol for coin-tossing by exchange of quantum messages is presented, which is secure against traditional kinds of cheating, even by an opponent with unlimited computing power, but ironically can be subverted by use of a still subtler quantum phenomenon, the Einstein-Podolsky-Rosen paradox.Expand

A lower bound on the efficiency of any possible quantum database searching algorithm is provided and it is shown that Grover''s algorithm nearly comes within a factor 2 of being optimal in terms of the number of probes required in the table.Expand

Consider a Boolean function $\chi: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $\chi(x)=1$ and bad otherwise. Consider also a quantum algorithm… Expand

Initial results from an apparatus and protocol designed to implement quantum public key distribution are described, by which two users exchange a random quantum transmission, consisting of very faint flashes of polarized light, which remains secure against an adversary with unlimited computing power.Expand

A more efficient protocol is presented, which leaks an amount of information acceptably close to the minimum possible for sufficiently reliable secret channels (those with probability of any symbol being transmitted incorrectly as large as 15%).Expand

It is proved that relative to an oracle chosen uniformly at random with probability 1 the class $\NP$ cannot be solved on a quantum Turing machine (QTM) in time $o(2^{n/2})$.Expand

This paper provides a general treatment of privacy amplification by public discussion, a concept introduced by Bennett, Brassard and Robert (1988) for a special scenario. The results have… Expand

This paper provides a general treatment of privacy amplification by public discussion, a concept introduced by Bennett, Brassard, and Robert for a special scenario, and yields results on wiretap and broadcast channels for a considerably strengthened definition of secrecy capacity.Expand

In this paper, we investigate how the use of a channel with perfect authenticity but no privacy can be used to repair the defects of a channel with imperfect privacy but no authenticity. More preci...