{"id":112,"date":"2006-08-15T19:38:00","date_gmt":"2006-08-15T19:38:00","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=112"},"modified":"2006-08-15T19:38:00","modified_gmt":"2006-08-15T19:38:00","slug":"the-ten-most-annoying-questions-in-quantum-computing","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=112","title":{"rendered":"The ten most annoying questions in quantum computing"},"content":{"rendered":"<ol>\n<li>Given an n-qubit pure state, is there always a way to apply Hadamard gates to some subset of the qubits, so as to make all 2<sup>n<\/sup> computational basis states have nonzero amplitudes?<\/li>\n<li>Can we get any upper bound on <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#qmip\">QMIP<\/a> (quantum multi-prover interactive proofs with unlimited prior entanglement)?  It would suffice to show (for example) that the provers never need more than Ackermann(n) ebits of entanglement.<\/li>\n<li>Can any <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#qma2\">QMA(2)<\/a> (<a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#qma\">QMA<\/a> with two unentangled yes-provers) protocol be amplified to exponentially small error probability?  If you think the answer is trivially yes, think about it some more!<\/li>\n<li>If a unitary operation U can be applied in polynomial time, then can some square root of U also be applied in polynomial time?<\/li>\n<li>Suppose Alice and Bob are playing n parallel <a href=\"http:\/\/www.cs.uwaterloo.ca\/%7Ewatrous\/lecture-notes\/519\/20.ps\">CHSH games<\/a>, with no communication or entanglement.  Is the probability that they&#8217;ll win all n games at most p<sup>n<\/sup>, for some p bounded below 0.853?<\/li>\n<li>Forget about an oracle relative to which <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#bqp\">BQP<\/a> is not in <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#ph\">PH<\/a>.   Forget about an oracle relative to which BQP is not in <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#am\">AM<\/a>.  Is there an oracle relative to which BQP is not in <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#szk\">SZK<\/a>?<\/li>\n<li>Given any n-qubit unitary operation U, does there exist an oracle relative to which U can be (approximately) applied in polynomial time?<\/li>\n<li>How many <a href=\"http:\/\/www.imaph.tu-bs.de\/qi\/problems\/13.pdf\">mutually unbiased bases<\/a> are there in non-prime-power dimensions?  (Alright, I don&#8217;t care about this one, but so many people do that I figured I&#8217;d put it in.)<\/li>\n<li>Is there an n-qubit pure state that can be prepared by a circuit of size n<sup>3<\/sup>, and that can&#8217;t be distinguished from the maximally mixed state by any circuit of size n<sup>2<\/sup>?<\/li>\n<li>Fill this space with your own annoying question!  Here are the rules: the question must involve quantum.  It must be annoying.  It must be clearly-stated &#8212; no open-ended pontificating allowed.  It can&#8217;t be an Everest of the field, like graph isomorphism or increasing the fault-tolerance threshold.  Instead it should be a dinky little molehill, that&#8217;s nevertheless caused all would-be climbers to fall flat on their asses.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Given an n-qubit pure state, is there always a way to apply Hadamard gates to some subset of the qubits, so as to make all 2n computational basis states have nonzero amplitudes? Can we get any upper bound on QMIP (quantum multi-prover interactive proofs with unlimited prior entanglement)? It would suffice to show (for example) [&hellip;]<\/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_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":[5,4],"tags":[],"class_list":["post-112","post","type-post","status-publish","format-standard","hentry","category-complexity","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\/112","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=112"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/112\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=112"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=112"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=112"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}