Abstract

We 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.

Department(s)

Biological Sciences

Keywords and Phrases

Algorithms; Coherent Light; Error Correction; Fiber Bragg Gratings; Fourier Transforms; Mathematical Models; Probability; Reflection; X Ray Crystallography, Bragg Reflections; Decoherence; Quantum Algorithms; Quantum Computing; Quantum Error Correction, Quantum Theory

International Standard Serial Number (ISSN)

0272-9172;1946-4274

Document Type

Article - Journal

Document Version

Accepted Manuscript

File Type

text

Language(s)

English

Rights

© 2002 Cambridge University Press, All rights reserved.

Publication Date

01 Jan 2002

Download

Included in

Biology Commons

Share

 
COinS