{"id":6913,"date":"2013-02-06T09:09:02","date_gmt":"2013-02-06T16:09:02","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=6913"},"modified":"2013-02-06T09:09:02","modified_gmt":"2013-02-06T16:09:02","slug":"simple-circuit-factors-arbitrarily-large-numbers","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2013\/02\/06\/simple-circuit-factors-arbitrarily-large-numbers\/","title":{"rendered":"Simple circuit "factors" arbitrarily large numbers"},"content":{"rendered":"

Last Thursday, at the QIP<\/a> rump session in Beijing, John Smolin described recent work with Graeme Smith and Alex Vargo [SSV]<\/a> showing that arbitrarily large numbers $latex N$ can be factored by using this constant-sized quantum circuit
\n\"\"
\nto implement a compiled version of Shor’s algorithm.\u00a0 The key to SSV’s breathtaking improvement is to choose a base for exponentiation,\u00a0$latex a$, such that the function $latex a^x bmod N$ is periodic with period 2.\u00a0 (This kind of\u00a0 simplification—using a base with a short period such as 2, 3, or 4—has in fact been used in all experimental demonstrations of Shor’s algorithm that we know of).\u00a0 SSV\u00a0 go on to show that an $latex a$ with period 2 exists for every product of distinct primes $latex N=pq$, and therefore that the circuit above can be used to factor any such number, however large.\u00a0 The problem, of course, is that in order to find a 2-periodic base $latex a$, one needs to know the factorization of $latex N$. After pointing this out, and pedantically complaining that any process requiring the answer to be known in advance ought not to be called compilation, the authors forge boldly on and note that their circuit can be simplified even further to a classical fair coin toss, giving a successful factorization whenever it is iterated sufficiently many times to obtain both a Head and a Tail among the outcomes (like having enough kids to have both a girl and a boy). \u00a0 Using a penny and two different US quarters, they successfully factor 15, RSA-768, and a 20,000-bit number of their own invention by this method, and announce plans for implementing the full circuit above on state-of-the art superconducting hardware.\u00a0 When I asked the authors of SSV what led them into this line of research, they said they noticed that the number of qubits used to do Shor demonstrations has been decreasing over time, even as the number being factored increased from 15 to 21, and they wanted to understand why.\u00a0 Alas news travels faster than understanding—there have already been inquiries as to whether SSV might provide a practical way of factoring without the difficulty and expense of building a large-scale quantum computer.<\/p>\n","protected":false},"excerpt":{"rendered":"

Last Thursday, at the QIP rump session in Beijing, John Smolin described recent work with Graeme Smith and Alex Vargo [SSV] showing that arbitrarily large numbers $latex N$ can be factored by using this constant-sized quantum circuit to implement a compiled version of Shor’s algorithm.\u00a0 The key to SSV’s breathtaking improvement is to choose a … <\/p>\n

Continue reading “Simple circuit "factors" arbitrarily large numbers”<\/span><\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[20,38,65,66],"tags":[],"class_list":["post-6913","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-hype","category-quantum-computing","category-quantum-computing-bastardizations"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6913","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=6913"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6913\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=6913"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=6913"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=6913"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}