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

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.

# Quantum Computing Algorithms and Architecture # Computer Science # Computability, Logic, AI Algorithms # Quantum Information and Cryptography

Yuri I. Manin (1999). "Classical computing, quantum computing, and Shor's factoring algorithm". arXiv (Cornell University). https://doi.org/10.48550/arxiv.quant-ph/9903008