Classical computing, quantum computing, and Shor's factoring algorithm | alphaXiv
BlogMCP Server
PaperBlogAudio
/ -
Hide ToolsCtrl + /
Open Tools
Abstract<br>This is an expository talk written for the Bourbaki Seminar. After a brief<br>introduction, Section 1 discusses in the categorical language the structure of<br>the classical deterministic computations. Basic notions of complexity icluding<br>the P/NP problem are reviewed. Section 2 introduces the notion of quantum<br>parallelism and explains the main issues of quantum computing. Section 3 is<br>devoted to four quantum subroutines: initialization, quantum computing of<br>classical Boolean functions, quantum Fourier transform, and Grover's search<br>algorithm. The central Section 4 explains Shor's factoring algorithm. Section 5<br>relates Kolmogorov's complexity to the spectral properties of computable<br>function. Appendix contributes to the prehistory of quantum computing.
arXiv:quant-ph/9903008v1 2 Mar 1999 CLASSICAL COMPUTING, QUANTUM COMPUTING, AND SHOR’S FACTORING ALGORITHM 1 Yu. I. Manin Max–Planck–Institut f¨ur Mathematik, Bonn, Germany 0. Why quantum computing? Information processing (computing) is the dynamical evolution of a highly orga- nized physical system produced by technology (computer) or nature (brain). The initial state of this system is (determined by) its input; its final state is the output. Physics describes nature in two complementary modes: classical and quantum. Up to the nineties, the basic mathematical models of computing, Turing machines, were classical objects, although the first suggestions for studying quantum models date back at least to 1980. Roughly speaking, the motivation to study quantum computing comes from several sources: physics and technology, cognitive science, and mathematics. We will briefly discuss them in turn. (i) Physically, the quantum mode of description is more fundamental than the classical one. In the seventies and eighties it was remarked that, because of the superposition principle, it is computationally unfeasible to simulate quantum pro- cesses on classical computers ([Po], [Fe1]). Roughly speaking, quantizing a classical system with N states we obtain a quantum system whose state space is an (N − 1)– dimensional complex projective space whose volume grows exponentially with N. One can argue that the main preoccupation of quantum chemistry is the struggle with resulting difficulties. Reversing this argument, one might expect that quan- tum computers, if they can be built at all, will be considerably more powerful than classical ones ([Fe1], [Ma2]). Progress in the microfabrication techniques of modern computers has already led us to the level where quantum noise becomes an essential hindrance to the error– free functioning of microchips. It is only logical to start exploiting the essential quantum mechanical behavior of small objects in devising computers, instead of neutralizing it. (ii) As another motivation, one can invoke highly speculative, but intriguing, conjectures that our brain is in fact a quantum computer. For example, the recent progress in writing efficient chess playing software (Deep Blue) shows that to sim- ulate the world championship level using only classical algorithms, one has to be able to analyze about 10 6 positions/sec and use about 10 10 memory bytes. Since the characteristic time of neuronal processing is about 10 −3 sec, it is very difficult 1 Talk at the Bourbaki Seminar, June 1999. 1
2 to explain how the classical brain could possibly do the job and play chess as suc- cessfully as Kasparov does. A less spectacular, but not less resource consuming task, is speech generation and perception, which is routinely done by billions of hu- man brains, but still presents a formidable challenge for modern computers using classical algorithms. Computational complexity of cognitive tasks has several sources: basic variables can be fields; a restricted amount of small blocks can combine into exponentially growing trees of alternatives; databases of incompressible information have to be stored and searched. Two paradigms have been developed to cope with these difficulties: logic–like languages and combinatorial algorithms, and statistical matching of observed data to an unobserved model (see D. Mumford’s paper [Mu] for a lucid discussion of the second paradigm.) In many cases, the second strategy efficiently supports an acceptable perfor- mance, but usually cannot achieve excellency of the Deep Blue level. Both paradigms require huge computational resources, and it is not clear, how they can be organized, unless hardware allows massive parallel computing. The idea of “quantum parallelism” (see sec. 2 below) is an appealing theoretical alternative. However, it is not at all clear that it can be made compatible with the available experimental evidence, which depicts the central nervous system as a distinctly classical device. The following way out might be worth exploring. The implementation of effi-...