{"id":3256,"date":"2017-05-24T04:29:59","date_gmt":"2017-05-24T09:29:59","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=3256"},"modified":"2019-01-28T14:24:55","modified_gmt":"2019-01-28T20:24:55","slug":"yet-more-errors-in-papers","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=3256","title":{"rendered":"Yet more errors in papers"},"content":{"rendered":"

Following up on my posts PostBQP Postscripts<\/a> and More Wrong Things I Said In Papers<\/a>, it felt like time for another post in which I publicly flog myself for mistakes in my research papers.  [Warning:<\/strong><\/span> The rest of this post is kinda, sorta technical.  Read at your own risk.]<\/p>\n

\n

(1) In my 2006 paper “Oracles are subtle but not malicious<\/a>,” I claimed to show that if PP is contained in BQP\/qpoly, then the counting hierarchy collapses to QMA (Theorem 5).  But on further reflection, I only know how to show a collapse of the counting hierarchy under the stronger assumption that PP is in BQP\/poly.  If PP is in BQP\/qpoly, then certainly P#P<\/sup>=PP=QMA, but I don’t know how to collapse any further levels of the counting hierarchy.  The issue is this: in QMA, we can indeed nondeterministically guess an (amplified) quantum advice state for a BQP\/qpoly algorithm.  We can then verify that the advice state works to solve PP problems, by using (for example) the interactive protocol for the permanent, or some other #P-complete problem.  But having done that, how do we then unravel the higher levels of the counting hierarchy?  For example, how do we simulate PPPP<\/sup> in PPBQP<\/sup>=PP?  We don’t have any mechanism to pass the quantum advice up to the oracle PP machine, since queries to a PP oracle are by definition classical strings.  We could try to use tools from my later paper with Andy Drucker<\/a>, passing a classical description<\/em> of the quantum advice up to the oracle and then using the description to reconstruct the advice for ourselves.  But doing so just doesn’t seem to give us a complexity class that’s low for PP, which is what would be needed to unravel the counting hierarchy.  I still think this result might be recoverable, but a new idea is needed.<\/p>\n

\n

(2) In my 2008 algebrization paper with Avi Wigderson<\/a>, one of the most surprising things we showed was a general connection between communication complexity lower bounds and algebraic query complexity lower bounds.  Specifically, given a Boolean oracle A:{0,1}n<\/sup>\u2192{0,1}, let ~A be a low-degree extension of A over a finite field F (that is, ~A(x)=A(x) whenever x\u2208{0,1}n<\/sup>).  Then suppose we have an algorithm that’s able to learn some property of A, by making k black-box queries to ~A.  We observed that, in such a case, if Alice is given the top half of the truth table of A, and Bob is given the bottom half of the truth table, then there’s necessarily a communication protocol by which Alice and Bob can learn the same property of A, by exchanging at most O(kn log|F|) bits.  This connection is extremely model-independent: a randomized query algorithm gives rise to a randomized communication protocol, a quantum query algorithm gives rise to a quantum communication protocol, etc. etc.  The upshot is that, if you want to lower-bound the number of queries that an algorithm needs to make to the algebraic extension oracle ~A, in order to learn something about A, then it suffices to prove a suitable communication complexity lower bound<\/em>.  And the latter, unlike algebraic query complexity, is a well-studied subject with countless results that one can take off the shelf.  We illustrated how one could use this connection to prove, for example, that there exists an oracle A such that NPA<\/sup> \u2284 BQP~A<\/sup>, for any low-degree extension ~A of A—a separation that we didn’t and don’t know how to prove any other way. Likewise, there exists an oracle B such that BQPB<\/sup> \u2284 BPP~B<\/sup> for any low-degree extension ~B of B.<\/p>\n

The trouble is, our “proof sketches” for these separations (in Theorem 5.11) are inadequate, even for “sketches.”  They can often be fixed, but only by appealing to special properties of the communication complexity separations in question, properties that don’t necessarily hold for an arbitrary communication separation between two arbitrary models.<\/p>\n

The issue is this: while it’s true, as we claimed, that a communication complexity lower bound implies an algebraic query complexity lower bound, it’s not true in general that a communication complexity upper<\/em> bound implies an algebraic query complexity upper<\/em> bound!  So, from a communication separation between models C and D, we certainly obtain a query complexity problem that’s not in D~A<\/sup>, but then the problem might not be in CA<\/sup>.  What tripped us up was that, in the cases we had in mind (e.g. Disjointness), it’s obvious<\/em> that the query problem is in CA<\/sup>.  In other cases, however, such as Raz’s separation<\/a> between quantum and randomized communication complexity, it probably isn’t even true.  In the latter case, to recover the desired conclusion about algebraic query complexity (namely, the existence of an oracle B such that BQPB<\/sup> \u2284 BPP~B<\/sup>), what seems to be needed is to start from a later quantum vs. classical communication complexity separation due to Klartag and Regev<\/a>, and then convert their communication problem into a query problem using a recent approach by myself and Shalev Ben-David<\/a> (see Section 4).  Unfortunately, my and Shalev’s approach only tells us nonconstructively that there exists<\/em> a query problem with the desired separation, with no upper bound on the gate complexity of the quantum algorithm.  So strictly speaking, I still<\/em> don’t know how to get a separation between the relativized complexity classes BQPB<\/sup> and BPP~B<\/sup> defined in terms of Turing machines.<\/p>\n

In any case, I of course should have realized this issue with the algebrization paper the moment Shalev and I encountered the same issue when writing our later paper.  Let me acknowledge Shalev, as well as Robin Kothari, for helping to spur my realization of the issue.<\/p>\n

\n

In case it wasn’t clear, the mistakes I’ve detailed here have no effect on the main results of the papers in question (e.g., the existence of an oracle relative to which PP has linear-sized circuits; the existence and pervasiveness of the algebrization barrier).  The effect is entirely on various “bonus” results—results that, because<\/em> they’re bonus, were gone over much less carefully by authors and reviewers alike.<\/p>\n

Nevertheless, I’ve always felt like in science, the louder you are about your own mistakes, the better.  Hence this post.<\/p>\n","protected":false},"excerpt":{"rendered":"

Following up on my posts PostBQP Postscripts and More Wrong Things I Said In Papers, it felt like time for another post in which I publicly flog myself for mistakes in my research papers.  [Warning: The rest of this post is kinda, sorta technical.  Read at your own risk.] (1) In my 2006 paper “Oracles […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","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":[31,5,18,4],"tags":[],"class_list":["post-3256","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity","category-embarrassing-myself","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\/3256","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=3256"}],"version-history":[{"count":4,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3256\/revisions"}],"predecessor-version":[{"id":4086,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3256\/revisions\/4086"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}