{"id":2820,"date":"2016-06-20T11:47:44","date_gmt":"2016-06-20T15:47:44","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2820"},"modified":"2017-01-12T17:06:37","modified_gmt":"2017-01-12T22:06:37","slug":"entanglement-without-end","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2820","title":{"rendered":"Entanglement without end"},"content":{"rendered":"

Today we take a break from this blog’s usual round of topics—free will, consciousness, the Singularity, social justice, Donald Trump—to talk about something really<\/em> crazy and left-field. \u00a0Namely, recent research in quantum information.<\/p>\n

Earlier this month,\u00a0William Slofstra<\/a>, currently a Research Assistant Professor at the IQC in\u00a0Waterloo, posted a breakthrough paper<\/a> on the arXiv (yeah, I’m using the b-word again—sue me), which\u00a0solves one\u00a0version of a ten-year-old problem in entanglement theory called Tsirelson’s Problem<\/a>. \u00a0The problem, in one sentence, asks whether all quantum-mechanical correlations that can be\u00a0achieved using commuting measurements, can also be achieved\u00a0using measurements\u00a0on separate parts of a tensor-product Hilbert space. \u00a0The answer turns out to be no<\/strong>. \u00a0(We’ve long known that the two kinds of correlations are identical as long as you stick to finite-dimensional Hilbert spaces, but Slofstra shows that they can differ in\u00a0infinite-dimensional spaces.)<\/p>\n

One\u00a0implication\u00a0of Slofstra’s result\u00a0can be stated much more concretely,\u00a0in terms of two-prover games<\/em>: those things like the famous\u00a0Bell\/CHSH experiment<\/a>, where Alice and Bob are put in separate rooms, and get inputs x<\/em> and y<\/em>\u00a0respectively, and then without communicating, have to produce outputs a<\/em> and b<\/em>\u00a0respectively satisfying some relation V<\/em>(x<\/em>,y<\/em>,a<\/em>,b<\/em>). \u00a0We’ve long known examples of two-prover games, like the Mermin-Peres magic square game<\/a>, that can be won 100% of the time if Alice and Bob share quantum entanglement, but that can’t be won 100% of the time in a classical universe. \u00a0Slofstra gives the first example of something different: namely, a two-prover game that can be won 100% of the time using commuting measurements in an\u00a0<\/strong>infinite-dimensional Hilbert space—something “formally within the rules of quantum mechanics”—but that can’t be won 100% of the time using any finite number of qubits of entanglement.<\/strong><\/p>\n

(Previously, Leung, Toner, and Watrous<\/a>\u00a0had given a simpler example of such a game, but theirs required the referee to exchange quantum messages with Alice and Bob.)<\/p>\n

If that’s not\u00a0enough, Slofstra’s construction also shows that, given as input a description of a two-prover game, it’s undecidable<\/em> (as in, equivalent to\u00a0the halting problem) whether Alice and Bob can win the game with certainty using commuting measurements on an infinite-dimensional Hilbert space. \u00a0Notoriously, quantum computing\u00a0theorists have been unable to put any<\/em> upper bound (not even “computable”) on the complexity class MIP*<\/a>, consisting of languages that admit multi-prover interactive systems with entangled provers—precisely because they’ve\u00a0been unable to bound how much entanglement the provers might need to implement their optimal strategy. \u00a0Slofstra’s result helps to explain why this problem\u00a0has been so vexing. \u00a0I hasten to add, though, that his result doesn’t imply that MIP* contains anything uncomputable, since it remains plausible that anything Alice and Bob can do with infinite entanglement, they can approximate well enough with a finite amount.<\/p>\n

That last remark leads to a\u00a0further\u00a0fundamental question, one that Slofstra leaves open. \u00a0Namely,\u00a0even if Alice and Bob need infinite entanglement to win Slofstra’s game\u00a0with certainty,\u00a0can they at least win it\u00a0with probability arbitrarily close<\/em> to 100%, using larger and larger finite amounts of entanglement? \u00a0More broadly, could there exist a game that was winnable with certainty using infinite\u00a0entanglement, but with at most (say) 90% probability using any<\/em> finite amount of entanglement? \u00a0That problem was shown, by Ozawa<\/a> (see also\u00a0Scholz and Werner<\/a>), to be equivalent to a famous unsolved problem in operator algebras called the Connes embedding problem<\/a>.<\/p>\n

Clarifying the matter further, Slofstra (following earlier authors<\/a>) points out that there are really\u00a0four<\/em> classes of two-prover games in play here:<\/p>\n

    \n
  1. Games\u00a0that can be won with certainty using some fixed, finite amount of entanglement.<\/li>\n
  2. Games\u00a0that can be won with certainty using an infinite amount of entanglement, but\u00a0still in a tensor-product Hilbert space, HA<\/sub>\u2297HB<\/sub>.<\/li>\n
  3. Games\u00a0that can be won with probability approaching<\/em> 1, using an infinite sequence of strategies from class 1, or equivalently (as it turns out) from class 2.<\/li>\n
  4. Games\u00a0that can be won with certainty using measurements by Alice and Bob on an infinite-dimensional quantum state |\u03c8\u3009, where we require all of Alice’s measurements to commute with all of Bob’s,\u00a0but don’t require |\u03c8\u3009 to have a tensor-product structure.<\/li>\n<\/ol>\n

    It can be shown that 1 is a subset of 2 is a subset of 3 is a subset of 4. \u00a0Previously, we didn’t know any<\/em> of these containments to be strict. \u00a0Slofstra’s result shows that class 2 differs from class 4—and as a consequence, that class 1 differs from class 4 as well. \u00a0The Connes embedding problem, which remains open, asks whether 3 differs from 4. \u00a0It also remains open whether 1 differs from 2 and whether 2 differs from 3.<\/p>\n

    \n

    OK, you ask, but what’s the broader importance of any of this? \u00a0To me, these problems touch on a question of almost metaphysical significance: namely, what sorts of experimental evidence could possibly bear\u00a0on whether\u00a0the universe was discrete or continuous?<\/em><\/p>\n

    Because of the Bekenstein bound from quantum gravity, I’m of the opinion\u00a0that the Hilbert spaces relevant to our universe are ultimately finite-dimensional—or more concretely, that any bounded physical system can\u00a0store at most ~1069<\/sup> qubits per square meter of surface area. \u00a0And in quantum computing and information, almost\u00a0everything we care about only requires\u00a0finite-dimensional Hilbert spaces—the subject of this blog post being a\u00a0striking exception!<\/p>\n

    Yet if you take a traditional quantum mechanics course, virtually every example you see will involve infinite<\/em>-dimensional Hilbert spaces—starting with the harmonic oscillator, the hydrogen atom, and coherent states of light. \u00a0And indeed, when I’ve banged the drum about finite-dimensional QM being the truly fundamental kind, physicists have often\u00a0retorted by pointing to\u00a0one of the very first things they learn: the position\/momentum commutation relation<\/a>, which only makes sense in infinite-dimensional Hilbert space. \u00a0Of course,\u00a0if you tried to probe<\/em>\u00a0position\/momentum commutation\u00a0to greater and greater\u00a0precision, eventually your experiments would run up against the limits of quantum gravity, so this retort doesn’t imply\u00a0that infinite dimensions actually exist at the\u00a0machine-code level of the universe. \u00a0But still: is there some\u00a0conceivable<\/em> experiment for which a positive result would show us\u00a0that Nature wasn’t describable by a finite number of qubits, but only by an infinite number?<\/p>\n

    A few years ago, Tobias Fritz wrote a lovely paper<\/a> about precisely that question. \u00a0He gave an example of an identity—namely,<\/p>\n

    V-1<\/sup>U2<\/sup>V=U3<\/sup> implies UV-1<\/sup>UV=V-1<\/sup>UVU<\/p>\n

    —that holds for all finite dimensional unitary matrices U and V, but fails badly for certain infinite-dimensional ones. \u00a0He suggested that, if this identity were discovered\u00a0to fail, then Occam’s Razor would favor an infinite-dimensional Hilbert space for our universe.<\/p>\n

    Unfortunately, Fritz’s example is open to the same sort of objection that Slofstra’s game is. \u00a0Namely, as Fritz points out,\u00a0if the antecedent (V-1<\/sup>U2<\/sup>V=U3<\/sup>) held to excellent precision but not perfectly, then his identity could “fail to within experimental limits,” even if our universe had a finite-dimensional Hilbert space and therefore satisfied his identity.<\/p>\n

    OK, but suppose that the Connes embedding problem had a negative answer—or equivalently, that there existed a two-prover game G that could be won with certainty using commuting operators, but that couldn’t be won (say) 90% of the time using any finite amount of entanglement. \u00a0In that case, the believers in a quantumly finite universe, like myself, would have to put some real money on the table, in much the same way the\u00a0original Bell inequality forced the believers in Einsteinian local\u00a0hidden variables\u00a0to put money down. \u00a0We finitists would have to say\u00a0that the game G couldn’t<\/em>\u00a0be won with certainty in the real world, even though formally, winning G with certainty wouldn’t seem to contradict either quantum mechanics or locality. \u00a0And if, hypothetically, an experiment showed that G could<\/em> be won with certainty—or indeed, with any probability bounded above 90%—then our position would’ve been falsified, much like\u00a0the Bell experiments falsified Einsteinian locality.<\/p>\n

    \n

    So how did Slofstra prove his result? \u00a0I’ll be brief, since STOC’2016<\/a> is happening in Cambridge right now, and I’d like to get over there in time for lunch.<\/p>\n

    If you like, the key idea is to start with equations that have infinite-dimensional solutions but no finite-dimensional ones. \u00a0The most famous such equation is the position\/momentum commutation relation mentioned earlier, which for our purposes is just the following matrix equation:<\/p>\n

    AB – BA = I.<\/p>\n

    This equation can’t be satisfied by any finite-dimensional matrices, since AB and BA have the same trace<\/a>, so Tr(AB-BA)=0, but Tr(I) is nonzero. \u00a0But, OK, let A be the infinite-dimensional linear operator\u00a0that takes as input the coefficients of a polynomial c0<\/sub>+c1<\/sub>x+c2<\/sub>x2<\/sup>+… and that differentiates the polynomial, and let B be the linear operator\u00a0that multiplies the polynomial by x. \u00a0Then I invite you to check that the equation holds.<\/p>\n

    It’s not known at present how to turn the above equation into a two-prover game—I regard it as a fascinating question whether that’s possible. \u00a0Rather than an algebraic equation\u00a0(involving both addition and multiplication), Slofstra instead needs to start with group<\/em> equations (involving only multiplication)—ones with the strange property that they’re satisfied only by the identity matrix\u00a0or\u00a0by infinite matrices. \u00a0Equivalently, he needs a group, defined by a finite list of generators and relations, that admits\u00a0no nontrivial finite-dimensional matrix representations. \u00a0Fortunately for him, such groups exist—the first known example being Higman’s group<\/a>, discovered in 1951. \u00a0Higman’s group is\u00a0generated by four elements, a,b,c,d, which satisfy the equations<\/p>\n

    a-1<\/sup>ba = b2<\/sup>, \u00a0 \u00a0b-1<\/sup>cb = c2<\/sup>, \u00a0 \u00a0c-1<\/sup>dc = d2<\/sup>, \u00a0 \u00a0d-1<\/sup>ad = a2<\/sup>.<\/p>\n

    I don’t have a good intuition for Higman’s group, but if I did, it would come from rereading this post by Terry Tao<\/a>. \u00a0Certainly it has no known “physics interpretation”\u00a0analogous to that for the position\/momentum commutation relation.<\/p>\n

    Anyway, given such a group, the hard part, the new part, is to give a general way to convert them into the kinds of groups that can be realized\u00a0as two-prover games. \u00a0So that’s what Slofstra does, using 50 pages dense with commutative diagrams, quotient maps, and other Serious Math Stuff—hey, I told you this part of the post would be brief! \u00a0For more, see his paper<\/a>.<\/p>\n

    Now, once you have this general transformation of groups, you can also use it to show that there’s no algorithm to decide whether a two-prover game has a perfect commuting strategy, by taking the word problem for groups<\/a>, which is known to be undecidable, and reducing it to that problem.<\/p>\n

    Anyway, infinite congrats (or the limit of arbitrarily large finite congrats?) to Slofstra for this achievement! \u00a0Now it’s off to STOC, which I guess you could also ask me about in the comments if you wanted.<\/p>\n

    \n

    Unrelated Announcement (June 21):<\/b><\/span> Ran Raz asks me to announce a workshop for Avi Wigderson’s 60th birthday<\/a>, to be held at the Institute for Advanced Study in Princeton October 6-8. \u00a0I’ll be speaking there, and I hope to see many of you there as well!<\/p>\n","protected":false},"excerpt":{"rendered":"

    Today we take a break from this blog’s usual round of topics—free will, consciousness, the Singularity, social justice, Donald Trump—to talk about something really crazy and left-field. \u00a0Namely, recent research in quantum information. Earlier this month,\u00a0William Slofstra, currently a Research Assistant Professor at the IQC in\u00a0Waterloo, posted a breakthrough paper on the arXiv (yeah, I’m […]<\/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_feature_clip_id":0,"_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,15,4],"tags":[],"class_list":["post-2820","post","type-post","status-publish","format-standard","hentry","category-complexity","category-csphysics-deathmatch","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\/2820","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=2820"}],"version-history":[{"count":20,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2820\/revisions"}],"predecessor-version":[{"id":3131,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2820\/revisions\/3131"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2820"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2820"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2820"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}