Recently it has been shown that Repeat-Until-Success (RUS) circuits can approximate a given single-qubit unitary with an expected number of T gates of about 1\/3 of what is required by optimal, deterministic, ancilla-free decompositions over the Cli\ufb00ord+T gate set. In this work, we introduce a more general and conceptually simpler circuit decomposition method that allows for synthesis into protocols that probabilistically implement quantum circuits over several universal gate sets including, but not restricted to, the Cli\ufb00ord+T gate set. The protocol, which we call Probabilistic Quantum Circuits with Fallback (PQF), implements a walk on a discrete Markov chain in which the target unitary is an absorbing state and in which transitions are induced by multi-qubit unitaries followed by measurements. In contrast to RUS protocols, the presented PQF protocols terminate after a \ufb01nite number of steps. Speci\ufb01cally, we apply our method to the Cli\ufb00ord+T, Cli\ufb00ord+V , and Cli\ufb00ord+\u03c0\/12 gate sets to achieve decompositions with expected gate counts of logb(1\/\u03b5)+O(log(log(1\/\u03b5))), where b is a quantity related to the expansion property of the underlying universal gate set.<\/p>\n","protected":false},"excerpt":{"rendered":"
Recently it has been shown that Repeat-Until-Success (RUS) circuits can approximate a given single-qubit unitary with an expected number of T gates of about 1\/3 of what is required by optimal, deterministic, ancilla-free decompositions over the Cli\ufb00ord+T gate set. In this work, we introduce a more general and conceptually simpler circuit decomposition method that allows […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[243138],"msr-publication-type":[193715],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-168514","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-quantum","msr-locale-en_us"],"msr_publishername":"APS","msr_edition":"Physical Review A","msr_affiliation":"","msr_published_date":"2015-05-18","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"052317","msr_chapter":"","msr_isbn":"","msr_journal":"Physical Review A","msr_volume":"91","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"See also arXiv preprint arXiv:1409.3552","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"426825","msr_publicationurl":"https:\/\/doi.org\/10.1103\/PhysRevA.91.052317","msr_doi":"https:\/\/doi.org\/10.1103\/PhysRevA.91.052317","msr_publication_uploader":[{"type":"file","title":"1409.3552","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2015\/05\/1409.3552.pdf","id":426825,"label_id":0},{"type":"url","title":"https:\/\/doi.org\/10.1103\/PhysRevA.91.052317","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"https:\/\/doi.org\/10.1103\/PhysRevA.91.052317","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"https:\/\/doi.org\/10.1103\/PhysRevA.91.052317"}],"msr-author-ordering":[{"type":"text","value":"A. Bocharov","user_id":0,"rest_url":false},{"type":"text","value":"M. R\u00f6tteler","user_id":0,"rest_url":false},{"type":"text","value":"K. M. Svore","user_id":0,"rest_url":false},{"type":"user_nicename","value":"alexeib","user_id":30935,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=alexeib"},{"type":"user_nicename","value":"ksvore","user_id":32588,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=ksvore"},{"type":"user_nicename","value":"martinro","user_id":32823,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=martinro"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[170888],"publication":[],"video":[],"download":[],"msr_publication_type":"article","related_content":{"projects":[{"ID":170888,"post_title":"Language-Integrated Quantum Operations: LIQUi|>","post_name":"language-integrated-quantum-operations-liqui","post_type":"msr-project","post_date":"2011-12-19 10:19:35","post_modified":"2018-11-02 11:06:22","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/language-integrated-quantum-operations-liqui\/","post_excerpt":"LIQUi|> is a software architecture and toolsuite for quantum computing. It includes a programming language, optimization and scheduling algorithms, and quantum simulators. LIQUi|> can be used to translate a quantum algorithm written in the form of a high-level program into the low-level machine instructions for a quantum device. LIQUi|> is being developed by the Quantum Architectures and Computation Group (QuArC)\u00a0at Microsoft Research. About LIQUi|> To aid in the development and understanding of quantum protocols, quantum…","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170888"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168514"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168514\/revisions"}],"predecessor-version":[{"id":426807,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168514\/revisions\/426807"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=168514"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=168514"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=168514"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=168514"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=168514"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=168514"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=168514"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=168514"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=168514"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=168514"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=168514"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=168514"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=168514"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=168514"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=168514"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=168514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}