{"id":174433,"date":"2023-10-20T00:39:50","date_gmt":"2023-10-20T05:39:50","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2023\/10\/thirty-years-later-a-speed-boost-for-quantum-factoring"},"modified":"2023-10-20T00:39:50","modified_gmt":"2023-10-20T05:39:50","slug":"thirty-years-later-a-speed-boost-for-quantum-factoring","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2023\/10\/thirty-years-later-a-speed-boost-for-quantum-factoring","title":{"rendered":"Thirty Years Later, a Speed Boost for Quantum Factoring"},"content":{"rendered":"

<\/a><\/p>\n

As Shor looked for applications for his quantum period-finding algorithm, he rediscovered a previously known but obscure mathematical theorem: For every number, there exists a periodic function whose periods are related to the number\u2019s prime factors. So if there\u2019s a number you want to factor, you can compute the corresponding function and then solve the problem using period finding \u2014 \u201cexactly what quantum computers are so good at,\u201d Regev said.<\/p>\n

On a classical computer, this would be an agonizingly slow way to factor a large number \u2014 slower even than trying every possible factor. But Shor\u2019s method speeds up the process exponentially, making period finding an ideal way to construct a fast quantum factoring algorithm.<\/p>\n

Shor\u2019s algorithm was one of a few key early results that transformed quantum computing from an obscure subfield of theoretical computer science to the juggernaut it is today. But putting the algorithm into practice is a daunting task, because quantum computers are notoriously susceptible to errors: In addition to the qubits required to perform their computations, they need many others doing extra work<\/a> to keep them from failing. A recent paper<\/a> by Eker\u00e5 and the Google researcher Craig Gidney<\/a> estimates that using Shor\u2019s algorithm to factor a security-standard 2,048-bit number (about 600 digits long) would require a quantum computer with 20 million qubits. Today\u2019s state-of-the-art machines have at most a few hundred.<\/p>\n","protected":false},"excerpt":{"rendered":"

As Shor looked for applications for his quantum period-finding algorithm, he rediscovered a previously known but obscure mathematical theorem: For every number, there exists a periodic function whose periods are related to the number\u2019s prime factors. So if there\u2019s a number you want to factor, you can compute the corresponding function and then solve the [\u2026]<\/p>\n","protected":false},"author":513,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1523,41,2229,1617,1492],"tags":[],"class_list":["post-174433","post","type-post","status-publish","format-standard","hentry","category-computing","category-information-science","category-mathematics","category-quantum-physics","category-security"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/174433","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/513"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=174433"}],"version-history":[{"count":0,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/174433\/revisions"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=174433"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=174433"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=174433"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}