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

This result makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step.Expand

Abstract Near-optimal strategies are developed for estimating the free energy difference between two canonical ensembles, given a Metropolis-type Monte Carlo program for sampling each one. The… Expand

Computers may be thought of as engines for transforming free energy into waste heat and mathematical work. Existing electronic computers dissipate energy vastly in excess of the mean thermal… 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

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

Let A be a language chosen randomly by tossing a fair coin for each string x to determine whether x belongs to A, and${\bf NP}^A is shown, with probability 1, to contain a-immune set, i.e., a set having no infinite subset in ${\bf P]^A $.Expand

In the classical analog of entanglement-assisted communication - communication over a discrete memoryless channel (DMC) between parties who share prior random information - one parameter is sufficient, i.e., that in the presence of prior shared random information, all DMCs of equal capacity can simulate one another with unit asymptotic efficiency.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

Some mathematical and natural objects (a random sequence, a sequence of zeros, a perfect crystal, a gas) are intuitively trivial, while others (e.g. the human body, the digits of π) contain internal… Expand