{"id":369,"date":"2008-12-03T20:17:06","date_gmt":"2008-12-04T00:17:06","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=369"},"modified":"2008-12-03T20:17:06","modified_gmt":"2008-12-04T00:17:06","slug":"no-no-no","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=369","title":{"rendered":"N\u00f6 n\u00f6 n\u00f6"},"content":{"rendered":"

At least three people have now asked my opinion of the paper Mathematical Undecidability and Quantum Randomness<\/a> by Paterek et al., which claims to link quantum mechanics with G\u00f6delian incompleteness.\u00a0 Abstract follows:<\/p>\n

We propose a new link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms and show that quantum measurements are capable of revealing whether a given proposition is decidable or not within the axiomatic system. Whenever a mathematical proposition is undecidable within the axioms encoded in the state, the measurement associated with the proposition gives random outcomes. Our results support the view that quantum randomness is irreducible and a manifestation of mathematical undecidability.<\/p><\/blockquote>\n

Needless to say, the paper has already been Slashdotted<\/a>.\u00a0 I was hoping to avoid blogging about it, because I doubt I can do so without jeopardizing my quest<\/a> for Obamalike equanimity and composure.\u00a0 But similar to what’s happened several<\/a> times<\/a> before<\/a>, I see colleagues who I respect and admire enormously—in this case, several who have done pioneering experiments that tested quantum mechanics in whole new regimes—making statements that can be so easily misinterpreted by a public and a science press hungry to misinterpret, that I find my fingers rushing to type even as my brain struggles in vain to stop them.<\/p>\n

Briefly, what is the connection the authors seek to make between mathematical undecidability and quantum randomness?\u00a0 Quantum states are identified with the “axioms” of a formal system, while measurements (technically, projective measurements in the Pauli group) are identified with “propositions.”\u00a0 A proposition is “decidable” from a given set of axioms, if and only if the requisite measurement produces a determinate outcome when applied to the state (in other words, if the state is an eigenstate of the measurement).\u00a0 From the simple fact that no one-qubit state can be an eigenstate of the \u03c3x<\/sub> and \u03c3z<\/sub> measurements simultaneously (in other words, the Uncertainty Principle<\/a>), it follows immediately that “no axiom system can decide every proposition.”\u00a0 The authors do some experiments to illustrate these ideas, which (not surprisingly) produce the outcomes predicted by quantum mechanics.<\/p>\n

But does this have anything to do with “undecidability” in the mathematical sense, and specifically with G\u00f6del’s Theorem?\u00a0 Well, it’s not an illustration of G\u00f6del’s Theorem to point out that, knowing only that x=5, you can’t deduce the value of an unrelated variable y.\u00a0 Nor is it an illustration of G\u00f6del’s Theorem to point out that, knowing only one bit about the pair of bits (x,y), you can’t deduce x and y simultaneously.\u00a0 These observations have nothing to do with G\u00f6del’s Theorem.\u00a0 G\u00f6del’s Theorem is about statements that are undecidable within some formal system, despite<\/em> having definite truth-values—since the statements just assert the existence of integers with certain properties, and those properties are stated explicitly. \u00a0To get this kind of undecidability, G\u00f6del had to use axioms that were strong enough to encode the addition and multiplication of integers, as well as the powerful inference rules of first-order logic. \u00a0By contrast, the logical deductions in the Paterek et al. paper consist entirely of multiplications of tensor products of Pauli matrices. \u00a0And the logic of Pauli matrix multiplication (i.e., is this matrix in the subgroup generated by these other matrices or not?) is, as the authors point out, trivially decidable.\u00a0 (The groups in question are all finite, so one can just enumerate their elements—or use Gaussian elimination for greater efficiency.)<\/p>\n

For this reason, I fear that Paterek et al.’s use of the phrase “mathematical undecidability” might mislead people.\u00a0 The paper’s central observation can be re-expressed as follows: given an N-qubit stabilizer state |\u03c8\u232a, the tensor products of Pauli matrices that stabilize |\u03c8\u232a form a group of order 2N<\/sup>. \u00a0On the other hand, the total number of tensor products of Pauli matrices is 4N<\/sup>, and hence the remaining 4N<\/sup>-2N<\/sup> tensor products correspond to “undecidable propositions” (meaning that they’re not in |\u03c8\u232a’s stabilizer group). \u00a0These and other facts about stabilizer states were worked out by Gottesman, Knill, and others in the 1990s.<\/p>\n

(Incidentally, the paper references results of Chaitin, which do interpret variants of G\u00f6del’s Theorem in terms of axiom systems “not containing enough information” to decide Kolmogorov-random sentences. \u00a0But Chaitin’s results don’t actually deal with information in the technical sense, but rather with Kolmogorov complexity. \u00a0Mathematically, the statements Chaitin is talking about have zero information, since they’re all mathematical truths.)<\/font><\/p>\n

So is<\/em> there a connection between quantum mechanics and logic?\u00a0 There is—and it was pointed out by Birkhoff and von Neumann in 1936.\u00a0 Recall that Paterek et al. identify propositions with projective measurements, and axioms with states. \u00a0But in logic, an axiom is just any proposition we assume; otherwise it has the same form as any other proposition.\u00a0 So it seems to me that we ought to identify both propositions and<\/em> axioms with projective measurements. \u00a0States that are eigenstates of all the axioms would then correspond to models<\/em> of those axioms.\u00a0 Also, logical inferences should derive some propositions from other propositions, like so: “any state that is an eigenstate of both X and Y is also an eigenstate of Z.”\u00a0 As it turns out, this is precisely the approach that Birkhoff and von Neumann took; the field they started is called “quantum logic.”<\/p>\n

Update (Dec. 8):<\/font><\/strong> I’ve posted an interesting response<\/a> from Caslav Brukner, and my response<\/a> to his response.<\/p>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

At least three people have now asked my opinion of the paper Mathematical Undecidability and Quantum Randomness by Paterek et al., which claims to link quantum mechanics with G\u00f6delian incompleteness.\u00a0 Abstract follows: We propose a new link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of […]<\/p>\n","protected":false},"author":2,"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_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","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,"jetpack_post_was_ever_published":false},"categories":[30,4],"tags":[],"class_list":["post-369","post","type-post","status-publish","format-standard","hentry","category-mirrored-on-csail-blog","category-quantum"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/369","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=369"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/369\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=369"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=369"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=369"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}