{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T18:57:24Z","timestamp":1772823444782,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,2,24]],"date-time":"2024-02-24T00:00:00Z","timestamp":1708732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Plan France 2030","award":["NISQ2LSQ ANR-22-PETQ-0006 and EPIQ ANR-22-PETQ-007"],"award-info":[{"award-number":["NISQ2LSQ ANR-22-PETQ-0006 and EPIQ ANR-22-PETQ-007"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>\n            The Clifford+\n            <jats:italic>T<\/jats:italic>\n            gate set is commonly used to perform universal quantum computation. In such setup the\n            <jats:italic>T<\/jats:italic>\n            gate is typically much more expensive to implement in a fault-tolerant way than Clifford gates. To improve the feasibility of fault-tolerant quantum computing it is then crucial to minimize the number of\n            <jats:italic>T<\/jats:italic>\n            gates. Many algorithms, yielding effective results, have been designed to address this problem. It has been demonstrated that performing a pre-processing step consisting of reducing the number of Hadamard gates in the circuit can help to exploit the full potential of these algorithms and thereby lead to a substantial\n            <jats:italic>T<\/jats:italic>\n            -count reduction. Moreover, minimizing the number of Hadamard gates also restrains the number of additional qubits and operations resulting from the gadgetization of Hadamard gates, a procedure used by some compilers to further reduce the number of\n            <jats:italic>T<\/jats:italic>\n            gates. In this work we tackle the Hadamard gate reduction problem, and propose an algorithm for synthesizing a sequence of \u03c0 \/4 Pauli rotations with a minimal number of Hadamard gates. Based on this result, we present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last\n            <jats:italic>T<\/jats:italic>\n            gate of the circuit.\n          <\/jats:p>","DOI":"10.1145\/3639062","type":"journal-article","created":{"date-parts":[[2023,12,28]],"date-time":"2023-12-28T21:57:35Z","timestamp":1703800655000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Optimal Hadamard Gate Count for Clifford+\n            <i>T<\/i>\n            Synthesis of Pauli Rotations Sequences"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9330-4999","authenticated-orcid":false,"given":"Vivien","family":"Vandaele","sequence":"first","affiliation":[{"name":"Atos Quantum Lab, Les Clayes-sous-Bois, France and Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, Nancy, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5624-2955","authenticated-orcid":false,"given":"Simon","family":"Martiel","sequence":"additional","affiliation":[{"name":"Atos Quantum Lab, Les Clayes-sous-Bois, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1808-2409","authenticated-orcid":false,"given":"Simon","family":"Perdrix","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, Nancy, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3445-0179","authenticated-orcid":false,"given":"Christophe","family":"Vuillot","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, Nancy, France"}]}],"member":"320","published-online":{"date-parts":[[2024,2,24]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2341953"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/2685179.2685180"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/978-3-319-08494-7_12","volume-title":"Reversible Computation","author":"Abdessaied Nabila","year":"2014","unstructured":"Nabila Abdessaied, Mathias Soeken, and Rolf Drechsler. 2014. Quantum circuit optimization by Hadamard gate reduction. In Reversible Computation, Shigeru Yamashita and Shin-ichi Minato (Eds.). Springer International Publishing, Cham, 149\u2013162. DOI:http:\/\/dx.doi.org\/1007\/978-3-319-08494-7_12"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2906374"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-018-0072-4"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aad604"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.102.022406"},{"key":"e_1_3_2_9_2","article-title":"Optimizing T gates in Clifford+T circuit as  \\(\\pi \/4\\)  rotations around Paulis","author":"Zhang Fang","year":"2019","unstructured":"Fang Zhang and Jianxin Chen. 2019. Optimizing T gates in Clifford+T circuit as \\(\\pi \/4\\) rotations around Paulis. arXiv preprint arXiv:1903.12456 (2019).","journal-title":"arXiv preprint arXiv:1903.12456"},{"key":"e_1_3_2_10_2","article-title":"Techniques to reduce  \\(\\pi \/4\\) -parity-phase circuits, motivated by the ZX calculus","author":"Beaudrap Niel de","year":"2019","unstructured":"Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. 2019. Techniques to reduce \\(\\pi \/4\\) -parity-phase circuits, motivated by the ZX calculus. arXiv preprint arXiv:1911.09039 (2019).","journal-title":"arXiv preprint arXiv:1911.09039"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2020.11"},{"key":"e_1_3_2_12_2","article-title":"AND-gates in ZX-calculus: Spider nest identities and QBC-completeness","author":"Munson Anthony","year":"2019","unstructured":"Anthony Munson, Bob Coecke, and Quanlong Wang. 2019. AND-gates in ZX-calculus: Spider nest identities and QBC-completeness. arXiv preprint arXiv:1910.06818 (2019).","journal-title":"arXiv preprint arXiv:1910.06818"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ac2d3a"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/42\/9\/095302"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.116.250501"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-09-02-181"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-12-20-606"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ac5d20"},{"key":"e_1_3_2_21_2","article-title":"Classical simulation of quantum circuits with partial and graphical stabiliser decompositions","author":"Kissinger Aleks","year":"2022","unstructured":"Aleks Kissinger, John van de Wetering, and Renaud Vilmart. 2022. Classical simulation of quantum circuits with partial and graphical stabiliser decompositions. arXiv preprint arXiv:2202.09202 (2022).","journal-title":"arXiv preprint arXiv:2202.09202"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056662"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2010.0301"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aad8ca"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2825602"},{"key":"e_1_3_2_27_2","article-title":"A graph-state based synthesis framework for Clifford isometries","author":"Brugi\u00e8re Timoth\u00e9e Goubault de","year":"2022","unstructured":"Timoth\u00e9e Goubault de Brugi\u00e8re, Simon Martiel, and Christophe Vuillot. 2022. A graph-state based synthesis framework for Clifford isometries. arXiv preprint arXiv:2212.06928 (2022).","journal-title":"arXiv preprint arXiv:2212.06928"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ac5a0e"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-07-06-497"},{"key":"e_1_3_2_30_2","article-title":"Relating measurement patterns to circuits via pauli flow","author":"Simmons Will","year":"2021","unstructured":"Will Simmons. 2021. Relating measurement patterns to circuits via pauli flow. arXiv preprint arXiv:2109.05654 (2021).","journal-title":"arXiv preprint arXiv:2109.05654"},{"key":"e_1_3_2_31_2","unstructured":"Matthew Amy. ([n. d.]). Feynman. https:\/\/github.com\/meamy\/feynman"},{"key":"e_1_3_2_32_2","unstructured":"Dmitri Maslov. ([n. d.]). Reversible Logic Synthesis Benchmarks page. http:\/\/webhome.cs.uvic.ca\/dmaslov. Accessed February 2023."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/2011464.2011476"},{"key":"e_1_3_2_34_2","article-title":"Quantum Implementation and Analysis of DEFAULT","author":"Jang Kyungbae","year":"2022","unstructured":"Kyungbae Jang, Anubhab Baksi, Jakub Breier, Hwajeong Seo, and Anupam Chattopadhyay. 2022. Quantum Implementation and Analysis of DEFAULT. Cryptology ePrint Archive, Paper 2022\/647. (2022). https:\/\/eprint.iacr.org\/2022\/647https:\/\/eprint.iacr.org\/2022\/647","journal-title":"Cryptology ePrint Archive, Paper 2022\/647"},{"key":"e_1_3_2_35_2","unstructured":"Xiaoning Bian. ([n. d.]). STOMP-code. https:\/\/github.com\/onestruggler\/stomp-code\/tree\/8df4f46228c2f413e0cf5f8b6d25c20b6460fc0e"},{"key":"e_1_3_2_36_2","unstructured":"2023. https:\/\/github.com\/VivienVandaele\/quantum_circuit_optimization (2023)."}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639062","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639062","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:57:09Z","timestamp":1750291029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639062"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,24]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3639062"],"URL":"https:\/\/doi.org\/10.1145\/3639062","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,24]]},"assertion":[{"value":"2023-04-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}