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.
P. Pfeifer and C. Hou, "Quantum Computing: From Bragg Reflections to Decoherence Estimates," Materials Research Society Symposium - Proceedings, vol. 746, pp. 265-276, Cambridge University Press, Jan 2002.
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)
Article - Journal
© 2002 Cambridge University Press, All rights reserved.