{"id":49,"date":"2016-09-28T09:00:30","date_gmt":"2016-09-28T16:00:30","guid":{"rendered":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/?p=49"},"modified":"2024-10-10T11:40:11","modified_gmt":"2024-10-10T18:40:11","slug":"verified-compilation-of-space-efficient-reversible-circuits","status":"publish","type":"post","link":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/","title":{"rendered":"Verified compilation of space-efficient reversible circuits"},"content":{"rendered":"<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-50\" src=\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2017\/09\/ReVerC-767x430.png\" alt=\"\" width=\"767\" height=\"430\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><span lang=\"EN\">Generation of reversible circuits from high-level code is an important problem in the compilation flow of quantum algorithms to lower-level hardware. The instantiation of quantum oracles in particular will require mapping classical circuits to a reversible implementation.\u00a0Existing tools compile and optimize reversible circuits for various metrics, such as the overall circuit size or the total amount of space required to implement a given function reversibly. However, little effort has been spent so far on verifying the correctness of the results.<\/span><\/p>\n<p><span lang=\"EN\">In the paper \u201cVerified compilation of space-efficient reversible circuits,\u201d Matt Amy, Martin Roetteler, and Krysta M. Svore present a reversible circuit compiler ReVerC (pronounced \u201cReverse\u201d).\u00a0It has been formally verified and compiles circuits that operate correctly with respect to the input program. The compiler compiles a subset of the higher-level .NET language F# into combinational reversible circuits with as few ancillary bits as possible, and provably cleans temporary values which is a crucial property for maintaining coherence in large-scale quantum algorithms. The proofs of correctness were written in the\u00a0<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/project\/the-f-project\/\" target=\"_blank\" rel=\"noopener\">F*<\/a>\u00a0 proof system.<\/span><\/p>\n<p><span lang=\"EN\">The ReVerC software is available from\u00a0<a href=\"https:\/\/github.com\/msr-quarc\/ReVerC\" target=\"_blank\" rel=\"noopener\">GitHub<\/a>. Read the\u00a0<a href=\"http:\/\/arxiv.org\/abs\/1603.01635\" target=\"_blank\" rel=\"noopener\">arXiv preprint<\/a>.\u00a0\u00a0<\/span><span lang=\"EN\">\u00a0<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; Generation of reversible circuits from high-level code is an important problem in the compilation flow of quantum algorithms to lower-level hardware. The instantiation of quantum oracles in particular will require mapping classical circuits to a reversible implementation.<\/p>\n","protected":false},"author":17,"featured_media":13594,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"msxcm_post_with_no_image":false,"ep_exclude_from_search":false,"_classifai_error":"","_classifai_text_to_speech_error":"","footnotes":""},"post_tag":[9],"product":[],"content-type":[1320],"coauthors":[11],"class_list":["post-49","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","tag-quantum-computing","content-type-news"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.2 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Verified compilation of space-efficient reversible circuits - Microsoft Azure Quantum Blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Verified compilation of space-efficient reversible circuits - Microsoft Azure Quantum Blog\" \/>\n<meta property=\"og:description\" content=\"&nbsp; Generation of reversible circuits from high-level code is an important problem in the compilation flow of quantum algorithms to lower-level hardware. The instantiation of quantum oracles in particular will require mapping classical circuits to a reversible implementation.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/\" \/>\n<meta property=\"og:site_name\" content=\"Microsoft Azure Quantum Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/MicrosoftQuantum\/\" \/>\n<meta property=\"article:published_time\" content=\"2016-09-28T16:00:30+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-10-10T18:40:11+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1170\" \/>\n\t<meta property=\"og:image:height\" content=\"640\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@MSFTQuantum\" \/>\n<meta name=\"twitter:site\" content=\"@MSFTQuantum\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Microsoft Azure Quantum Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 min read\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/\"},\"author\":[{\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/author\/microsoft-quantum-team\/\",\"@type\":\"Person\",\"@name\":\"Microsoft Azure Quantum Team\"}],\"headline\":\"Verified compilation of space-efficient reversible circuits\",\"datePublished\":\"2016-09-28T16:00:30+00:00\",\"dateModified\":\"2024-10-10T18:40:11+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/\"},\"wordCount\":191,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/#organization\"},\"image\":{\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.webp\",\"keywords\":[\"quantum computing\"],\"articleSection\":[\"Quantum Computing\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/\",\"url\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/\",\"name\":\"Verified compilation of space-efficient reversible circuits - Microsoft Azure Quantum Blog\",\"isPartOf\":{\"@id\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.webp\",\"datePublished\":\"2016-09-28T16:00:30+00:00\",\"dateModified\":\"2024-10-10T18:40:11+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#primaryimage\",\"url\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.webp\",\"contentUrl\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.webp\",\"width\":1170,\"height\":640},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Verified compilation of space-efficient reversible circuits\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/#website\",\"url\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/\",\"name\":\"Microsoft Azure Quantum Blog\",\"description\":\"Worldwide consortium for the advancement of topological quantum computation\",\"publisher\":{\"@id\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/#organization\",\"name\":\"Microsoft Azure Quantum Blog\",\"url\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2019\/08\/Microsoft-Logo.png\",\"contentUrl\":\"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2019\/08\/Microsoft-Logo.png\",\"width\":259,\"height\":194,\"caption\":\"Microsoft Azure Quantum Blog\"},\"image\":{\"@id\":\"https:\/\/cloudblogs.microsoft.com\/quantum\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/MicrosoftQuantum\/\",\"https:\/\/x.com\/MSFTQuantum\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Verified compilation of space-efficient reversible circuits - Microsoft Azure Quantum Blog","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/","og_locale":"en_US","og_type":"article","og_title":"Verified compilation of space-efficient reversible circuits - Microsoft Azure Quantum Blog","og_description":"&nbsp; Generation of reversible circuits from high-level code is an important problem in the compilation flow of quantum algorithms to lower-level hardware. The instantiation of quantum oracles in particular will require mapping classical circuits to a reversible implementation.","og_url":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/","og_site_name":"Microsoft Azure Quantum Blog","article_publisher":"https:\/\/www.facebook.com\/MicrosoftQuantum\/","article_published_time":"2016-09-28T16:00:30+00:00","article_modified_time":"2024-10-10T18:40:11+00:00","og_image":[{"width":1170,"height":640,"url":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.png","type":"image\/png"}],"twitter_card":"summary_large_image","twitter_creator":"@MSFTQuantum","twitter_site":"@MSFTQuantum","twitter_misc":{"Written by":"Microsoft Azure Quantum Team","Est. reading time":"1 min read"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#article","isPartOf":{"@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/"},"author":[{"@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/author\/microsoft-quantum-team\/","@type":"Person","@name":"Microsoft Azure Quantum Team"}],"headline":"Verified compilation of space-efficient reversible circuits","datePublished":"2016-09-28T16:00:30+00:00","dateModified":"2024-10-10T18:40:11+00:00","mainEntityOfPage":{"@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/"},"wordCount":191,"commentCount":0,"publisher":{"@id":"https:\/\/cloudblogs.microsoft.com\/quantum\/#organization"},"image":{"@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#primaryimage"},"thumbnailUrl":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.webp","keywords":["quantum computing"],"articleSection":["Quantum Computing"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/","url":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/","name":"Verified compilation of space-efficient reversible circuits - Microsoft Azure Quantum Blog","isPartOf":{"@id":"https:\/\/cloudblogs.microsoft.com\/quantum\/#website"},"primaryImageOfPage":{"@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#primaryimage"},"image":{"@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#primaryimage"},"thumbnailUrl":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.webp","datePublished":"2016-09-28T16:00:30+00:00","dateModified":"2024-10-10T18:40:11+00:00","breadcrumb":{"@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#primaryimage","url":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.webp","contentUrl":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2024\/06\/CLO22_HumanBuiltAbstracts_014.webp","width":1170,"height":640},{"@type":"BreadcrumbList","@id":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2016\/09\/28\/verified-compilation-of-space-efficient-reversible-circuits\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/cloudblogs.microsoft.com\/quantum\/"},{"@type":"ListItem","position":2,"name":"Verified compilation of space-efficient reversible circuits"}]},{"@type":"WebSite","@id":"https:\/\/cloudblogs.microsoft.com\/quantum\/#website","url":"https:\/\/cloudblogs.microsoft.com\/quantum\/","name":"Microsoft Azure Quantum Blog","description":"Worldwide consortium for the advancement of topological quantum computation","publisher":{"@id":"https:\/\/cloudblogs.microsoft.com\/quantum\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/cloudblogs.microsoft.com\/quantum\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/cloudblogs.microsoft.com\/quantum\/#organization","name":"Microsoft Azure Quantum Blog","url":"https:\/\/cloudblogs.microsoft.com\/quantum\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/cloudblogs.microsoft.com\/quantum\/#\/schema\/logo\/image\/","url":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2019\/08\/Microsoft-Logo.png","contentUrl":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-content\/uploads\/2019\/08\/Microsoft-Logo.png","width":259,"height":194,"caption":"Microsoft Azure Quantum Blog"},"image":{"@id":"https:\/\/cloudblogs.microsoft.com\/quantum\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/MicrosoftQuantum\/","https:\/\/x.com\/MSFTQuantum"]}]}},"msxcm_display_generated_audio":false,"msxcm_animated_featured_image":null,"distributor_meta":false,"distributor_terms":false,"distributor_media":false,"distributor_original_site_name":"Microsoft Azure Quantum Blog","distributor_original_site_url":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum","push-errors":false,"_links":{"self":[{"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/posts\/49","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/users\/17"}],"replies":[{"embeddable":true,"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/comments?post=49"}],"version-history":[{"count":0,"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/posts\/49\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/media\/13594"}],"wp:attachment":[{"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/media?parent=49"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/post_tag?post=49"},{"taxonomy":"product","embeddable":true,"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/product?post=49"},{"taxonomy":"content-type","embeddable":true,"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/content-type?post=49"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/wp-json\/wp\/v2\/coauthors?post=49"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}