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

Simple item page
dc.creatorManin, Yuri I.
dc.date1999-03-02
dc.date.accessioned2026-07-07T06:16:15Z
dc.date.available2026-07-07T06:16:15Z
dc.descriptionThis 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.
dc.description27 pp., no figures, amstex
dc.identifierhttps://arxiv.org/abs/quant-ph/9903008
dc.identifierhttp://arxiv.org/abs/quant-ph/9903008
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/94002
dc.subjectQuantum Physics
dc.subjectQuantum Algebra
dc.titleClassical computing, quantum computing, and Shor's factoring algorithm
dc.typetext

Files

Collections

arXiv