{"id":2309,"date":"2018-06-25T11:03:01","date_gmt":"2018-06-25T10:03:01","guid":{"rendered":"https:\/\/www.quantum-bits.org\/?p=2309"},"modified":"2022-08-12T17:15:39","modified_gmt":"2022-08-12T16:15:39","slug":"an-update-on-quantum-computing-and-complexity-classes","status":"publish","type":"post","link":"https:\/\/www.quantum-bits.org\/?p=2309","title":{"rendered":"An update on quantum computing and complexity classes"},"content":{"rendered":"<p>In a series of posts, we introduced various <strong>quantum computing<\/strong> concepts:<\/p>\n<ul>\n<li><a href=\"https:\/\/www.quantum-bits.org\/?p=55\" target=\"_blank\" rel=\"noopener\">How information and quantum mechanics are related ?<\/a><\/li>\n<li><a href=\"https:\/\/www.quantum-bits.org\/?p=1611\" target=\"_blank\" rel=\"noopener\">What is quantum computing ?<\/a><\/li>\n<li><a href=\"https:\/\/www.quantum-bits.org\/?p=1785\" target=\"_blank\" rel=\"noopener\">What are Bell states ?<\/a><\/li>\n<li><a href=\"https:\/\/www.quantum-bits.org\/?p=1857\" target=\"_blank\" rel=\"noopener\">What is quantum teleportation ?<\/a><\/li>\n<li><a href=\"https:\/\/www.quantum-bits.org\/?p=1930\" target=\"_blank\" rel=\"noopener\">What is quantum error correction ?<\/a><\/li>\n<li><a href=\"https:\/\/www.quantum-bits.org\/?p=2226\" target=\"_blank\" rel=\"noopener\">What are topological quantum computer ?<\/a><\/li>\n<\/ul>\n<p>In addition to these concepts, we devoted two posts to the very crucial topic that is <strong>complexity<\/strong>:<\/p>\n<ul>\n<li><a href=\"https:\/\/www.quantum-bits.org\/?p=1988\" target=\"_blank\" rel=\"noopener\">Complexity and quantum computing<\/a><\/li>\n<li><a href=\"https:\/\/www.quantum-bits.org\/?p=2059\" target=\"_blank\" rel=\"noopener\">On quantum computing and cryptography<\/a><\/li>\n<\/ul>\n<p>In a <a href=\"https:\/\/eccc.weizmann.ac.il\/report\/2018\/107\/\" target=\"_blank\" rel=\"noopener\">recent paper<\/a>, computer scientists <a href=\"https:\/\/engineering.princeton.edu\/faculty\/ran-raz\" target=\"_blank\" rel=\"noopener\">Ran Raz<\/a> and <a href=\"http:\/\/www.avishaytal.org\/\" target=\"_blank\" rel=\"noopener\">Avishay Tal<\/a> <strong>rocked the world of quantum complexity<\/strong> so much it is now time for an update on that subject !<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-1612\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/quantum-physics-formulas-over-blackboard.jpg\" alt=\"\" width=\"850\" height=\"332\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/quantum-physics-formulas-over-blackboard.jpg 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/quantum-physics-formulas-over-blackboard-300x117.jpg 300w\" sizes=\"(max-width: 850px) 100vw, 850px\" \/><\/p>\n<p><strong>Back to complexity classes<\/strong><\/p>\n<p>One of the purposes of theoretical computer science is to sort problems into complexity classes. Quoting <a href=\"https:\/\/www.quantamagazine.org\" target=\"_blank\" rel=\"noopener\">Quanta Magazine<\/a>, a complexity class &#8220;<em>contains all problems that can be solved within a given resource budget, where the resource is something like time or memory.<\/em>&#8221;<\/p>\n<p>In a previous post, we have introduced the two most famous complexity classes:<\/p>\n<ul>\n<li><b><a title=\"P (complexity)\" href=\"https:\/\/en.wikipedia.org\/wiki\/P_(complexity)\" target=\"_blank\" rel=\"noopener\">P<\/a><\/b>: The&nbsp;complexity class&nbsp;of&nbsp;<a title=\"Decision problem\" href=\"https:\/\/en.wikipedia.org\/wiki\/Decision_problem\" target=\"_blank\" rel=\"noopener\">decision problems<\/a>&nbsp;that can be solved on a&nbsp;<a class=\"mw-redirect\" title=\"Deterministic Turing machine\" href=\"https:\/\/en.wikipedia.org\/wiki\/Deterministic_Turing_machine\" target=\"_blank\" rel=\"noopener\">deterministic Turing machine<\/a>&nbsp;in polynomial time. <strong>P<\/strong> is all the problems that a classical computer can solve quickly (for example: &#8220;Is this number prime?&#8221; belongs to <strong>P<\/strong>).&nbsp;<\/li>\n<li><b><a title=\"NP (complexity)\" href=\"https:\/\/en.wikipedia.org\/wiki\/NP_(complexity)\" target=\"_blank\" rel=\"noopener\">NP<\/a><\/b>: The complexity class of decision problems that can be solved on a&nbsp;<a title=\"Non-deterministic Turing machine\" href=\"https:\/\/en.wikipedia.org\/wiki\/Non-deterministic_Turing_machine\" target=\"_blank\" rel=\"noopener\">non-deterministic Turing machine<\/a>&nbsp;in polynomial time. <strong>NP<\/strong> is all the problems that classical computers can\u2019t necessarily solve quickly, but for which they can quickly verify an answer if presented with one. (for example: \u201cWhat are its prime factors?\u201d belongs to <strong>NP<\/strong>).<\/li>\n<\/ul>\n<p>Also, within the NP class, we introduced <a href=\"https:\/\/en.wikipedia.org\/wiki\/NP-completeness\" target=\"_blank\" rel=\"noopener\"><strong>NP-complete<\/strong>&nbsp;<\/a>and <a class=\"mw-redirect\" title=\"NP-hard\" href=\"https:\/\/en.wikipedia.org\/wiki\/NP-hard\" target=\"_blank\" rel=\"noopener\">NP-hard<\/a> problem (a problem is said to be <strong>NP-hard<\/strong> if an&nbsp;algorithm&nbsp;for solving it can be translated into one for solving any&nbsp;NP-problem), as well as&nbsp; <a href=\"https:\/\/en.wikipedia.org\/wiki\/NP-intermediate\" target=\"_blank\" rel=\"noopener\">NP-intermediate<\/a> (<strong>NPI<\/strong>) class (problems in the&nbsp;complexity class&nbsp;<a title=\"NP (complexity)\" href=\"https:\/\/en.wikipedia.org\/wiki\/NP_(complexity)\" target=\"_blank\" rel=\"noopener\">NP<\/a>&nbsp;but that are neither <a title=\"P (complexity)\" href=\"https:\/\/en.wikipedia.org\/wiki\/P_(complexity)\" target=\"_blank\" rel=\"noopener\">P<\/a>&nbsp;nor&nbsp;<a class=\"mw-redirect\" title=\"NP-complete\" href=\"https:\/\/en.wikipedia.org\/wiki\/NP-complete\" target=\"_blank\" rel=\"noopener\">NP-complete<\/a>).<\/p>\n<p><strong>co-NP<\/strong> is the complexity class which contains the complements of problems found in NP. In other terms,&nbsp; class of problems for which there is a polynomial-time algorithm that can verify counterexamples.<\/p>\n<p>Determining whether it is possible to solve these problems quickly, called the <a title=\"P versus NP problem\" href=\"https:\/\/en.wikipedia.org\/wiki\/P_versus_NP_problem\" target=\"_blank\" rel=\"noopener\">P versus NP problem<\/a>, is one of the principal <a class=\"mw-redirect\" title=\"List of open problems in computer science\" href=\"https:\/\/en.wikipedia.org\/wiki\/List_of_open_problems_in_computer_science\" target=\"_blank\" rel=\"noopener\">unsolved problems in computer science<\/a> today:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2028\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/euler-diagram.png\" alt=\"\" width=\"450\" height=\"318\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/euler-diagram.png 1292w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/euler-diagram-300x212.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/euler-diagram-768x543.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/euler-diagram-1024x724.png 1024w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/p>\n<p><strong>Quantum complexity<\/strong><\/p>\n<p>In 1993 computer scientists Ethan Bernstein and Umesh Vazirani defined a new complexity class called <strong>BQP<\/strong> (for Bounded-error Quantum Polynomial time): the complexity class of decision problems that can be solved with 2-sided error on a&nbsp;<a title=\"Quantum Turing machine\" href=\"https:\/\/en.wikipedia.org\/wiki\/Quantum_Turing_machine\" target=\"_blank\" rel=\"noopener\">quantum Turing machine<\/a>&nbsp;in polynomial time.<\/p>\n<p>They defined this particular class to contain all the decision problems that quantum computers can solve efficiently. They also proved that quantum computers can solve all the problems that classical computers can solve : <strong>BQP<\/strong> contains all the problems that are in <strong>P<\/strong>.<\/p>\n<p>A central task of quantum computing theory is to understand how <strong>BQP<\/strong> fits in with classical complexity classes. That is why the boundaries of <strong>BQP<\/strong>, sketched in the following diagram, are uncertain:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2033\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits.png\" alt=\"\" width=\"450\" height=\"340\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits.png 1366w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits-300x226.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits-768x580.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits-1024x773.png 1024w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/04\/where-quantum-fits-285x214.png 285w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/p>\n<p>So far, we know that:<\/p>\n<ul>\n<li><strong>P<\/strong> sits in <strong>BQP <\/strong><\/li>\n<li><strong>BQP<\/strong> sits in <strong>PSPACE<\/strong><\/li>\n<li>Boundaries of <strong>BQP<\/strong> (relative to <strong>NP<\/strong>) are uncertain<\/li>\n<\/ul>\n<div><strong>Polynomial hierarchy<\/strong><\/div>\n<div>&nbsp;<\/div>\n<div>In computational complexity theory, the <b>polynomial hierarchy<\/b> is a hierarchy of complexity classes that generalize the classes <strong>P<\/strong>, <strong>NP <\/strong>and <strong>co-NP<\/strong> to oracle machines. An <b>oracle machine<\/b> is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box (called an <b>oracle)<\/b>, which is able to solve certain decision problems in a single operation.<\/div>\n<div>&nbsp;<\/div>\n<div>\n<p>The complexity class <b>PH<\/b> is the union of all complexity classes in the <strong>Polynomial Hierarchy<\/strong>. <strong>PH<\/strong> is the is a generalization of <strong>NP<\/strong> to allow multiple quantifiers such as \u2203 (i.e. there exists), \u2200 (i.e. for all), etc. (see <a href=\"https:\/\/en.wikipedia.org\/wiki\/Second-order_logic\" target=\"_blank\" rel=\"noopener\">second order<\/a> logic for details).<\/p>\n<p>You can think of <strong>PH<\/strong> as the class of all problems classical computers could solve if <strong>P<\/strong> turned out to equal <strong>NP<\/strong>.<\/p>\n<p>In other words, to compare <strong>BQP<\/strong> and <strong>PH<\/strong> is to &#8220;<em>determine whether quantum computers have an advantage over classical computers that would survive even if classical computers could solve many more problems than they can today<\/em><strong>&#8220;<\/strong> [Quanta Magazine].<\/p>\n<p><strong>Using oracle separation to distinguish BQP from PH<\/strong><\/p>\n<p>Up to now, there were <strong>some evidence<\/strong> that <strong>BQP was not contained in PH<\/strong>. This result is <strong>now proven<\/strong> by Ran Raz and Avishay Tal.<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2320\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/raz-tal.png\" alt=\"\" width=\"600\" height=\"212\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/raz-tal.png 1813w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/raz-tal-300x106.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/raz-tal-768x271.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/raz-tal-1024x361.png 1024w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><\/p>\n<\/div>\n<p>The best way to distinguish between two complexity classes is to find a problem that is provably in one and not the other.<\/p>\n<p>If you want a problem that is in <strong>BQP<\/strong> but not in <strong>PH<\/strong>, you have to identify something that \u201c<em>by definition a classical computer could not even efficiently verify the answer, let alone find it<\/em>,\u201d&nbsp; (Scott Aaronson).<\/p>\n<p>The first step was the introduction of the concept of &#8220;forrelation&#8221; (also known as <em>Fourier checking<\/em>) by Scott Aaronson and Andris Ambainis. See for example:<\/p>\n<ul>\n<li><a href=\"https:\/\/www.scottaaronson.com\/papers\/bqpph.pdf\" target=\"_blank\" rel=\"noopener\">https:\/\/www.scottaaronson.com\/papers\/bqpph.pdf<\/a> or<\/li>\n<li><a href=\"https:\/\/www.scottaaronson.com\/papers\/for.pdf\" target=\"_blank\" rel=\"noopener\">https:\/\/www.scottaaronson.com\/papers\/for.pdf<\/a>.<\/li>\n<\/ul>\n<p>The problem to be solved is the following:<\/p>\n<ul>\n<li>Imagine two random number generators (<em>f<\/em> and <em>g<\/em>), each producing a sequence of bits<\/li>\n<li>Forrelation estimates the correlation between <em>f<\/em> and the Fourier transform of <em>g<\/em> (are the two sequences completely independent from each other, or are they related in a hidden way)<\/li>\n<\/ul>\n<p>It was then proved in 2010 that forrelation belongs to <strong>BQP<\/strong>. What is left was the hardest step: <strong>proving that forrelation is not in PH<\/strong>.<\/p>\n<p>To distinguish between complexity classes like <strong>BQP<\/strong> and <strong>PH<\/strong>, one would like be to measure the computational time required to solve a problem in each. Unfortunately, nobody has a clear understanding of how to measure actual computation time.<\/p>\n<p>When the thing they\u2019d really like to prove is beyond their reach, computer scientists often resort to <strong>oracles<\/strong>. They measure something else that they hope will provide insight into the computation times they can\u2019t measure: they work out the number of times a computer needs to consult an oracl\u201d in order to come back with an answer.<\/p>\n<p>We can get an understanding of complexity by allowing both machines access to the same oracle and seeing what we can separate. In our case, the problem is to figure out whether two random number generators are secretly related:<\/p>\n<ul>\n<li>You can ask the oracle questions such as \u201cWhat\u2019s the sixth number from each generator?\u201d.<\/li>\n<li>Then you compare computational power based on the number of hints each type of computer needs to solve the problem. The computer that needs more hints is slower.<\/li>\n<\/ul>\n<p>The paper published by Ran Raz and Avishay Tal shows that quantum computer need just one hint, while even with unlimited hints, there\u2019s no algorithm in PH that can solve the problem.<\/p>\n<p>\u201c<em>This means there is a very efficient quantum algorithm that solves that problem<\/em>,\u201d said Raz. \u201c<em>But if you only consider classical algorithms, even if you go to very high classes of classical algorithms, they cannot.<\/em>\u201d<\/p>\n<p><strong>Quantum and classical computers exist in a different computational realm<\/strong><\/p>\n<p>This establishes that with an oracle, Fourier checking (forrelation) is <strong>a problem<\/strong> that is in <strong>BQP but not in PH<\/strong>. This is big, so let&#8217;s repeat it : for the first time, <strong>a problem is found to be in BQP but not in PH<\/strong>:<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-2318\" src=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/ph-bqp.png\" alt=\"\" width=\"700\" height=\"308\" srcset=\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/ph-bqp.png 2426w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/ph-bqp-300x132.png 300w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/ph-bqp-768x337.png 768w, https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/06\/ph-bqp-1024x450.png 1024w\" sizes=\"(max-width: 700px) 100vw, 700px\" \/><\/p>\n<p>To finish this update, let&#8217;s quote Quanta Magazine: &#8220;<em>The work provides an ironclad assurance that quantum computers exist in a different computational realm than classical computers (at least relative to an oracle). Even in a world where P equals NP [&#8230;] Raz and Tal\u2019s proof demonstrates that there would still be problems only quantum computers could solve.<\/em> <em>Even if P were equal to NP, even making that strong assumption,\u201d said Fortnow, \u201cthat\u2019s not going to be enough to capture quantum computing.<\/em>\u201d<\/p>\n<p>&nbsp;<br \/>\n<span style=\"font-size: 8pt;\">Note: A few paragraphs and illustrations of this post are based on Quanta Magazine.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>In a series of posts, we introduced various quantum computing concepts: How information and quantum mechanics are related ? What is quantum computing ? What are Bell states ? What &#8230;<\/p>\n","protected":false},"author":1,"featured_media":3846,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0},"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/posts\/2309"}],"collection":[{"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2309"}],"version-history":[{"count":0,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/posts\/2309\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=\/wp\/v2\/media\/3846"}],"wp:attachment":[{"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2309"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2309"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.quantum-bits.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2309"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}