Classical computing, quantum computing, and Shor's factoring algorithm

Abstract

This is an expository talk written for the Bourbaki Seminar. After a brief introduction, Section 1 discusses in the categorical language the structure of the classical deterministic computations. Basic notions of complexity icluding the P/NP problem are reviewed. Section 2 introduces the notion of quantum parallelism and explains the main issues of quantum computing. Section 3 is devoted to four quantum subroutines: initialization, quantum computing of classical Boolean functions, quantum Fourier transform, and Grover's search algorithm. The central Section 4 explains Shor's factoring algorithm. Section 5 relates Kolmogorov's complexity to the spectral properties of computable function. Appendix contributes to the prehistory of quantum computing.

27 pp., no figures, amstex

References in corpus (1)

• Quantum Mechanics helps in searching for a needle in a haystack

Cited by in corpus (13)

• A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points
• Spin network quantum simulator
• A Survey of Quantum Learning Theory
• Quantum Computing: Lecture Notes
• Renormalization and computation I: motivation and background
• Complexity vs Energy: Theory of Computation and Theoretical Physics
• Georg Cantor and his heritage
• Renormalization and Computation II: Time Cut-off and the Halting Problem
• Normalizer Circuits and Quantum Computation
• Neural codes and homotopy types: mathematical models of place field recognition
• The information-theoretical viewpoint on the physical complexity of classical and quantum objects and their dynamical evolution
• Semiclassical Shor's Algorithm
• The influence of quantum noise on the Grover algorithm and quantum Fourier transform: quantum operations theory approach