{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:41:56Z","timestamp":1787017316329,"version":"build-2736575974"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T00:00:00Z","timestamp":1632960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-17-CE25-0009-02"],"award-info":[{"award-number":["ANR-17-CE25-0009-02"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DGE of the French Ministry of Industry","award":["PIA-GDN\/QuantEx P163746-484124"],"award-info":[{"award-number":["PIA-GDN\/QuantEx P163746-484124"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>Linear reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. These circuits can be efficiently simulated by classical computers and their size is polynomially bounded by the number of qubits, making them a good candidate to deploy efficient methods to reduce computational costs. We propose a new algorithm for synthesizing any linear reversible operator by using an optimized version of the Gaussian elimination algorithm coupled with a tuned LU factorization. We also improve the scalability of purely greedy methods. Overall, on random operators, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes: The custom Gaussian elimination algorithm provides the best results for large problem sizes (n &gt; 150), while the purely greedy methods provide quasi optimal results when n &lt; 30. On a benchmark of reversible functions, we manage to significantly reduce the CNOT count and the depth of the circuit while keeping other metrics of importance (T-count, T-depth) as low as possible.<\/jats:p>","DOI":"10.1145\/3474226","type":"journal-article","created":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T13:35:15Z","timestamp":1633008915000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits"],"prefix":"10.1145","volume":"2","author":[{"given":"Timoth\u00e9e Goubault","family":"De Brugi\u00e8re","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, Orsay, France and Atos Quantum Lab, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Baboulin","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, Orsay, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Beno\u00eet","family":"Valiron","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, Orsay, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon","family":"Martiel","sequence":"additional","affiliation":[{"name":"Atos Quantum Lab, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cyril","family":"Allouche","sequence":"additional","affiliation":[{"name":"Atos Quantum Lab, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,9,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1155\/2015\/736138"},{"key":"e_1_2_1_3_1","unstructured":"Matthew Amy. [n.d.]. Matthew Amy\u2019s Github. Retrieved from https:\/\/github.com\/meamy.  Matthew Amy. [n.d.]. Matthew Amy\u2019s Github. Retrieved from https:\/\/github.com\/meamy."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aad8ca"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2341953"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000671"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00108-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-012-9124-7"},{"key":"e_1_2_1_9_1","volume-title":"RC 2020, Oslo, Norway, July 9-10, 2020, Proceedings(Lecture Notes in Computer Science, Vol.\u00a0 12227)","author":"de Brugi\u00e8re Timoth\u00e9e\u00a0Goubault","year":"2020","unstructured":"Timoth\u00e9e\u00a0Goubault de Brugi\u00e8re , Marc Baboulin , Beno\u00eet Valiron , Simon Martiel , and Cyril Allouche . 2020 . Quantum CNOT circuits synthesis for NISQ architectures using the syndrome decoding problem. In Reversible Computation - 12th International Conference , RC 2020, Oslo, Norway, July 9-10, 2020, Proceedings(Lecture Notes in Computer Science, Vol.\u00a0 12227) , Ivan Lanese and Mariusz Rawski (Eds.). Springer, 189\u2013205. DOI:https:\/\/doi.org\/10.1007\/978-3-030-52482-1_11 10.1007\/978-3-030-52482-1_11 Timoth\u00e9e\u00a0Goubault de Brugi\u00e8re, Marc Baboulin, Beno\u00eet Valiron, Simon Martiel, and Cyril Allouche. 2020. Quantum CNOT circuits synthesis for NISQ architectures using the syndrome decoding problem. In Reversible Computation - 12th International Conference, RC 2020, Oslo, Norway, July 9-10, 2020, Proceedings(Lecture Notes in Computer Science, Vol.\u00a0 12227), Ivan Lanese and Mariusz Rawski (Eds.). Springer, 189\u2013205. DOI:https:\/\/doi.org\/10.1007\/978-3-030-52482-1_11"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087611"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"15459","DOI":"10.1038\/ncomms15459","article-title":"Digital logic circuits in yeast with CRISPR-dCas9 NOR gates","volume":"8","author":"Gander W.","year":"2017","unstructured":"Miles\u00a0 W. Gander , Justin\u00a0 D. Vrana , William\u00a0 E. Voje , James\u00a0 M. Carothers , and Eric Klavins . 2017 . Digital logic circuits in yeast with CRISPR-dCas9 NOR gates . Nat. Commun. 8 (2017), 15459 . Miles\u00a0W. Gander, Justin\u00a0D. Vrana, William\u00a0E. Voje, James\u00a0M. Carothers, and Eric Klavins. 2017. Digital logic circuits in yeast with CRISPR-dCas9 NOR gates. Nat. Commun. 8 (2017), 15459.","journal-title":"Nat. Commun."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/248979"},{"key":"e_1_2_1_14_1","volume-title":"Combinatorial synthesis of genetic networks. Science 296, 5572","author":"Guet C.","year":"2002","unstructured":"C\u0103lin\u00a0 C. Guet , Michael\u00a0 B. Elowitz , Weihong Hsing , and Stanislas Leibler . 2002. Combinatorial synthesis of genetic networks. Science 296, 5572 ( 2002 ), 1466\u20131470. C\u0103lin\u00a0C. Guet, Michael\u00a0B. Elowitz, Weihong Hsing, and Stanislas Leibler. 2002. Combinatorial synthesis of genetic networks. Science 296, 5572 (2002), 1466\u20131470."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622591.1622599"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"015004","DOI":"10.1088\/2058-9565\/aad604","article-title":"An efficient quantum compiler that reduces T count","volume":"4","author":"Heyfron E.","year":"2019","unstructured":"Luke\u00a0 E. Heyfron and Earl\u00a0 T. Campbell . 2019 . An efficient quantum compiler that reduces T count . Quant. Sci. Technol. 4 , 1 (2019), 015004 . Retrieved from http:\/\/stacks.iop.org\/2058-9565\/4\/i=1\/a=015004. Luke\u00a0E. Heyfron and Earl\u00a0T. Campbell. 2019. An efficient quantum compiler that reduces T count. Quant. Sci. Technol. 4, 1 (2019), 015004. Retrieved from http:\/\/stacks.iop.org\/2058-9565\/4\/i=1\/a=015004.","journal-title":"Quant. Sci. Technol."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00093-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381102"},{"key":"e_1_2_1_20_1","first-page":"7","article-title":"CNOT circuit extraction for topologically-constrained quantum memories","volume":"20","author":"Kissinger Aleks","year":"2020","unstructured":"Aleks Kissinger and Arianne\u00a0Meijer-van de Griend. 2020 . CNOT circuit extraction for topologically-constrained quantum memories . Quant. Inf. Comput. 20 , 7 - 8 (2020), 581\u2013596. Retrieved from http:\/\/www.rintonpress.com\/xxqic20\/qic-20-78\/0581-0596.pdf. Aleks Kissinger and Arianne\u00a0Meijer-van de Griend. 2020. CNOT circuit extraction for topologically-constrained quantum memories. Quant. Inf. Comput. 20, 7-8 (2020), 581\u2013596. Retrieved from http:\/\/www.rintonpress.com\/xxqic20\/qic-20-78\/0581-0596.pdf.","journal-title":"Quant. Inf. Comput."},{"key":"e_1_2_1_21_1","first-page":"1","article-title":"Linear optical quantum computing with photonic qubits","volume":"79","author":"Kok Pieter","year":"2007","unstructured":"Pieter Kok , W.\u00a0 J. Munro , Kae Nemoto , T.\u00a0 C. Ralph , Jonathan\u00a0 P. Dowling , and G.\u00a0 J. Milburn . 2007 . Linear optical quantum computing with photonic qubits . Rev. Mod. Phys. 79 , 1 (Jan. 2007), 135\u2013174. DOI:https:\/\/doi.org\/10.1103\/RevModPhys.79.135 10.1103\/RevModPhys.79.135 Pieter Kok, W.\u00a0J. Munro, Kae Nemoto, T.\u00a0C. Ralph, Jonathan\u00a0P. Dowling, and G.\u00a0J. Milburn. 2007. Linear optical quantum computing with photonic qubits. Rev. Mod. Phys. 79, 1 (Jan. 2007), 135\u2013174. DOI:https:\/\/doi.org\/10.1103\/RevModPhys.79.135","journal-title":"Rev. Mod. Phys."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90084-0"},{"key":"e_1_2_1_23_1","volume-title":"Algorithms and Theory of Computation Handbook","author":"Korf E.","unstructured":"Richard\u00a0 E. Korf . 1996. Artificial intelligence search algorithms . In Algorithms and Theory of Computation Handbook , Chapman & Hall\/CRC Applied Algorithms and Data Structures Series. CRC Press . DOI:10.1201\/9781420049503-c37 10.1201\/9781420049503-c37 Richard\u00a0E. Korf. 1996. Artificial intelligence search algorithms. In Algorithms and Theory of Computation Handbook, Chapman & Hall\/CRC Applied Algorithms and Data Structures Series. CRC Press. DOI:10.1201\/9781420049503-c37"},{"key":"e_1_2_1_24_1","volume-title":"Computation at a distance. Chicago J. Theor. Comput. Sci. 2007","author":"Kutin A.","year":"2007","unstructured":"Samuel\u00a0 A. Kutin , David\u00a0Petrie Moulton , and Lawren Smithline . 2007. Computation at a distance. Chicago J. Theor. Comput. Sci. 2007 ( 2007 ). Retrieved from http:\/\/cjtcs.cs.uchicago.edu\/articles\/2007\/1\/contents.html. Samuel\u00a0A. Kutin, David\u00a0Petrie Moulton, and Lawren Smithline. 2007. Computation at a distance. Chicago J. Theor. Comput. Sci. 2007 (2007). Retrieved from http:\/\/cjtcs.cs.uchicago.edu\/articles\/2007\/1\/contents.html."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2981345.2981441"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.76.052310"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/3179430.3179432"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"4729","DOI":"10.1109\/TIT.2018.2825602","article-title":"Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations","volume":"64","author":"Maslov Dmitri","year":"2018","unstructured":"Dmitri Maslov and Martin Roetteler . 2018 . Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations . IEEE Trans. Inf. Theor. 64 , 7 (2018), 4729 \u2013 4738 . DOI:https:\/\/doi.org\/10.1109\/TIT.2018.2825602 10.1109\/TIT.2018.2825602 Dmitri Maslov and Martin Roetteler. 2018. Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations. IEEE Trans. Inf. Theor. 64, 7 (2018), 4729\u20134738. DOI:https:\/\/doi.org\/10.1109\/TIT.2018.2825602","journal-title":"IEEE Trans. Inf. Theor."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Conference on Computer-aided Design, ICCAD 2019","author":"Meuli Giulia","year":"2019","unstructured":"Giulia Meuli , Mathias Soeken , Earl Campbell , Martin Roetteler , and Giovanni\u00a0De Micheli . 2019 . The role of multiplicative complexity in compiling low $T$-count Oracle Circuits . In Proceedings of the International Conference on Computer-aided Design, ICCAD 2019 , Westminster, CO, USA , November 4-7, 2019, David\u00a0Z. Pan (Ed.). ACM, 1\u20138. DOI:https:\/\/doi.org\/10.1109\/ICCAD45719.2019.8942093 10.1109\/ICCAD45719.2019.8942093 Giulia Meuli, Mathias Soeken, Earl Campbell, Martin Roetteler, and Giovanni\u00a0De Micheli. 2019. The role of multiplicative complexity in compiling low $T$-count Oracle Circuits. In Proceedings of the International Conference on Computer-aided Design, ICCAD 2019, Westminster, CO, USA, November 4-7, 2019, David\u00a0Z. Pan (Ed.). ACM, 1\u20138. DOI:https:\/\/doi.org\/10.1109\/ICCAD45719.2019.8942093"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the International Conference on Reversible Computation. Springer, 175\u2013188","author":"Meuli Giulia","year":"2018","unstructured":"Giulia Meuli , Mathias Soeken , and Giovanni De\u00a0Micheli . 2018 . SAT-based CNOT, T quantum circuit synthesis . In Proceedings of the International Conference on Reversible Computation. Springer, 175\u2013188 . Giulia Meuli, Mathias Soeken, and Giovanni De\u00a0Micheli. 2018. SAT-based CNOT, T quantum circuit synthesis. In Proceedings of the International Conference on Reversible Computation. Springer, 175\u2013188."},{"key":"e_1_2_1_32_1","volume-title":"ROS: Resource-constrained oracle synthesis for quantum computers.","author":"Meuli Giulia","year":"2020","unstructured":"Giulia Meuli , Mathias Soeken , Martin Roetteler , and Giovanni\u00a0De Micheli . 2020 . ROS: Resource-constrained oracle synthesis for quantum computers. Retrieved from https:\/\/arxiv.org\/abs\/2005.00211. Giulia Meuli, Mathias Soeken, Martin Roetteler, and Giovanni\u00a0De Micheli. 2020. ROS: Resource-constrained oracle synthesis for quantum computers. Retrieved from https:\/\/arxiv.org\/abs\/2005.00211."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601069"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the Electron Devices Meeting, Vol.\u00a0 21","author":"E.","unstructured":"Gordon\u00a0 E. Moore et\u00a0al. 1975. Progress in digital integrated electronics . In Proceedings of the Electron Devices Meeting, Vol.\u00a0 21 . 11\u201313. Gordon\u00a0E. Moore et\u00a0al. 1975. Progress in digital integrated electronics. In Proceedings of the Electron Devices Meeting, Vol.\u00a0 21. 11\u201313."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1038\/s41534-018-0072-4","article-title":"Automated optimization of large quantum circuits with continuous parameters. npj","volume":"4","author":"Nam Yunseong","year":"2018","unstructured":"Yunseong Nam , Neil\u00a0 J. Ross , Yuan Su , Andrew\u00a0 M. Childs , and Dmitri Maslov . 2018 . Automated optimization of large quantum circuits with continuous parameters. npj Quant. Inf. 4 , 1 (2018), 23 . DOI:https:\/\/doi.org\/10.1038\/s41534-018-0072-4 10.1038\/s41534-018-0072-4 Yunseong Nam, Neil\u00a0J. Ross, Yuan Su, Andrew\u00a0M. Childs, and Dmitri Maslov. 2018. Automated optimization of large quantum circuits with continuous parameters. npj Quant. Inf. 4, 1 (2018), 23. DOI:https:\/\/doi.org\/10.1038\/s41534-018-0072-4","journal-title":"Quant. Inf."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab79b1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1972505"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011763.2011767"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431220"},{"key":"e_1_2_1_40_1","volume-title":"A cost minimization approach to synthesis of linear reversible circuits. arXiv preprint arXiv:1407.0070","author":"Schaeffer Ben","year":"2014","unstructured":"Ben Schaeffer and Marek Perkowski . 2014. A cost minimization approach to synthesis of linear reversible circuits. arXiv preprint arXiv:1407.0070 ( 2014 ). Ben Schaeffer and Marek Perkowski. 2014. A cost minimization approach to synthesis of linear reversible circuits. arXiv preprint arXiv:1407.0070 (2014)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598347011"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/3176748.3176755"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 3rd Annual Symposium on Combinatorial Search.","author":"Wilt Christopher\u00a0Makoto","year":"2010","unstructured":"Christopher\u00a0Makoto Wilt , Jordan\u00a0Tyler Thayer , and Wheeler Ruml . 2010 . A comparison of greedy search algorithms . In Proceedings of the 3rd Annual Symposium on Combinatorial Search. Christopher\u00a0Makoto Wilt, Jordan\u00a0Tyler Thayer, and Wheeler Ruml. 2010. A comparison of greedy search algorithms. In Proceedings of the 3rd Annual Symposium on Combinatorial Search."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/647288.721436"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/21\/17\/175202"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/777092.777250"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474226","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3474226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:28:21Z","timestamp":1750181301000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,30]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3474226"],"URL":"https:\/\/doi.org\/10.1145\/3474226","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,30]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}