{"id":2996,"date":"2016-11-24T10:02:30","date_gmt":"2016-11-24T15:02:30","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2996"},"modified":"2017-01-12T09:10:03","modified_gmt":"2017-01-12T14:10:03","slug":"non-trump-related-quantum-computing-news","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2996","title":{"rendered":"Quantum computing news (98% Trump-free)"},"content":{"rendered":"

(1) Apparently Microsoft has decided to make a major investment in building\u00a0topological quantum computers, which will include hiring Charles Marcus and Matthias Troyer among others. \u00a0See here<\/a> for their blog post, and here<\/a> for the New York Times<\/em> piece. \u00a0In the race to implement\u00a0QC among the established\u00a0corporate labs, Microsoft thus joins the Martinis group at Google, as well as\u00a0the IBM group at T. J. Watson—though both Google and IBM are focused on superconducting\u00a0qubits, rather than the more exotic nonabelian anyon approach that Microsoft has long favored and is now doubling down on. \u00a0I don’t really know more about this new initiative beyond what’s in the articles, but I know many of the people involved, they’re some of the most serious in the business, and Microsoft intensifying its commitment to QC can only be good for the field. \u00a0I wish the new effort every success, despite being personally agnostic between superconducting qubits, trapped ions, photonics, nonabelian anyons, and other QC hardware proposals—whichever one gets there first is fine with me!<\/p>\n

\n

(2) For me, though, perhaps the most exciting QC development of the last month was a new preprint\u00a0by my longtime friend Dorit Aharonov and her colleague Yosi Atia, entitled Fast-Forwarding of Hamiltonians and Exponentially Precise Measurements<\/a>. \u00a0In this work, Dorit and Yosi wield the clarifying sword of\u00a0computational complexity at one\u00a0of the most historically confusing issues in quantum mechanics: namely, the so-called “time-energy uncertainty principle<\/a>” (TEUP).<\/p>\n

The TEUP says that, just as position and momentum are conjugate in quantum mechanics, so too are energy and time—with greater precision in energy corresponding to lesser precision in time and vice versa. \u00a0The trouble is, it was never 100%\u00a0clear what the TEUP even meant<\/em>—after all, time isn’t even an observable in quantum mechanics, just an external parameter—and, to whatever extent the TEUP did<\/em>\u00a0have a definite meaning, it wasn’t clear that it was true. \u00a0Indeed, as Dorit and Yosi’s\u00a0paper discusses in detail, in 1961 Dorit’s uncle Yakir Aharonov, together with David Bohm, gave a counterexample to a natural interpretation of the TEUP. \u00a0But, despite this and other counterexamples, the general feeling among physicists—who, after all, are physicists!—seems to have been that\u00a0some\u00a0corrected\u00a0version of the\u00a0TEUP should hold “in all reasonable circumstances.”<\/p>\n

But, OK, what do we mean by a “reasonable circumstance”? \u00a0This is where Dorit and Yosi come in. \u00a0 In the new work, they present a compelling case that the TEUP should really be formulated as a tradeoff between the precision of energy measurements and circuit complexity<\/em> (that is, the minimum number of gates needed to implement the energy measurement)—and in that amended form, the TEUP holds for exactly those Hamiltonians H that can’t be “computationally fast-forwarded.” \u00a0In other words, it holds whenever applying the unitary transformation e-iHt<\/sup> requires\u00a0close to t computation steps, when there’s no magical shortcut that lets you simulate t steps of time evolution with only (say) log(t) steps. \u00a0And, just as the physicists handwavingly thought, that should indeed hold for “generic” Hamiltonians H (assuming BQP\u2260PSPACE), although it’s possible to use Shor’s algorithm, for finding the order of an element in a multiplicative group, to devise a counterexample to it.<\/p>\n

Anyway, there’s lots of other stuff in the paper, including a connection to the stuff Lenny Susskind and I have been doing about the “generic” growth of circuit complexity, in the CFT dual of an expanding wormhole (where we also needed to assume BQP\u2260PSPACE and closely related complexity separations, for much the same reasons). \u00a0Congratulations to Dorit and Yosi for once again illustrating the long reach<\/a> of computational complexity in physics, and for giving me a reason to be happy this month!<\/p>\n

\n

(3) As many of you will have seen, my former MIT colleagues, Lior Eldar and Peter Shor, recently posted an arXiv preprint\u00a0claiming a\u00a0bombshell result: namely, a\u00a0polynomial-time quantum algorithm<\/a> to solve a variant of the Closest Vector Problem in lattices. \u00a0Their claimed algorithm\u00a0wouldn’t yet<\/em>\u00a0break lattice-based cryptography<\/a>, but if the approximation factors could be improved, it would be well on the way to doing so. \u00a0This has been one of the most tempting targets for quantum algorithms research for more than\u00a0twenty years—ever since Shor’s “original” algorithm<\/a> laid waste to RSA, Diffie-Hellman, elliptic-curve cryptography, and more in a world with scalable quantum computers, leaving lattice-based cryptography as one of the few\u00a0public-key crypto proposals still standing.<\/p>\n

Unfortunately, Lior tells me that Oded Regev has discovered a flaw in the algorithm, which he and Peter don’t currently know how to fix. \u00a0So for now, they’re withdrawing the paper (because of the Thanksgiving holiday, the\u00a0withdrawal won’t take effect on the arXiv until Monday). \u00a0It’s still a worthy attempt on a great problem—here’s hoping that they or someone else manage to, as Lior put it to me, “make the algorithm great again.”<\/p>\n","protected":false},"excerpt":{"rendered":"

(1) Apparently Microsoft has decided to make a major investment in building\u00a0topological quantum computers, which will include hiring Charles Marcus and Matthias Troyer among others. \u00a0See here for their blog post, and here for the New York Times piece. \u00a0In the race to implement\u00a0QC among the established\u00a0corporate labs, Microsoft thus joins the Martinis group at […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":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},"_wpas_customize_per_network":false},"categories":[5,4],"tags":[],"class_list":["post-2996","post","type-post","status-publish","format-standard","hentry","category-complexity","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2996","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2996"}],"version-history":[{"count":4,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2996\/revisions"}],"predecessor-version":[{"id":3001,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2996\/revisions\/3001"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2996"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2996"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2996"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}