{"id":6703,"date":"2012-10-29T19:11:53","date_gmt":"2012-10-30T02:11:53","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=6703"},"modified":"2012-10-29T19:11:53","modified_gmt":"2012-10-30T02:11:53","slug":"3-7-21","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2012\/10\/29\/3-7-21\/","title":{"rendered":"21 = 3 * 7"},"content":{"rendered":"<p>&#8230;with high probability.<br \/>\nThat joke was recycled, and in <a href=\"http:\/\/arxiv.org\/abs\/1111.4147v2\">recent work<\/a>, <a href=\"http:\/\/www.bristol.ac.uk\/physics\/research\/quantum\/\">Bristol experimentalists<\/a> have found a way to recycle photonic qubits to perform Shor&#8217;s algorithm using only $latex lceil log Nrceil + 1$ qubits.  (Ok, so actually is was Kitaev who figured this out, as they are basically using Kitaev&#8217;s <a href=\"http:\/\/www.cs.berkeley.edu\/~vazirani\/s07quantum\/notes\/phase.pdf\">semi-classical QFT<\/a>.  But they found a way to do this with photons.)  Further reductions on the number of qubits can be achieved by &#8220;compiling&#8221; to throw out the unused ones.  In this case, we are left with a qubit and a qutrit.  The feedback of the measurement is also replaced with the usual postselection.  However, buried in the <a href=\"http:\/\/arxiv.org\/pdf\/1111.4147v2.pdf\">body of the paper<\/a> is the main advance:<\/p>\n<blockquote><p>Our scheme therefore requires two consecutive photonic CNOT gates&#8211;something that has not previously been demonstrated&#8211;acting on qubit subspaces of the qutrit.<\/p><\/blockquote>\n<p>This is important progress, but until the factored numbers get a lot larger, the &#8220;size of number factored&#8221; yardstick is going to be a frustrating one.  For example, how is it that <a href=\"http:\/\/arxiv.org\/abs\/1111.3726\">factoring 143<\/a> on an NMR quantum computer takes only 4 qubits while <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0112176\">factoring 15<\/a> takes 7?<br \/>\nAnyone have ideas for something more objective, like a quantum analogue of MIPS?  (Incidentally, apparently MIPS is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Instructions_per_second\">obsolete<\/a> because of memory hierarchies.)  Perhaps Grover&#8217;s algorithm would be good, as &#8220;compiling&#8221; is harder to justify, and noise is <a href=\"http:\/\/arxiv.org\/abs\/1202.1027\">harder to survive<\/a>.<br \/>\n<b>Update:<\/b><br \/>\nIn the <a href=\"https:\/\/dabacon.org\/pontiff\/?p=6703#comment-667341\">comments<\/a>, Tom Lawson points out the real significance of factoring 21.  This is the smallest example of factoring in which the desired distribution is not uniformly random, thus making it possible to distinguish the successful execution of an experiment from the effects of noise.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>&#8230;with high probability. That joke was recycled, and in recent work, Bristol experimentalists have found a way to recycle photonic qubits to perform Shor&#8217;s algorithm using only $latex lceil log Nrceil + 1$ qubits. (Ok, so actually is was Kitaev who figured this out, as they are basically using Kitaev&#8217;s semi-classical QFT. But they found &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/dabacon.org\/pontiff\/2012\/10\/29\/3-7-21\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;21 = 3 * 7&#8221;<\/span><\/a><\/p>\n","protected":false},"author":3,"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":[63,65],"tags":[],"class_list":["post-6703","post","type-post","status-publish","format-standard","hentry","category-quantum","category-quantum-computing"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6703","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\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=6703"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6703\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=6703"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=6703"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=6703"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}