dorsal/arxiv
View SchemaClassical computing, quantum computing, and Shor's factoring algorithm
| Authors | Yuri I. Manin |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9903008 |
| URL | https://arxiv.org/abs/quant-ph/9903008 |
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.
{
"annotation_id": "bcd7d64a-b227-4f10-8a72-b6390bd83137",
"date_created": "2026-03-02T18:02:44.263000Z",
"date_modified": "2026-03-02T18:02:44.263000Z",
"file_hash": "47d819d072ea331a0aef4b18b67a5e4a9bac8509cdeee366e73b876b083e81ac",
"private": false,
"record": {
"abstract": "This is an expository talk written for the Bourbaki Seminar. After a brief\nintroduction, Section 1 discusses in the categorical language the structure of\nthe classical deterministic computations. Basic notions of complexity icluding\nthe P/NP problem are reviewed. Section 2 introduces the notion of quantum\nparallelism and explains the main issues of quantum computing. Section 3 is\ndevoted to four quantum subroutines: initialization, quantum computing of\nclassical Boolean functions, quantum Fourier transform, and Grover\u0027s search\nalgorithm. The central Section 4 explains Shor\u0027s factoring algorithm. Section 5\nrelates Kolmogorov\u0027s complexity to the spectral properties of computable\nfunction. Appendix contributes to the prehistory of quantum computing.",
"arxiv_id": "quant-ph/9903008",
"authors": [
"Yuri I. Manin"
],
"categories": [
"quant-ph",
"math.QA"
],
"title": "Classical computing, quantum computing, and Shor\u0027s factoring algorithm",
"url": "https://arxiv.org/abs/quant-ph/9903008"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5ff3836b-c427-4305-826e-da7d286edfcc",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}