{"id":168241,"date":"2012-12-01T00:00:00","date_gmt":"2012-12-01T00:00:00","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/msr-research-item\/asymptotically-optimal-approximation-of-single-qubit-unitaries-by-clifford-and-t-circuits-using-a-constant-number-of-ancillary-qubits\/"},"modified":"2018-10-16T21:13:28","modified_gmt":"2018-10-17T04:13:28","slug":"asymptotically-optimal-approximation-of-single-qubit-unitaries-by-clifford-and-t-circuits-using-a-constant-number-of-ancillary-qubits","status":"publish","type":"msr-research-item","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/asymptotically-optimal-approximation-of-single-qubit-unitaries-by-clifford-and-t-circuits-using-a-constant-number-of-ancillary-qubits\/","title":{"rendered":"Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits"},"content":{"rendered":"<div class=\"asset-content\">\n<p>We present an algorithm for building a circuit that approximates single qubit unitaries with precision \u03b5 using O(log(1\/\u03b5)) Clifford and T gates and employing up to two ancillary qubits. The algorithm for computing our approximating circuit requires an average of O(log^2(1\/\u03b5)log log(1\/\u03b5)) operations. We prove that the number of gates in our circuit saturates the lower bound on the number of gates required in the scenario when a constant number of ancillae are supplied, and as such, our circuits are asymptotically optimal. This results in significant improvement over the current state of the art for finding an approximation of a unitary, including the Solovay-Kitaev algorithm that requires O(log^3+\u03b4(1\/\u03b5)) gates and does not use ancillae and the phase kickback approach that requires O(log^2(1\/\u03b5)log log(1\/\u03b5)) gates, but uses O(log^2(1\/\u03b5)) ancillae.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>We present an algorithm for building a circuit that approximates single qubit unitaries with precision \u03b5 using O(log(1\/\u03b5)) Clifford and T gates and employing up to two ancillary qubits. The algorithm for computing our approximating circuit requires an average of O(log^2(1\/\u03b5)log log(1\/\u03b5)) operations. We prove that the number of gates in our circuit saturates the [&hellip;]<\/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":"","msr-author-ordering":null,"msr_publishername":"American Physical Society","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"Physical Review Letters","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"Physical Review Letters","msr_number":"19","msr_organization":"","msr_pages_string":"1\u20135","msr_page_range_start":"1","msr_page_range_end":"5","msr_series":"","msr_volume":"110","msr_copyright":"","msr_conference_name":"","msr_doi":"10.1103\/PhysRevLett.110.190502","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"Dmitri Maslov, Michele Mosca","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2012-12-01","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"http:\/\/journals.aps.org\/prl\/abstract\/10.1103\/PhysRevLett.110.190502","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":2012,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561],"msr-publication-type":[193715],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-168241","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-locale-en_us"],"msr_publishername":"American Physical Society","msr_edition":"Physical Review Letters","msr_affiliation":"","msr_published_date":"2012-12-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"1\u20135","msr_chapter":"","msr_isbn":"","msr_journal":"Physical Review Letters","msr_volume":"110","msr_number":"19","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","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":"","msr_publicationurl":"http:\/\/journals.aps.org\/prl\/abstract\/10.1103\/PhysRevLett.110.190502","msr_doi":"10.1103\/PhysRevLett.110.190502","msr_publication_uploader":[{"type":"url","title":"http:\/\/journals.aps.org\/prl\/abstract\/10.1103\/PhysRevLett.110.190502","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"10.1103\/PhysRevLett.110.190502","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":0,"url":"http:\/\/journals.aps.org\/prl\/abstract\/10.1103\/PhysRevLett.110.190502"}],"msr-author-ordering":[{"type":"user_nicename","value":"vadym","user_id":34468,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=vadym"},{"type":"text","value":"Dmitri Maslov","user_id":0,"rest_url":false},{"type":"text","value":"Michele Mosca","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"article","related_content":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168241","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168241\/revisions"}],"predecessor-version":[{"id":413561,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168241\/revisions\/413561"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=168241"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=168241"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=168241"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=168241"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=168241"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=168241"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=168241"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=168241"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=168241"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=168241"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=168241"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=168241"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=168241"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}