{"id":204,"date":"2005-05-07T09:30:25","date_gmt":"2005-05-06T23:30:25","guid":{"rendered":"http:\/\/michaelnielsen.org\/?p=204"},"modified":"2005-05-07T09:30:25","modified_gmt":"2005-05-06T23:30:25","slug":"the-solovay-kitaev-algorithm","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/blog\/the-solovay-kitaev-algorithm\/","title":{"rendered":"The Solovay-Kitaev algorithm"},"content":{"rendered":"<p>New paper: <a href=\"http:\/\/www.qinfo.org\/people\/nielsen\/blog\/archive\/notes\/arxiv_0505030_solovay_kitaev.pdf\">\u00e2\u20ac\u0153The Solovay-Kitaev algorithm\u00e2\u20ac\u009d<\/a>, jointly with Chris Dawson, submitted as a tutorial \/ review article to the journal \u00e2\u20ac\u0153Quantum Information and Computation\u00e2\u20ac\u009d.    I expect the paper to appear at the preprint arxiv this coming Monday, as I write.<\/p>\n<p>The Solovay-Kitaev theorem is an important result in quantum computing.  In a classical computer, it\u00e2\u20ac\u2122s well-known that the same computation can be built up out of many different basic gate sets.  For example, you can build up a circuit to add two numbers either using OR and NOT gates, or out of NAND gates alone.  Furthermore, you can use OR and NOT gates to simulate NAND gates (or vice versa), so, roughly speaking, these two different circuits can have the same size, up to some constant of proportionality.<\/p>\n<p>In the case of quantum computers, things are more complicated.  The set of possible quantum gates forms a <em>continuum<\/em>, and it\u00e2\u20ac\u2122s not necessarily possible to use one gate set to simulate another <em>exactly<\/em>.  Instead, some approximation may be necessary.<\/p>\n<p>The Solovay-Kitaev theorem guarantees that different universal gate sets can simulate one another exceedingly quickly, to a very good approximation.  From a practical point of view, this is important in compiling quantum algorithms (like Shor\u00e2\u20ac\u2122s) into a form that can be implemented fault-tolerantly.  From a more mathematical point of view, the Solovay-Kitaev theorem is a remarkable general statement about how quickly the group SU(d) is \u00e2\u20ac\u0153filled in\u00e2\u20ac\u009d by a universal set of gates.<\/p>\n<p>This paper aims to provide a simple exposition of the Solovay-Kitaev theorem, which we hope is accessible to people who\u00e2\u20ac\u2122ve just started working on quantum computing.  We explain the proof in the form of an algorithm (just nine simple lines of pseudocode!) which, given a goal unitary operation U, builds up a good approximation to U using some prespecified set of universal gates.  Chris has also prepared an <a href=\"http:\/\/www.physics.uq.edu.au\/people\/dawson\/sk\/index.html\">online implementation<\/a> of the algorithm.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>New paper: \u00e2\u20ac\u0153The Solovay-Kitaev algorithm\u00e2\u20ac\u009d, jointly with Chris Dawson, submitted as a tutorial \/ review article to the journal \u00e2\u20ac\u0153Quantum Information and Computation\u00e2\u20ac\u009d. I expect the paper to appear at the preprint arxiv this coming Monday, as I write. The Solovay-Kitaev theorem is an important result in quantum computing. In a classical computer, it\u00e2\u20ac\u2122s well-known&hellip; <a class=\"more-link\" href=\"https:\/\/michaelnielsen.org\/blog\/the-solovay-kitaev-algorithm\/\">Continue reading <span class=\"screen-reader-text\">The Solovay-Kitaev algorithm<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10,3,11],"tags":[],"class_list":["post-204","post","type-post","status-publish","format-standard","hentry","category-creative","category-3","category-science","entry"],"_links":{"self":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/204","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/comments?post=204"}],"version-history":[{"count":0,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/204\/revisions"}],"wp:attachment":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/media?parent=204"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/categories?post=204"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/tags?post=204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}