{"id":166311,"date":"2018-11-06T17:21:36","date_gmt":"2018-11-07T01:21:36","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/msr-research-item\/a-quantum-circuit-to-find-discrete-logarithms-on-ordinary-binary-elliptic-curves-in-depth-olog2-n\/"},"modified":"2018-11-06T17:21:36","modified_gmt":"2018-11-07T01:21:36","slug":"a-quantum-circuit-to-find-discrete-logarithms-on-ordinary-binary-elliptic-curves-in-depth-olog2-n","status":"publish","type":"msr-research-item","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/a-quantum-circuit-to-find-discrete-logarithms-on-ordinary-binary-elliptic-curves-in-depth-olog2-n\/","title":{"rendered":"A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)"},"content":{"rendered":"<div class=\"asset-content\">\n<p>Improving over an earlier construction by Kaye and Zalka, Maslov et al. describe an implementation of Shor&#8217;s algorithm which can solve the discrete logarithm problem on binary elliptic curves in quadratic depth O(n<sup>2<\/sup>). In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth O(log<sup>2<\/sup> n). As technical tools we introduce quantum circuits for GF(2<sup>n<\/sup>) multiplication in depth O(log n) and for GF(2<sup>n<\/sup>) inversion in depth O(log<sup>2<\/sup> n).<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Improving over an earlier construction by Kaye and Zalka, Maslov et al. describe an implementation of Shor&#8217;s algorithm which can solve the discrete logarithm problem on binary elliptic curves in quadratic depth O(n2). In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth O(log2 n). [&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":"Rinton Press","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"9-10","msr_journal":"Quant. Inform. & Comp.","msr_number":"","msr_organization":"","msr_pages_string":"888-900","msr_page_range_start":"888","msr_page_range_end":"900","msr_series":"","msr_volume":"14","msr_copyright":"","msr_conference_name":"","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"M. R\u00f6tteler, R. Steinwandt","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":"2014-07-01","msr_highlight_text":"","msr_notes":"Accepted for publication. See also arXiv preprint arXiv:1306.1161","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":2014,"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,243138],"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-166311","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-research-area-quantum","msr-locale-en_us"],"msr_publishername":"Rinton Press","msr_edition":"","msr_affiliation":"","msr_published_date":"2014-07-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"888-900","msr_chapter":"","msr_isbn":"","msr_journal":"Quant. Inform. & Comp.","msr_volume":"14","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"9-10","msr_organization":"","msr_how_published":"","msr_notes":"Accepted for publication. See also arXiv preprint arXiv:1306.1161","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":"204801","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"Roetteler%20Steinwandt%20Quantum%20Circuits%20for%20ECC%20Dlog%201306.1161.pdf","viewUrl":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2016\/02\/Roetteler20Steinwandt20Quantum20Circuits20for20ECC20Dlog201306.1161.pdf","id":204801,"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":[],"msr-author-ordering":[{"type":"text","value":"M. R\u00f6tteler","user_id":0,"rest_url":false},{"type":"text","value":"R. Steinwandt","user_id":0,"rest_url":false},{"type":"user_nicename","value":"martinro","user_id":32823,"rest_url":"https:\/\/cm-edgetun.pages.dev\/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":[],"msr-tool":[],"msr_publication_type":"article","related_content":{"projects":[{"ID":170888,"post_title":"Language-Integrated Quantum Operations: LIQUi|&gt;","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:\/\/cm-edgetun.pages.dev\/en-us\/research\/project\/language-integrated-quantum-operations-liqui\/","post_excerpt":"LIQUi|&gt; is a software architecture and toolsuite for quantum computing. It includes a programming language, optimization and scheduling algorithms, and quantum simulators. LIQUi|&gt; 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|&gt; is being developed by the Quantum Architectures and Computation Group (QuArC)\u00a0at Microsoft Research. About LIQUi|&gt; To aid in the development and understanding of quantum protocols, quantum&hellip;","_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170888"}]}}]},"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/166311","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\/166311\/revisions"}],"predecessor-version":[{"id":433794,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/166311\/revisions\/433794"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=166311"}],"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=166311"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=166311"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=166311"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=166311"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=166311"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=166311"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=166311"},{"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=166311"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=166311"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=166311"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=166311"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=166311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}