{"id":862,"date":"2011-12-03T17:27:37","date_gmt":"2011-12-03T22:27:37","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=862"},"modified":"2017-01-12T16:40:19","modified_gmt":"2017-01-12T21:40:19","slug":"quantum-algorithms-for-quantum-field-theories","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=862","title":{"rendered":"Quantum Algorithms for Quantum Field Theories"},"content":{"rendered":"

For weeks, I’ve been meaning to blog about an important recent paper by Stephen Jordan, Keith Lee, and John Preskill, entitled Quantum Algorithms for Quantum Field Theories<\/a>. \u00a0So I’m now doing so.<\/p>\n

As long as I’ve been in quantum computing, people have been wondering aloud about the computational power of realistic quantum field theories<\/em> (for example, the Standard Model of elementary particles). \u00a0But no one seemed to have any detailed analysis of this question (if there’s something I missed, surely commenters will let me know). \u00a0The “obvious” guess would be that realistic quantum field theories should provide exactly the same computational power as “ordinary,” nonrelativistic quantum mechanics—in other words, the power of BQP (the class of problems solvable in polynomial time by a quantum computer). \u00a0That would be analogous to the situation in classical<\/em> physics, where bringing in special relativity dramatically changes our understanding of space, time, matter, and energy, but seems (unlike quantum mechanics) to have little or no\u00a0effect on which computational problems can be solved efficiently. \u00a0Analogously, it would seem strange if quantum field theories (QFTs)—which tie together quantum mechanics, special relativity, and detailed knowledge about the elementary particles and their interactions, but seen from far enough away are “just” quantum mechanics—forced any major revision to quantum computing theory.<\/p>\n

Until now, though, there seems to have been only one detailed analysis supporting that conclusion, and it applied to (2+1)-dimensional\u00a0topological<\/em> QFTs<\/a> (TQFTs) only, rather than “realistic” (3+1)-dimensional QFTs. \u00a0This was the seminal work of Freedman, Kitaev, and Wang<\/a>\u00a0and Freedman, Larsen, and Wang<\/a>\u00a0in 2000. \u00a0(Six years later, Aharonov, Jones, and Landau<\/a> gave a more computer-science-friendly version, by directly proving the BQP-completeness of approximating the Jones polynomial<\/a> at roots of unity. \u00a0The latter problem was known to be closely-related to simulating TQFTs, from the celebrated work of Witten and others in the 1980s.) \u00a0To a theoretical computer scientist, dropping from three to two spatial dimensions might not sound like a big deal, but what’s important is that the relevant degrees of freedom become “topological”, making possible a clean, simple model of computation. \u00a0For “realistic” QFTs, by contrast, it wasn’t even obvious how to define<\/em>\u00a0a model of computation; putting realistic QFTs on a rigorous mathematical footing remains a notorious open problem<\/a>.<\/p>\n

In their new paper, Jordan, Lee, and Preskill say that they give an algorithm, running on a “conventional” quantum computer, to estimate scattering probabilities in a class of QFTs called “continuum \u03c64<\/sup>\u00a0theories.” Their algorithm uses time polynomial in the number of incoming particles in the scattering experiment and in their total energy, and inversely polynomial in the desired precision \u03b5 and in the distance \u03bb-\u03bbc<\/sub> between the QFT’s coupling constant \u03bb and a phase transition \u03bbc<\/sub>. \u00a0(In d=2 spatial dimensions, they say the dependence on the precision scales like (1\/\u03b5)2.376<\/sup>, the 2.376 coming from matrix multiplication. Naturally, that should now be amended to (1\/\u03b5)2.373<\/sup>.) \u00a0To develop their algorithm, Jordan et al. apparently had to introduce some new techniques for coping with the error incurred by discretizing QFTs. \u00a0No classical algorithm is known with similar scaling—so when suitably formalized, the “QFT simulation problem” might indeed be in BQP-BPP, matching the uninformed doofus intuition of complexity theorists like me. \u00a0Jordan et al. don’t say whether the problem they’re solving is also BQP-complete; I imagine that could be a topic for future research. \u00a0They also don’t say whether their precision parameter \u03b5\u00a0bounds the variation distance<\/em> between the real and simulated output distributions (rather than just the differences between probabilities of individual<\/i> scattering outcomes); I hope they or someone else will be able to clarify that point.<\/p>\n

In case it isn’t obvious yet, let me make it crystal-clear that I lack the physics background to evaluate Jordan et al.’s work in a serious technical way. \u00a0All I can say with confidence is that the small number of people who (1) have<\/em> the requisite background and (2) care about computational complexity, will probably spend non-negligible time discussing and understanding this paper in the weeks and months to come.<\/p>\n

\n

Conflict-of-Interest Warning:<\/strong><\/span> At a deep, subconscious level, I probably chose to blog about Jordan et al.’s paper not for any legitimate scientific reason, but simply because I know John Preskill and Stephen Jordan personally, and, despite being physicists, they’re both tremendously-respected colleagues who’ve made\u00a0many outstanding contributions to quantum computing theory besides this one. \u00a0Then again, everything I’ve ever done—and everything you’ve<\/em> ever done—has probably had such unsavory hidden motives as well, so who’s counting? \u00a0In all of history, there have only been ten or twenty people whose commitment to scientific objectivity has been absolute and pure, and since they comment on complexity blogs anonymously, we’ll probably never even know their names…<\/p>\n","protected":false},"excerpt":{"rendered":"

For weeks, I’ve been meaning to blog about an important recent paper by Stephen Jordan, Keith Lee, and John Preskill, entitled Quantum Algorithms for Quantum Field Theories. \u00a0So I’m now doing so. As long as I’ve been in quantum computing, people have been wondering aloud about the computational power of realistic quantum field theories (for […]<\/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-862","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\/862","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=862"}],"version-history":[{"count":8,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/862\/revisions"}],"predecessor-version":[{"id":3128,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/862\/revisions\/3128"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=862"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=862"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=862"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}