"Quantum Computing 001.ps.gz" - читать интересную книгу автораThis is page 1 Printer: Opaque this Quantum Computation "Because nature isn't classical, dammit..." Richard P. Feynman Andr'e Berthiaume1 ABSTRACT Historically, Turing machines have been the paradigm by which we defined computability and efficiency. This is based on Church's thesis that everything effectively computable can also be computed on a Turing machine. But since our world behaves quantum mechanically, it seems reasonable to also consider computing models that make use of quantum mechanical properties. First stated by Benioff [Ben82] and Feynman [Fey82], this idea was formalized by Deutsch [Deu85] when he introduced his quantum computer and, later on, quantum gate arrays. This paper gives an introduction to quantum computing and briefly looks at a few results in quantum computation, not the least of which is Shor's polynomial time factoring algorithm ([Sho94] and [Sho95]). 1 The Need for Quantum Mechanics Why introduce quantum mechanics in computation? The opening quote, if a little blunt, captures the essence of the answer. At the center of computer science are two questions: what problems are computable and how efficiently can they be computed? Historically, (probabilistic) Turing machines have been the paradigm by which we defined computability and efficiency. This is based on Church's thesis that everything effectively computable can also be computed on a Turing machine. But since our world behaves quantum mechanically, it seems reasonable to also consider computing models that make use of quantum mechanical properties. First stated by Benioff [Ben82] and Feynman [Fey82], this idea was formalized by Deutsch [Deu85] when he defined the first quantum computing model that made full use ofn quantum superposition. This paper gives an introduction to Deutsch's quantum computing model and briefly looks at a few results in quantum computation, not the least of which is Shor's polynomial time factoring algorithm. Before defining a quantum computing model, some basic notions of quan1Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands ([email protected]). This article appeared in "Complexity Theory Retrospective II'', Springer-Verlag, 1996 (Editors: Lane Hemaspaandra and Alan L. Selman). It is reproduced here with Springer-Verlag's kind permission. 2 Andr'e Berthiaume tum mechanics must be introduced. A comprehensive presentation of quantum mechanics is beyond the scope of this paper, but fortunately only the very simplest systems are used for quantum computation: two-state systems or finite groups of two-state systems. The next section introduces the relevant notions for these special cases. Quantum gate arrays will be defined next and, after a few examples of their capabilities, the results leading to Shor's algorithm will be briefly reviewed. The last section addresses some of the difficulties facing the actual construction of a quantum computer. 2 Basic Principles of Quantum Mechanics We now introduce the basic rules of quantum mechanics through a series of principles. Young's celebrated two-slit experiment will serve as a background to illustrate these principles. 2 x 1 s A/B C FIGURE 1. Young's two-slits experiment. Curves A and B show the light intensity when only one hole is open. Curve C shows the interference pattern when both holes are open. (the curves are exaggerated) In Young's experiment (figure 1), light coming out of a hole in the left wall must go through two small holes in the center wall. A detector on the right wall measures the light intensity at different positions along the length of the wall. If only one hole is open, the intensity reaches its maximum at a position directly in line with that hole and the source s. As the detector 1. Quantum Computation 3 moves away from that position, the intensity slowly fades and eventually vanishes. When both holes are open, the intensity pattern is not the sum of the two one-hole intensities, as one would expect, but an alternation of bright and dark fringes. This effect is caused by the interference of the light coming out from both holes. Surprisingly, the interference persists even when the source s is dim enough to send only one photon at a time; if many runs are made and a photon count is kept for various positions, the same pattern of bright and dark fringes appears. Each photon seems to interfere with itself. 2.1 Probability Amplitudes The self-interference appearing in Young's experiment is just one example illustrating that classical intuition cannot be applied to quantum systems. The purpose of this section is not to explain why such strange behavior appears at the quantum level but merely to state the rules for these behaviors. Following Feynman's example [FLS64], these rules are presented as the principles of quantum mechanics. Definition 2.1 For a given experiment, an event is a set of initial and final conditions. |
|
|