ABSTRACTWe give an exposition of the principles of quantum computing (logic gates, exponential parallelism from polynomial hardware, fast quantum algorithms, quantum error correction, hardware requirements, and experimental milestones). A compact description of the quantum Fourier transform to find the period of a function—the key step in Shor's factoring algorithm—illustrates how parallel state evolution along many classical computational paths produces fast algorithms by constructive interference similar to Bragg reflections in x-ray crystallography. On the hardware side, we present a new method to estimate critical time scales for the operation of a quantum computer. We derive a universal upper bound on the probability of a computation to fail due to decoherence (entanglement of the computer with the environment), as a function of time. The bound is parameter-free, requiring only the interaction between the computer and the environment, and the time-evolving state in the absence of any interaction. For a simple model we find that the bound performs well and decoherence is small when the energy of the computer state is large compared to the interaction energy. This supports a recent estimate of minimum energy requirements for quantum computation.