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

<!DOCTYPE html> <html lang="fr"> <head> <title> Classical computing, quantum computing, and Shor's factoring algorithm </title> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/> <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1.0, minimum-scale=1.0"> <link rel="shortcut icon" type="image/x-icon" href="/static/numdam/img/numdam_favicon.ico"> <link rel="stylesheet" href="//fonts.googleapis.com/css?family=Lato"/> <link rel="stylesheet" href="/static/ptf/vendors/bootstrap/css/bootstrap.min.css"/> <link rel="stylesheet" href="/static/ptf/vendors/font-awesome/css/font-awesome.min.css"> <link rel="stylesheet" href="/static/ptf/vendors/lightbox/css/lightbox.css"> <link rel="stylesheet" href="/static/ptf/css/ptf.css" type="text/css"/> <link rel="stylesheet" href="/static/ptf/css/search-bar.css" type="text/css"/> <link rel="stylesheet" href="/static/numdam/vendors/owl-carousel/css/owl.carousel.css"> <link rel="stylesheet" href="/static/numdam/vendors/owl-carousel/css/owl.theme.css"> <link rel="stylesheet" href="/static/numdam/css/numdam.css" type="text/css"/> </head> <body id="page-" style="font-family: ;font-size: px;"> <div id="main"> <div id="top"> <div id="bandeau"> <div style="float:left"> <a href="/" class='no-focus'> <img src="/static/numdam/img/numdam_logo.gif" title='Accueil' alt='Accueil' class='logo no-text-decoration'/> </a> </div> <div class="bandeau-background"> <div style="float:left;width:calc(50% - 16px)"> </div> <div style="float:left" class="smartphone"> <div class="dropdown"> <button class="btn light-blue dropdown-toggle" type="button" data-toggle="dropdown"> <img src='/static/mersenne_cms/img/main-menu.svg' alt='main-menu'/> </button> <ul class="dropdown-menu"> <li><a href="/journals/">Revues</a></li> <li><a href="/actas/">S茅minaires</a></li> <li><a href="/proceedings/">Congr猫s</a></li> <li><a href="/books/">Livres</a></li> <li><a href="/lectures">Notes de cours</a></li> <li><a href="/thesis">Th猫ses</a></li> <li><a href="/authors">Auteurs</a></li> </ul> </div> </div> </div> <div class="onoffswitch-group"> <div id="language-switch" title="Cliquer pour afficher le site en anglais"> <form id="language-switch-form" action="/i18n/setlang/" method="post"><input type="hidden" name="csrfmiddlewaretoken" value="f3u2RznPtZa0BuGGlTDazSBPE4aJGlVq5CLXmZk2zdiMl1oMLbUmEA8XFhh4kM3f"> <div class="onoffswitch" id="lang_flags"> <input type="checkbox" name="language" value="en" class="onoffswitch-checkbox" id="lang_onoffswitch" checked> <label class="onoffswitch-label" for="lang_onoffswitch"> <span class="onoffswitch-inner" data-on="" data-off=""></span> <span class="onoffswitch-switch"></span> </label> </div> </form> </div> <div id="mathml-switch" title="Cliquer pour afficher le code source TeX" > <form action="/set-formula-display/" method="post"><input type="hidden" name="csrfmiddlewaretoken" value="f3u2RznPtZa0BuGGlTDazSBPE4aJGlVq5CLXmZk2zdiMl1oMLbUmEA8XFhh4kM3f"> <div class="onoffswitch"> <input type="checkbox" name="formula-display" value="tex" class="onoffswitch-checkbox" id="tex_onoffswitch" onclick="this.form.submit();" > <label class="onoffswitch-label" for="tex_onoffswitch"> <span class="onoffswitch-inner" data-on="TeX" data-off="TeX"></span> <div class="onoffswitch-switch"> <div class="onoffswitch-switch-label"> OFF</div> </div> </label> </div> </form> </div> </div> </div> <nav class="navbar navbar-default desktop"> <div class="container-fluid"> <ul class="nav navbar-nav"> <li ><a href="/journals/">Revues</a></li> <li ><a href="/actas/">S茅minaires</a></li> <li ><a href="/proceedings/">Congr猫s</a></li> <li class="active"><a href="/books/">Livres</a></li> <li ><a href="/lectures">Notes de cours</a></li> <li ><a href="/thesis">Th猫ses</a></li> <li ><a href="/authors">Auteurs</a></li> </ul> </div> </nav> <div id="bandeau3"> <div class="container" id="search-bar"> <div> <form class="form-horizontal" method="post" action="/search"><input type="hidden" name="csrfmiddlewaretoken" value="f3u2RznPtZa0BuGGlTDazSBPE4aJGlVq5CLXmZk2zdiMl1oMLbUmEA8XFhh4kM3f"> <div class="form-group"> <div class="col-sm-offset-1 col-xs-8" id="line-container"> <div class="input-group search-group"> <div class="search-group-inner"> <input class="searchinput form-control" type="text" name="q0" value="" placeholder="Rechercher des articles, des livres..."/> <span class="searchclear glyphicon glyphicon-remove"></span> </div> <div class="input-group-btn" id="search-group-btn"> <input type="hidden" name="qt0" value="all"> <button type="button" class="btn btn-default dropdown-toggle" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false"> Tout <span class="caret"></span> </button> <ul class="dropdown-menu"> <li><a href="#">Tout</a></li> <li><a href="#">Auteur</a></li> <li><a href="#">Titre</a></li> <li><a href="#">Bibliographie</a></li> <li><a href="#">Plein texte</a></li> </ul> <button id="add-search-field" type="button" class="btn btn-default"> <span class="glyphicon glyphicon-plus"></span> </button> </div> </div> </div> <div class="col-xs-2 search-button-div"> <button type="submit" class="btn search-button" name="Submit"> <span class="glyphicon glyphicon-search"></span> <span id="search-button-text">Rechercher</span> </button> <a href="/help/"><img src="/static/mersenne_cms/img/question.png"></a> </div> </div> </form> <div id="template-search-form" style="display:none"> <div class="input-group search-group search-group-added"> <div class="input-group-addon"> <input class="bt-checkbox" type="checkbox" name="not##i##" /> <span style="line-height:20px">NOT</span> </div> <div class="search-group-inner"> <input class="searchinput form-control" type="text" name="q##i##"/> <span class="searchclear glyphicon glyphicon-remove"></span> </div> <div style="display:none" class="bt-input-with-text">   <span class="bt-input-text-between">Entre</span> <input class="form-control-in" type="text" name="q-f-##i##" placeholder="Ann茅e" /> <span class="bt-input-text">et</span> <input class="form-control-in" type="text" name="q-l-##i##" placeholder="Ann茅e" />   </div> <span class="input-group-btn"> <input type="hidden" name="qt##i##" value="author"> <button type="button" class="btn btn-default dropdown-toggle" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false"> Auteur <span class="caret"></span> </button> <ul class="dropdown-menu"> <li><a href="#">Tout</a></li> <li><a href="#">Auteur</a></li> <li><a href="#">Titre</a></li> <li><a href="#">Date</a></li> <li><a href="#">Bibliographie</a></li> <li><a href="#">Mots-cl茅s</a></li> <li><a href="#">Plein texte</a></li> </ul> <button type="button" class="btn btn-default remove-search-field"> <span class="glyphicon glyphicon-minus"></span> </button> </span> </div> </div> </div> </div> </div> </div> <div class="container"> </div> <div id="content" class="wrapper-float"> <div id="left"> <div id="content_left"> <div class="cover-thumbnail"> <a href="/icon/SB/SB_1998-1999__41_/couv1.jpg" class="lightbox" title=""> <img src="/icon/SB/SB_1998-1999__41_/couv1_small.jpg" width="80px"> </a> </div> </div> </div> <div id="center"> <div class="row breadcrumb-row"> <div class="col-xs-12"> <div class="breadcrumb-lg"> <div style="float:left"> <ul class="cms-breadcrumb"> <li class="breadcrumb-previous"> <a href="/item/SB_1998-1999__41__351_0/">Pr茅c茅dent</a> </li> </ul> </div> <div style="float:left"> <ul class="cms-breadcrumb"> <li class=""> <a href="/item/AST/">Ast茅risque</a> </li> <li class=""> <a href="/item/SB_1998-1999__41_/">no. 266</a> </li> <li class="active"> <a href="/item/SB_1998-1999__41__375_0/">Expos茅 no. 862</a> </li> </ul> </div> <div style="float:left"> <ul class="cms-breadcrumb"> <li class="breadcrumb-next"> <a href="/item/SB_1998-1999__41__405_0/">Suivant</a> </li> </ul> </div> </div> <div class="breadcrumb-sm"> <a href="BreadcrumbItem(title='Suivant', url='/item/SB_1998-1999__41__405_0/', icon_class='', html=False)" class="btn btn-default"><i class="glyphicon glyphicon-chevron-right"></i></a> </div> <div class="clearfix"> </div> </div> </div> <div id="article-div" class="article-div" style="margin-left:-15px"> <div class="row " style="margin:0px"> <div class="float-minus-100"> <div style="font-size:18px;margin-bottom:10px"> <span class="common-title article-title"> Classical computing, quantum computing, and Shor's factoring algorithm </span> </div> <div class="article-author" style="display:inline-block"> <div style="margin-bottom:5px; font-size: 16px"> <a class="author_link" href="/search?"Manin, Yuri I."-c">Manin, Yuri I.</a><sup><a href="https://www.idref.fr/058586407" target="_blank"><img style="width:16px;margin-top:-3px;margin-left:3px" src='/static/ptf/img/logo-idref.png'></a></sup> </div> </div> <div style="margin-bottom:10px"> <span style="display:inline-block;">S茅minaire Bourbaki : volume 1998/99, expos茅s 850-864, </span> Ast茅risque, no. 266 (2000), Expos茅 no. 862, 30 p. </div> <div style="margin-top:20px;margin-bottom:10px"> <div class="wrapper-float"> <div style="float:left;margin-top:0px"> <a href="/item/SB_1998-1999__41__375_0.pdf" target="_blank"> <img src="/static/ptf/img/pdf.gif"> </a> <a href="/item/SB_1998-1999__41__375_0.djvu"> <img src="/static/ptf/img/djvu.png"> </a> </div> </div> </div> </div> <div style="float:left;margin-top:20px;width:98px;padding-right:10px;padding-left:15px;"> <a href="https://smf.emath.fr"><img src="/static/mersenne_cms/img/logo-societe-mathematique-de-france.jpg" width="80px"></a> </div> </div> <div class="row" style="margin:0px"> <div class="col-xs-12"> <div style="margin-top:10px;margin-bottom:10px"> <ul class="nav nav-tabs article-tab"> <li class="nav-item active"><a class="nav-link active" data-bs-toggle="tab" data-toggle="tab" data-bs-target="#info-tab" href="#info-tab">D茅tail</a></li> <li class="nav-item"><a class="nav-link" data-bs-toggle="tab" data-toggle="tab" data-bs-target="#citation-tab" href="#citation-tab">Export</a></li> <li class="nav-item "> <a class="nav-link " data-bs-toggle="tab" data-toggle="tab" data-bs-target="#how-to-cite-tab" href="#how-to-cite-tab">Comment citer</a> </li> </ul> <div class="tab-content" style="margin-top:10px"> <div id="info-tab" class="tab-pane fade in active"> <span class="publication-date-info">  <div style="margin-top:5px"> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1772680" class="badge badge-secondary ref-badge extid-badge"> MR </a>   <a href="https://zbmath.org/?q=an:1005.81014" class="badge badge-secondary ref-badge extid-badge"> Zbl </a> </div> <div style="margin-top:5px"> </div> </div> <div id="citation-tab" class="tab-pane fade"> <div class="upper"> <ul class="nav nav-pills"> <li role="presentation" class="active"><a data-toggle="pill" href="#bibtex">BibTeX</a></li> <li role="presentation"><a data-toggle="pill" href="#ris">RIS</a></li> <li role="presentation"><a data-toggle="pill" href="#enw">EndNote</a></li> </ul> <div class="tab-content"> <div id="bibtex" class="tab-pane fade in active"> <pre class="upper-right-content" id="bibtex-div">@incollection{SB_1998-1999__41__375_0, author = {Manin, Yuri I.}, title = {Classical computing, quantum computing, and {Shor's} factoring algorithm}, booktitle = {S\'eminaire Bourbaki : volume 1998/99, expos\'es 850-864}, series = {Ast\'erisque}, note = {talk:862}, pages = {375--404}, publisher = {Soci\'et\'e math\'ematique de France}, number = {266}, year = {2000}, mrnumber = {1772680}, zbl = {1005.81014}, language = {en}, url = {https://www.numdam.org/item/SB_1998-1999__41__375_0/} }</pre> <button class="fa fa-clipboard copy-button btn btn-primary" data-clipboard-action="copy" data-clipboard-target="#bibtex-div" aria-hidden="true" title="Copier dans le presse-papier"></button> <a class="fa fa-download export-button btn btn-primary" title="T茅l茅charger" href="/export_citation/SB_1998-1999__41__375_0/bib/"></a> </div> <div id="ris" class="tab-pane fade"> <pre class="upper-right-content" id="ris-div">TY - CHAP AU - Manin, Yuri I. TI - Classical computing, quantum computing, and Shor's factoring algorithm BT - S茅minaire Bourbaki : volume 1998/99, expos茅s 850-864 AU - Collectif T3 - Ast茅risque N1 - talk:862 PY - 2000 SP - 375 EP - 404 IS - 266 PB - Soci茅t茅 math茅matique de France UR - https://www.numdam.org/item/SB_1998-1999__41__375_0/ LA - en ID - SB_1998-1999__41__375_0 ER - </pre> <button class="fa fa-clipboard copy-button btn btn-primary" data-clipboard-action="copy" data-clipboard-target="#ris-div" aria-hidden="true" title="Copier dans le presse-papier"></button> <a class="fa fa-download export-button btn btn-primary" title="T茅l茅charger" href="/export_citation/SB_1998-1999__41__375_0/ris/"></a> </div> <div id="enw" class="tab-pane fade"> <pre class="upper-right-content" id="enw-div">%0 Book Section %A Manin, Yuri I. %T Classical computing, quantum computing, and Shor's factoring algorithm %B S茅minaire Bourbaki : volume 1998/99, expos茅s 850-864 %A Collectif %S Ast茅risque %Z talk:862 %D 2000 %P 375-404 %N 266 %I Soci茅t茅 math茅matique de France %U https://www.numdam.org/item/SB_1998-1999__41__375_0/ %G en %F SB_1998-1999__41__375_0</pre> <button class="fa fa-clipboard copy-button btn btn-primary" data-clipboard-action="copy" data-clipboard-target="#enw-div" aria-hidden="true" title="Copier dans le presse-papier"></button> <a class="fa fa-download export-button btn btn-primary" title="T茅l茅charger" href="/export_citation/SB_1998-1999__41__375_0/enw/"></a> </div> </div> </div> </div> <div id="how-to-cite-tab" class="tab-pane fade "> <div class="upper-right"> <pre class="upper-right-content" id="how-to-cite-div">Manin, Yuri I. Classical computing, quantum computing, and Shor's factoring algorithm, dans <em>S茅minaire Bourbaki : volume 1998/99, expos茅s 850-864</em>, Ast茅risque, no. 266 (2000), Expos茅 no. 862, 30 p. https://www.numdam.org/item/SB_1998-1999__41__375_0/</pre> <button class="fa fa-clipboard copy-button btn btn-primary" data-clipboard-action="copy" data-clipboard-target="#how-to-cite-div" aria-hidden="true" title="Copier dans le presse-papier"></button> </div> </div> </div> </div> </div> </div> <div class="row" style="margin:0px"> <div class="col-xs-12"> <div style="margin-top:30px;margin-bottom:10px"> <ul class="nav nav-tabs article-tab" > <li class="nav-item active" id="main-citations-li" > <a class="nav-link" data-bs-toggle="tab" data-toggle="tab" data-bs-target="#references-tab" href="#references-tab">Bibliographie</a> </li> <li class="nav-item" id="citations-html" style="display:none"> <a class="nav-link" data-bs-toggle="tab" data-toggle="tab" data-bs-target="#citations-tab" href="#citations-tab">Cit茅 par</a> </li> </ul> <div class="tab-content" style="margin-top:10px"> <div id="references-tab" class="tab-pane fade in active"> <div style="margin-top:11px;margin-bottom: 0px"> <p class="bibitemcls " > [BCDP] <span class="citation-author">D. Beckman</span>, <span class="citation-author">A. N. Chari</span>, <span class="citation-author">Sr. Devabhaktuni</span>, <span class="citation-author">J. Preskill</span> - <span class="citation-document-title">Efficient networks for quantum computing</span>. <span class="citation-publication-title">Phys. Rev.</span> A, <span class="citation-volume">54</span>:2 (1996), 1034-1063. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1404473" class="badge badge-secondary ref-badge "> MR </a> </p> <p class="bibitemcls " > [Ben1] <span class="citation-author">P. Benioff</span> - <span class="citation-document-title">The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines</span>, <span class="citation-publication-title">J. Stat. Phys.</span>, <span class="citation-volume">22</span> (1980), 563-591. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=574722" class="badge badge-secondary ref-badge "> MR </a> </p> <p class="bibitemcls " > [Ben2] <span class="citation-author">P. Benioff</span> - <span class="citation-document-title">Quantum mechanical Hamiltonian models of Turing machines that dissipate no energy</span>, <span class="citation-publication-title">Phys. Rev. Lett.</span>, <span class="citation-volume">48</span> (1980), 1581-1585. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=660412" class="badge badge-secondary ref-badge "> MR </a> </p> <p class="bibitemcls " > [BoL] <span class="citation-author">D. Boneh</span>, <span class="citation-author">R. Lipton</span> - <span class="citation-document-title">Quantum cryptoanalysis of hidden linear functions, Proc. of Advances in Cryptology - CRYPTO '95</span>, Springer LN in Computer Science, vol. <span class="citation-volume">963</span> (1995), 424-437. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1445578" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0876.94023" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [BoyBHT] <span class="citation-author">M. Boyer</span>, <span class="citation-author">G. Brassard</span>, <span class="citation-author">P. H酶yer</span>, <span class="citation-author">A. Tapp</span> - <span class="citation-document-title">Tight bounds on quantum searching</span>, Preprint, 1996. </p> <p class="bibitemcls " > [CZ] <span class="citation-author">J. Cirac</span>, <span class="citation-author">P. Zoller</span> - <span class="citation-document-title">Quantum computation with cold trapped ions</span>, <span class="citation-publication-title">Phys. Rev. Lett.</span>, <span class="citation-volume">74</span>:20 (1995), 4091-4094. </p> <p class="bibitemcls " > [Deu] <span class="citation-author">D. Deutsch</span> - <span class="citation-document-title">Quantum theory, the Church-Turing principle and the universal quantum computer</span>, <span class="citation-publication-title">Proc. R. Soc. Lond.</span> <span class="citation-volume">A</span> <span class="citation-volume">400</span> (1985), 97-117. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=801665" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0900.81019" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [DeuJ] <span class="citation-author">D. Deutsch</span>, <span class="citation-author">R. Jozsa</span> - <span class="citation-document-title">Rapid solutions of problems by quantum computation</span>, <span class="citation-publication-title">Proc. Roy. Soc. London</span>, Ser. A, <span class="citation-volume">449</span> (1992), 553-558. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1196433" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0792.68058" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [Fe1] <span class="citation-author">R. Feynman</span> - <span class="citation-document-title">Simulating physics with computers</span>, <span class="citation-publication-title">Int. J. of Theor. Phys.</span>, <span class="citation-volume">21</span> (1982), 467-488. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=658311" class="badge badge-secondary ref-badge "> MR </a> </p> <p class="bibitemcls " > [Fe2] <span class="citation-author">R. Feynman</span>. <span class="citation-document-title">Quantum mechanical computers</span>, <span class="citation-publication-title">Found. Phys.</span>, <span class="citation-volume">16</span> (1986), 507-531. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=895035" class="badge badge-secondary ref-badge "> MR </a> </p> <p class="bibitemcls " > [Fr1] <span class="citation-author">M. Freedman</span> - <span class="citation-document-title">Topological views on computational complexity</span>, <span class="citation-publication-title">In Proc. ICM</span> Berlin 1998, vol. <span class="citation-volume">II</span>, 453-464. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1648095" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0967.68520" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [Fr2] <span class="citation-author">M. Freedman</span> - <span class="citation-document-title">Limit, logic, and computation</span>, <span class="citation-publication-title">Proc. Nat. Ac. Sci. USA</span>, <span class="citation-volume">95</span> (1998), 95-97. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1612421" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0891.68041" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [Fr3] <span class="citation-author">M. Freedman</span> - <span class="citation-document-title">P/NP, and the quantum field computer</span>, <span class="citation-publication-title">Proc. Nat. Ac. Sci. USA</span>, <span class="citation-volume">95</span> (1998), 98-101. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1612425" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0895.68053" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [GaJ] <span class="citation-author">M. Garey</span>, <span class="citation-author">D. Johnson</span> - <span class="citation-document-title">Computers and Intractability: A Guide to the Theory of NP-Completeness</span>, W. H. Freeman and Co., San-Francisco, 1979. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=519066" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0411.68039" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [GeC] <span class="citation-author">N. Gershenfield</span>, <span class="citation-author">I. Chuang</span> - <span class="citation-document-title">Bulk spin-resonance quantum computation</span>, <span class="citation-publication-title">Science</span> <span class="citation-volume">275</span> (1997), 350-355. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1429853" class="badge badge-secondary ref-badge "> MR </a> </p> <p class="bibitemcls " > [Gri] <span class="citation-author">D. Grigoriev</span> - <span class="citation-document-title">Testing the shift-equivalence of polynomials using quantum mechanics</span>, In: <span class="citation-document-title">Manin's Festschrift</span>, <span class="citation-publication-title">Journ. of Math. Sci.</span>, <span class="citation-volume">82</span>:1 (1996), 3184-3193. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1423635" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0999.12017" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [Gro] <span class="citation-author">L. K. Grover</span> - <span class="citation-document-title">Quantum mechanics helps in searching for a needle in a haystack</span>, <span class="citation-publication-title">Phys. Rev. Lett.</span> <span class="citation-volume">79</span> (1997), 325-328. </p> <p class="bibitemcls " > [Ki1] <span class="citation-author">A. Kitaev</span> - <span class="citation-document-title">Quantum computations: algorithms and error correction</span>, <span class="citation-publication-title">Russian Math. Surveys</span>, <span class="citation-volume">52</span>:6 (1997), 53-112. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1611329" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0917.68063" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [Ki2] <span class="citation-author">A. Kitaev</span> - <span class="citation-document-title">Classical and quantum computations</span>, Lecture notes, Independent University, Moscow, 1998. </p> <p class="bibitemcls " > [Ma1] <span class="citation-author">Yu. Manin</span> - <span class="citation-document-title">A Course in Mathematical Logic</span>, Springer Verlag, 1977, pp. xiii+286. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=457126" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0383.03002" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [Ma2] <span class="citation-author">Yu. Manin</span> - <span class="citation-document-title">Computable and uncomputable</span> (in Russian), Moscow, Sovetskoye Radio, 1980. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=611681" class="badge badge-secondary ref-badge "> MR </a> </p> <p class="bibitemcls " > [Mu] <span class="citation-author">D. Mumford</span> - <span class="citation-document-title">The statistical description of visual signals</span>, Preprint. </p> <p class="bibitemcls " > [Po] <span class="citation-author">R. P. Poplavskii</span> - <span class="citation-document-title">Thermodynamical models of information processing</span> (in Russian), <span class="citation-publication-title">Uspekhi Fizicheskikh Nauk</span>, <span class="citation-volume">115</span>:3 (1975), 465-501. </p> <p class="bibitemcls " > [Sa] <span class="citation-author">A. Salomaa</span> - <span class="citation-document-title">Computation and Automata</span>, Cambridge UP, 1985. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=801724" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:0565.68046" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [Sh] <span class="citation-author">P. W. Shor</span> - <span class="citation-document-title">Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer</span>, <span class="citation-publication-title">SIAM J. Comput.</span>, <span class="citation-volume">26</span>:5 (1997), 1484-1509. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1471990" class="badge badge-secondary ref-badge "> MR </a> | <a href="https://zbmath.org/?q=an:1005.11065" class="badge badge-secondary ref-badge "> Zbl </a> </p> <p class="bibitemcls " > [Si] <span class="citation-author">D. Simon</span> - <span class="citation-document-title">On the power of quantum computation</span>, <span class="citation-publication-title">Proc. of the 35th Ann. Symp. on Foundations of Comp. Sci.</span> (1994), 116-123. | <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1489241" class="badge badge-secondary ref-badge "> MR </a> </p> <p class="bibitemcls " > [Ts] <span class="citation-author">B. Tsirelson</span> - <span class="citation-document-title">Quantum information processing</span>, Lecture notes, Tel-Aviv University, 1997. </p> </div> </div> </div> </div> </div> </div> </div> </div> <div id="right"> </div> </div> </div> <div id="footer"> <div class="horizontal-menu menu-footer"> <ul> <li><a href="/about/">脌 propos</a></li> <li><a href="/help/">Aide</a></li> <li><a href="/legal/">Mentions l茅gales</a></li> <li><a href="/contact/">Contact</a></li> </ul> </div> <div class="logo-footer"> <div class="logo-footer-left" style="float:left;"> </div> <div style="float:left"> <div class="lg-desktop"> <p>D茅velopp茅 par</p> </div> <div style="display:inline-block"> <a href="http://www.mathdoc.fr"><img class="logo-auto" src="/static/numdam/img/logo-mathdoc.png"/></a> </div> </div> <div style="float:left;width:5%"> </div> <div style="float:left"> <div class="lg-desktop"> <p>Soutenu par</p> </div> <div style="display:inline-block"> <a href="http://www.cnrs.fr/insmi"><img class="logo-auto" src="/static/numdam/img/logo-insmi.png"/></a>  <a href="http://www.univ-grenoble-alpes.fr/"><img class="logo-auto" src="/static/numdam/img/logo-uga.svg"/></a> </div> </div> <div style="float:left;width:5%"> </div> <div style="float:left"> <div class="lg-desktop"> <p>Partenaire de</p> </div> <div style="display:inline-block"> <a href="http://www.eudml.eu"><img class="logo-auto" src="/static/numdam/img/logo-eudml.png"/></a>  <a href="http://portail.math.cnrs.fr"><img class="logo-auto" src="/static/numdam/img/logo-portail.png"/></a> </div> </div> <div style="float:right; margin-right:20px"> <div id="logo-collex"> <a href="https://www.collexpersee.eu/"><img class="logo-auto" src="/static/numdam/img/logo-collex.png"/></a>  </div> <div id="logo-collex-lg"> <a href="https://www.collexpersee.eu/"><img class="logo-auto" src="/static/numdam/img/logo-collex.png"/></a>  </div> </div> </div> </div> <script type="text/javascript" src="/static/ptf/vendors/jquery/js/jquery-3.5.1.min.js"></script> <script type="text/javascript" src="/static/ptf/vendors/clipboard/js/clipboard.min.js"></script> <script type="text/javascript" src="/static/ptf/vendors/bootstrap/js/bootstrap.min.js"></script> <script type="text/javascript" src="/static/ptf/vendors/lightbox/js/lightbox.js"></script> <script type="text/javascript" src="/static/ptf/js/ptf.js"></script> <script type="text/javascript" src="/static/ptf/js/search-bar.js"></script> <script type="text/javascript" src="/static/numdam/vendors/owl-carousel/js/owl.carousel.min.js"></script> <script type="text/javascript" src="/static/numdam/js/scripts.js"></script> <script src="/static/ptf/js/mathjax-config.js" defer></script> <script type="text/javascript" id="MathJax-script" defer src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"> </script> </body> </html>

CINXE.COM

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