{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T19:28:14Z","timestamp":1772566094403,"version":"3.50.1"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T00:00:00Z","timestamp":1744329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"PEPR EPiQ","award":["ANR-22-PETQ-0007"],"award-info":[{"award-number":["ANR-22-PETQ-0007"]}]},{"name":"ANR JCJC DisQC","award":["ANR-22-CE47-0002-01"],"award-info":[{"award-number":["ANR-22-CE47-0002-01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Unitary and non-unitary diagonal operators are fundamental building blocks in quantum algorithms with applications in the resolution of partial differential equations, Hamiltonian simulations, the loading of classical data on quantum computers (quantum state preparation), and many others. In this paper, we introduce a general approach to implement unitary and non-unitary diagonal operators with efficient-adjustable-depth quantum circuits. The depth, i.e., the number of layers of quantum gates of the quantum circuit, is reducible with respect either to the width, i.e., the number of ancilla qubits, or to the accuracy between the implemented operator and the target one. While exact methods have an optimal exponential scaling either in terms of size, i.e., the total number of primitive quantum gates, or width, approximate methods prove to be efficient for the class of diagonal operators depending on smooth, at least differentiable, functions. Our approach is general enough to allow any method for diagonal operators to become adjustable-depth or approximate, decreasing the depth of the circuit by increasing its width or its approximation level. This feature offers flexibility and can match with the hardware limitations in coherence time or cumulative gate error. We illustrate these methods by performing quantum state preparation and non-unitary-real-space simulation of the diffusion equation. This simulation paves the way to efficient implementations of stochastic models useful in physics, chemistry, biology, image processing, and finance.<\/jats:p>","DOI":"10.1145\/3718348","type":"journal-article","created":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T11:18:26Z","timestamp":1739963906000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Quantum Circuits for Non-Unitary and Unitary Diagonal Operators with Space-Time-Accuracy Trade-Offs"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7785-8246","authenticated-orcid":false,"given":"Julien","family":"Zylberman","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, Observatoire de Paris, Universit\u00e9 PSL, CNRS, LUX, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1973-6574","authenticated-orcid":false,"given":"Ugo","family":"Nzongani","sequence":"additional","affiliation":[{"name":"CNRS, LIS, Aix-Marseille Universit\u00e9, Universit\u00e9 de Toulon, Marseille, France and Unit\u00e9 de Math\u00e9matiques Appliqu\u00e9es, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2923-3361","authenticated-orcid":false,"given":"Andrea","family":"Simonetto","sequence":"additional","affiliation":[{"name":"Unit\u00e9 de Math\u00e9matiques Appliqu\u00e9es, ENSTA Paris, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6894-6159","authenticated-orcid":false,"given":"Fabrice","family":"Debbasch","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, Observatoire de Paris, Universit\u00e9 PSL, CNRS, LUX, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"e_1_3_3_3_2","volume-title":"Applications of Walsh and Related Functions, with an Introduction to Sequency Theory","author":"Beauchamp Kenneth George","year":"1984","unstructured":"Kenneth George Beauchamp. 1984. Applications of Walsh and Related Functions, with an Introduction to Sequency Theory. Vol. 2. Academic Press."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591854"},{"issue":"9","key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"090502","DOI":"10.1103\/PhysRevLett.114.090502","article-title":"Simulating Hamiltonian dynamics with a truncated Taylor series","volume":"114","author":"Berry Dominic W.","year":"2015","unstructured":"Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. 2015. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters 114, 9 (2015), 090502.","journal-title":"Physical Review Letters"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-017-3002-y"},{"key":"e_1_3_3_7_2","volume-title":"Optimization Over Integers","author":"Bertsimas D.","year":"2005","unstructured":"D. Bertsimas and R. Weismantel. 2005. Optimization Over Integers. Dynamic Ideas."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-405X(76)90024-6"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","unstructured":"Gilles Brassard Peter H\u00f8yer Michele Mosca and Alain Tapp. 2002. Quantum amplitude amplification and estimation. (2002) 53\u201374 pages. DOI:10.1090\/conm\/305\/05215","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1157"},{"issue":"2","key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s11128-021-02996-3","article-title":"Quantum algorithm for the advection\u2013diffusion equation simulated with the lattice Boltzmann method","volume":"20","author":"Budinski Ljubomir","year":"2021","unstructured":"Ljubomir Budinski. 2021. Quantum algorithm for the advection\u2013diffusion equation simulated with the lattice Boltzmann method. Quantum Information Processing 20, 2 (2021), 57.","journal-title":"Quantum Information Processing"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/2011572.2011575"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-11-17-860"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/2481569.2481570"},{"issue":"1","key":"e_1_3_3_16_2","doi-asserted-by":"crossref","first-page":"5886","DOI":"10.1038\/s41467-024-50065-x","article-title":"Polylogarithmic-depth controlled-NOT gates without ancilla qubits","volume":"15","author":"Claudon Baptiste","year":"2024","unstructured":"Baptiste Claudon, Julien Zylberman, C\u00e9sar Feniou, Fabrice Debbasch, Alberto Peruzzo, and Jean-Philip Piquemal. 2024. Polylogarithmic-depth controlled-NOT gates without ancilla qubits. Nature Communications 15, 1 (2024), 5886.","journal-title":"Nature Communications"},{"key":"e_1_3_3_17_2","unstructured":"D. Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. (2002). arxiv:quant-ph\/quant-ph\/0201067"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/qute.201900015"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-016-1452-3"},{"issue":"6","key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/s11128-022-03549-y","article-title":"Double sparse quantum state preparation","volume":"21","author":"Veras Tiago M. L. de","year":"2022","unstructured":"Tiago M. L. de Veras, Leon D. da Silva, and Adenilton J. da Silva. 2022. Double sparse quantum state preparation. Quantum Information Processing 21, 6 (2022), 204.","journal-title":"Quantum Information Processing"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1057726"},{"issue":"11","key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"3197","DOI":"10.1021\/acs.jpclett.3c03159","article-title":"Sparse quantum state preparation for strongly correlated systems","volume":"15","author":"Feniou C\u00e9sar","year":"2024","unstructured":"C\u00e9sar Feniou, Olivier Adjoua, Baptiste Claudon, Julien Zylberman, Emmanuel Giner, and Jean-Philip Piquemal. 2024. Sparse quantum state preparation for strongly correlated systems. The Journal of Physical Chemistry Letters 15, 11 (2024), 3197\u20133205.","journal-title":"The Journal of Physical Chemistry Letters"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-45396-2","volume-title":"Stochastic Processes in Physics, Chemistry, and Biology","author":"Freund Jan A.","year":"2000","unstructured":"Jan A. Freund and Thorsten P\u00f6schel. 2000. Stochastic Processes in Physics, Chemistry, and Biology. Vol. 557. Springer Science & Business Media."},{"issue":"3","key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"033200","DOI":"10.1103\/PhysRevResearch.3.033200","article-title":"Experimental quantum learning of a spectral decomposition","volume":"3","author":"Geller Michael R.","year":"2021","unstructured":"Michael R. Geller, Zo\u00eb Holmes, Patrick J. Coles, and Andrew Sornborger. 2021. Experimental quantum learning of a spectral decomposition. Physical Review Research 3, 3 (2021), 033200.","journal-title":"Physical Review Research"},{"key":"e_1_3_3_25_2","unstructured":"Craig Gidney. 2015. Using quantum gates instead of ancilla bits. https:\/\/algassert.com\/circuits\/2015\/06\/22\/using-quantum-gates-instead-of-ancilla- bits.html. (2015)."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_3_3_27_2","first-page":"1","volume-title":"ACM International Conference Proceeding Series","volume":"58","author":"Gingrich Robert M.","year":"2004","unstructured":"Robert M. Gingrich and Colin P. Williams. 2004. Non-unitary probabilistic quantum computing. In ACM International Conference Proceeding Series, Vol. 58. Citeseer, 1\u20136."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-017-1768-7"},{"key":"e_1_3_3_29_2","volume-title":"Digital Image Processing","author":"Gonzalez Rafael C.","year":"2009","unstructured":"Rafael C. Gonzalez. 2009. Digital Image Processing. Pearson Education India."},{"key":"e_1_3_3_30_2","unstructured":"F. Gray. 1953. Pulse Code Communication. (1953). http:\/\/www.google.com\/patents\/US2632058US Patent 2 632 058."},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","unstructured":"Robert M. Gray and others. 2006. Toeplitz and circulant matrices: A review. Foundations and Trends\u00ae in Communications and Information Theory 2 3 (2006) 155\u2013239.","DOI":"10.1561\/0100000006"},{"key":"e_1_3_3_32_2","article-title":"Creating superpositions that correspond to efficiently integrable probability distributions","author":"Grover Lov","year":"2002","unstructured":"Lov Grover and Terry Rudolph. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph\/0208112 (2002).","journal-title":"arXiv preprint quant-ph\/0208112"},{"key":"e_1_3_3_33_2","doi-asserted-by":"crossref","unstructured":"Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. (1996). arxiv:quant-ph\/quant-ph\/9605043","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1217069"},{"key":"e_1_3_3_35_2","unstructured":"Julien Zylberman Ugo Nzongani Andrea Simonetto and Fabrice Debbasch. 2024. Quantum circuits for non-unitary and unitary diagonal operators. https:\/\/github.com\/ugo-nzongani\/Quantum-circuits-for-non-unitary-and-unitary-diagonal-operators. (2024)."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0808245105"},{"key":"e_1_3_3_37_2","article-title":"Tutorial on the Quantikz package","author":"Kay Alastair","year":"2018","unstructured":"Alastair Kay. 2018. Tutorial on the Quantikz package. arXiv preprint arXiv:1809.03842 (2018).","journal-title":"arXiv preprint arXiv:1809.03842"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-022-04442-6"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-07-12-163"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-04-08-1311"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3569095"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799355053"},{"issue":"2","key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"020368","DOI":"10.1103\/PRXQuantum.5.020368","article-title":"Generalized quantum signal processing","volume":"5","author":"Motlagh Danial","year":"2024","unstructured":"Danial Motlagh and Nathan Wiebe. 2024. Generalized quantum signal processing. PRX Quantum 5, 2 (2024), 020368.","journal-title":"PRX Quantum"},{"key":"e_1_3_3_45_2","unstructured":"Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information. Cambridge university press."},{"issue":"5","key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s11128-024-04400-2","article-title":"Adjustable-depth quantum circuit for position-dependent coin operators of discrete-time quantum walks","volume":"23","author":"Nzongani Ugo","year":"2024","unstructured":"Ugo Nzongani and Pablo Arnault. 2024. Adjustable-depth quantum circuit for position-dependent coin operators of discrete-time quantum walks. Quantum Information Processing 23, 5 (2024), 193.","journal-title":"Quantum Information Processing"},{"issue":"7","key":"e_1_3_3_47_2","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/s11128-023-03957-8","article-title":"Quantum circuits for discrete-time quantum walks with position-dependent coin operator","volume":"22","author":"Nzongani Ugo","year":"2023","unstructured":"Ugo Nzongani, Julien Zylberman, Carlo-Elia Doncecchi, Armando P\u00e9rez, Fabrice Debbasch, and Pablo Arnault. 2023. Quantum circuits for discrete-time quantum walks with position-dependent coin operator. Quantum Information Processing 22, 7 (2023), 270.","journal-title":"Quantum Information Processing"},{"key":"e_1_3_3_48_2","volume-title":"Stochastic Differential Equations: An Introduction with Applications","author":"Oksendal Bernt","year":"2013","unstructured":"Bernt Oksendal. 2013. Stochastic Differential Equations: An Introduction with Applications. Springer Science & Business Media."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8659(08)00011-2"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.106.022414"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1021\/acsomega.3c09720"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539795293172"},{"key":"e_1_3_3_53_2","article-title":"Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis","author":"Sun Xiaoming","year":"2023","unstructured":"Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. 2023. Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2023).","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"issue":"04","key":"e_1_3_3_54_2","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1142\/S0219749905001456","article-title":"Nonunitary quantum circuit","volume":"3","author":"Terashima Hiroaki","year":"2005","unstructured":"Hiroaki Terashima and Masahito Ueda. 2005. Nonunitary quantum circuit. International Journal of Quantum Information 3, 04 (2005), 633\u2013647.","journal-title":"International Journal of Quantum Information"},{"key":"e_1_3_3_55_2","unstructured":"N. G. Van Kampen. 2004. Stochastic Processes in Physics and Chemistry. 5th. (2004)."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.2307\/2387224"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.5555\/3179320.3179326"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/16\/3\/033040"},{"key":"e_1_3_3_59_2","article-title":"Simulations of many-body quantum systems by a quantum computer","author":"Wiesner Stephen","year":"1996","unstructured":"Stephen Wiesner. 1996. Simulations of many-body quantum systems by a quantum computer. arXiv preprint quant-ph\/9603028 (1996).","journal-title":"arXiv preprint quant-ph\/9603028"},{"issue":"6","key":"e_1_3_3_60_2","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1109\/T-C.1975.224271","article-title":"Function approximation by Walsh series","volume":"100","author":"Yuen Chung-Kwong","year":"1975","unstructured":"Chung-Kwong Yuen. 1975. Function approximation by Walsh series. IEEE Trans. Comput. 100, 6 (1975), 590\u2013598.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1998.0162"},{"issue":"4","key":"e_1_3_3_62_2","doi-asserted-by":"crossref","first-page":"042601","DOI":"10.1103\/PhysRevA.109.042601","article-title":"Depth-optimized quantum circuit synthesis for diagonal unitary operators with asymptotically optimal gate count","volume":"109","author":"Zhang Shihao","year":"2024","unstructured":"Shihao Zhang, Kai Huang, and Lvzhou Li. 2024. Depth-optimized quantum circuit synthesis for diagonal unitary operators with asymptotically optimal gate count. Physical Review A 109, 4 (2024), 042601.","journal-title":"Physical Review A"},{"issue":"23","key":"e_1_3_3_63_2","doi-asserted-by":"crossref","first-page":"230504","DOI":"10.1103\/PhysRevLett.129.230504","article-title":"Quantum state preparation with optimal circuit depth: Implementations and applications","volume":"129","author":"Zhang Xiao-Ming","year":"2022","unstructured":"Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. 2022. Quantum state preparation with optimal circuit depth: Implementations and applications. Physical Review Letters 129, 23 (2022), 230504.","journal-title":"Physical Review Letters"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.109.042401"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3718348","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3718348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:34Z","timestamp":1750298254000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3718348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,11]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3718348"],"URL":"https:\/\/doi.org\/10.1145\/3718348","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,11]]},"assertion":[{"value":"2024-06-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}