{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T12:56:42Z","timestamp":1774616202665,"version":"3.50.1"},"reference-count":56,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T00:00:00Z","timestamp":1774569600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"\n Quantum signal processing and quantum singular value transformation are powerful tools to implement polynomial transformations of block-encoded matrices on quantum computers, and has achieved asymptotically optimal complexity in many prominent quantum algorithms. We propose a framework of quantum signal processing and quantum singular value transformation on\n \n U<\/mml:mi>\n (<\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>\n , which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on\n \n U<\/mml:mi>\n (<\/mml:mo>\n 2<\/mml:mn>\n )<\/mml:mo>\n <\/mml:math>\n in the original frameworks. We provide a comprehensive characterization of achievable polynomial matrices and give recursive algorithms to construct the quantum circuits that realize desired polynomial transformations. As three example applications, we propose a framework to realize bi-variate polynomial functions, demonstrate\n \n N<\/mml:mi>\n <\/mml:math>\n -interval decision achieving\n \n O<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>\n query complexity with a\n \n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n &#x2061;<\/mml:mo>\n N<\/mml:mi>\n <\/mml:math>\n improvement over iterative\n \n U<\/mml:mi>\n (<\/mml:mo>\n 2<\/mml:mn>\n )<\/mml:mo>\n <\/mml:math>\n -QSP requiring\n \n O<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n &#x2061;<\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>\n queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.\n <\/jats:p>","DOI":"10.22331\/q-2026-03-27-2048","type":"journal-article","created":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T12:05:25Z","timestamp":1774613125000},"page":"2048","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Signal Processing and Quantum Singular Value Transformation on\n \n U<\/mml:mi>\n (<\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>"],"prefix":"10.22331","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4121-3419","authenticated-orcid":false,"given":"Xi","family":"Lu","sequence":"first","affiliation":[{"name":"School of Mathematical Science, Zhejiang University, Hangzhou, 310027, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1468-942X","authenticated-orcid":false,"given":"Yuan","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, North Carolina State University, Raleigh, NC 27606, USA"},{"name":"Department of Computer Science, North Carolina State University, Raleigh, NC 27606, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9337-9624","authenticated-orcid":false,"given":"Hongwei","family":"Lin","sequence":"additional","affiliation":[{"name":"School of Mathematical Science, Zhejiang University, Hangzhou, 310027, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2026,3,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical review letters, 118(1):010501, 2017. doi:10.1103\/PhysRevLett.118.010501.","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193\u2013204, 2019. doi:10.1145\/3313276.3316366.","DOI":"10.1145\/3313276.3316366"},{"key":"2","doi-asserted-by":"publisher","unstructured":"John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX quantum, 2(4):040203, 2021. doi:10.1103\/PRXQuantum.2.040203.","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. doi:10.22331\/q-2019-07-12-163.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Zhiyan Ding, Xiantao Li, and Lin Lin. Simulating open quantum systems using hamiltonian simulations. PRX Quantum, 5:020332, May 2024. doi:10.1103\/PRXQuantum.5.020332.","DOI":"10.1103\/PRXQuantum.5.020332"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920\u20131950, 2017. doi:10.1137\/16M1087072.","DOI":"10.1137\/16M1087072"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Yulong Dong, Lin Lin, and Yu Tong. Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices. PRX Quantum, 3(4):040305, 2022. doi:10.1103\/PRXQuantum.3.040305.","DOI":"10.1103\/PRXQuantum.3.040305"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Theodore J Yoder, Guang Hao Low, and Isaac L Chuang. Fixed-point quantum search with an optimal number of queries. Physical review letters, 113(21):210501, 2014. doi:10.1103\/PhysRevLett.113.210501.","DOI":"10.1103\/PhysRevLett.113.210501"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Patrick Rall and Bryce Fuller. Amplitude estimation from quantum signal processing. Quantum, 7:937, 2023. doi:10.22331\/q-2023-03-02-937.","DOI":"10.22331\/q-2023-03-02-937"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum-enhanced measurements: beating the standard quantum limit. Science, 306(5700):1330\u20131336, 2004. doi:10.1126\/science.1104149.","DOI":"10.1126\/science.1104149"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum metrology. Physical review letters, 96(1):010401, 2006. doi:10.1103\/PhysRevLett.96.010401.","DOI":"10.1103\/PhysRevLett.96.010401"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Advances in quantum metrology. Nature photonics, 5(4):222\u2013229, 2011. doi:10.1038\/nphoton.2011.35.","DOI":"10.1038\/nphoton.2011.35"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro. Quantum speedup of monte carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015. doi:10.1098\/rspa.2015.0301.","DOI":"10.1098\/rspa.2015.0301"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Jeongwan Haah, Aram W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 913\u2013925, 2016. doi:10.1145\/2897518.2897585.","DOI":"10.1145\/2897518.2897585"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 899\u2013912, 2016. doi:10.1145\/2897518.2897544.","DOI":"10.1145\/2897518.2897544"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 325\u2013338, 2018. doi:10.1145\/3188745.3188802.","DOI":"10.1145\/3188745.3188802"},{"key":"16","unstructured":"Hong-Ye Hu, Ryan LaRose, Yi-Zhuang You, Eleanor Rieffel, and Zhihui Wang. Logical shadow tomography: Efficient estimation of error-mitigated observables. arXiv preprint arXiv:2203.07263, 2022."},{"key":"17","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn, Arjan Cornelissen, Andr\u00e1s Gily\u00e9n, and Giacomo Nannicini. Quantum tomography using state-preparation unitaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1265\u20131318. SIAM, 2023. doi:10.1137\/1.9781611977554.ch47.","DOI":"10.1137\/1.9781611977554.ch47"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Emanuel Knill, Gerardo Ortiz, and Rolando D Somma. Optimal quantum measurements of expectation values of observables. Physical Review A, 75(1):012328, 2007. doi:10.1103\/PhysRevA.75.012328.","DOI":"10.1103\/PhysRevA.75.012328"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Ivan Kassal, Stephen P Jordan, Peter J Love, Masoud Mohseni, and Al\u00e1n Aspuru-Guzik. Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences, 105(48):18681\u201318686, 2008. doi:10.1073\/pnas.0808245105.","DOI":"10.1073\/pnas.0808245105"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Masaya Kohda, Ryosuke Imai, Keita Kanno, Kosuke Mitarai, Wataru Mizukami, and Yuya O Nakagawa. Quantum expectation-value estimation by computational basis sampling. Physical Review Research, 4(3):033173, 2022. doi:10.1103\/PhysRevResearch.4.033173.","DOI":"10.1103\/PhysRevResearch.4.033173"},{"key":"21","doi-asserted-by":"publisher","unstructured":"William J Huggins, Kianna Wan, Jarrod McClean, Thomas E O\u2019Brien, Nathan Wiebe, and Ryan Babbush. Nearly optimal quantum algorithm for estimating multiple expectation values. Physical Review Letters, 129(24):240501, 2022. doi:10.1103\/PhysRevLett.129.240501.","DOI":"10.1103\/PhysRevLett.129.240501"},{"key":"22","unstructured":"Sophia Simon, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, Michael Streif, and Nathan Wiebe. Amplified amplitude estimation: Exploiting prior knowledge to improve estimates of expectation values. arXiv preprint arXiv:2402.14791, 2024."},{"key":"23","unstructured":"Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n. Quantum algorithms for zero-sum games. arXiv preprint arXiv:1904.03180, 2019."},{"key":"24","doi-asserted-by":"publisher","unstructured":"Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Al\u00e1n Aspuru-Guzik, and Jeremy L O\u2019brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):4213, 2014. doi:10.1038\/ncomms5213.","DOI":"10.1038\/ncomms5213"},{"key":"25","unstructured":"Nathan Wiebe, Ashish Kapoor, and Krysta M Svore. Quantum deep learning. arXiv preprint arXiv:1412.3489, 2014."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Nathan Wiebe, Ashish Kapoor, and Krysta M Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Information & Computation, 15(3-4):316\u2013356, 2015. doi:10.26421\/QIC15.3-4-7.","DOI":"10.26421\/QIC15.3-4-7"},{"key":"27","unstructured":"Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: A quantum algorithm for unsupervised machine learning. Advances in neural information processing systems, 32, 2019."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Haoya Li, Hongkang Ni, and Lexing Ying. On efficient quantum block encoding of pseudo-differential operators. Quantum, 7:1031, 2023. doi:10.22331\/q-2023-06-02-1031.","DOI":"10.22331\/q-2023-06-02-1031"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices. SIAM Journal on Matrix Analysis and Applications, 45(1):801\u2013827, 2024. doi:10.1137\/22M1484298.","DOI":"10.1137\/22M1484298"},{"key":"30","unstructured":"Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy. Finding angles for quantum signal processing with machine precision. arXiv preprint arXiv:2003.02831, 2020."},{"key":"31","doi-asserted-by":"publisher","unstructured":"Lexing Ying. Stable factorization for phase factors of quantum signal processing. Quantum, 6:842, 2022. doi:10.22331\/q-2022-10-20-842.","DOI":"10.22331\/q-2022-10-20-842"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Yulong Dong, Xiang Meng, K Birgitta Whaley, and Lin Lin. Efficient phase-factor evaluation in quantum signal processing. Physical Review A, 103(4):042419, 2021. doi:10.1103\/PhysRevA.103.042419.","DOI":"10.1103\/PhysRevA.103.042419"},{"key":"33","unstructured":"Lorenzo Laneve. Quantum signal processing over su (n): exponential speed-up for polynomial transformations under shor-like assumptions. arXiv preprint arXiv:2311.03949, 2023."},{"key":"34","unstructured":"Yulong Dong and Lin Lin. Multi-level quantum signal processing with applications to ground state preparation using fast-forwarded hamiltonian evolution. arXiv preprint arXiv:2406.02086, 2024."},{"key":"35","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Yuan Su. Quantum eigenvalue processing. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1051\u20131062, 2024. doi:10.1109\/FOCS61266.2024.00070.","DOI":"10.1109\/FOCS61266.2024.00070"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Zane M Rossi and Isaac L Chuang. Multivariable quantum signal processing (m-qsp): prophecies of the two-headed oracle. Quantum, 6:811, 2022. doi:10.22331\/q-2022-09-20-811.","DOI":"10.22331\/q-2022-09-20-811"},{"key":"37","unstructured":"Bal\u00e1zs N\u00e9meth, Blanka K\u00f6v\u00e9r, Bogl\u00e1rka Kulcs\u00e1r, Roland Botond Mikl\u00f3si, and Andr\u00e1s Gily\u00e9n. On variants of multivariate quantum signal processing and their characterizations. arXiv preprint arXiv:2312.09072, 2023."},{"key":"38","doi-asserted-by":"publisher","unstructured":"Yuta Kikuchi, Conor Mc Keever, Luuk Coopmans, Michael Lubasch, and Marcello Benedetti. Realization of quantum signal processing on a noisy quantum computer. npj Quantum Information, 9(1):93, 2023. doi:10.1038\/s41534-023-00762-0.","DOI":"10.1038\/s41534-023-00762-0"},{"key":"39","doi-asserted-by":"publisher","unstructured":"J.-T. Bu, Lei Zhang, Zhan Yu, Jing-Bo Wang, W.-Q. Ding, W.-F. Yuan, B. Wang, H.-J. Du, W.-J. Chen, L. Chen, J.-W. Zhang, J.-C. Li, F. Zhou, Xin Wang, and M. Feng. Exploring the experimental limit of deep quantum signal processing using a trapped-ion simulator. Phys. Rev. Appl., 23:034073, Mar 2025. doi:10.1103\/PhysRevApplied.23.034073.","DOI":"10.1103\/PhysRevApplied.23.034073"},{"key":"40","unstructured":"Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. arXiv preprint quant-ph\/0005055, 2000."},{"key":"41","doi-asserted-by":"publisher","unstructured":"Danial Motlagh and Nathan Wiebe. Generalized quantum signal processing. PRX Quantum, 5(2):020368, 2024. doi:10.1103\/PRXQuantum.5.020368.","DOI":"10.1103\/PRXQuantum.5.020368"},{"key":"42","doi-asserted-by":"crossref","unstructured":"Andrew M Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. arXiv preprint arXiv:1202.5822, 2012.","DOI":"10.26421\/QIC12.11-12-1"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Norbert Wiener and Pesi Masani. The prediction theory of multivariate stochastic processes. Acta mathematica, 98(1):111\u2013150, 1957. doi:10.1007\/BF02404472.","DOI":"10.1007\/BF02404472"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Lasha Ephremidze. An elementary proof of the polynomial matrix spectral factorization theorem. Proceedings of the Royal Society of Edinburgh Section A: Mathematics, 144(4):747\u2013751, 2014. doi:10.1017\/S0308210512001552.","DOI":"10.1017\/S0308210512001552"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Jasmine Sinanan-Singh, Gabriel L Mintzer, Isaac L Chuang, and Yuan Liu. Single-shot quantum signal processing interferometry. Quantum, 8:1427, 2024. doi:10.22331\/q-2024-07-30-1427.","DOI":"10.22331\/q-2024-07-30-1427"},{"key":"46","unstructured":"Christopher M Dawson and Michael A Nielsen. The solovay-kitaev algorithm. arXiv preprint quant-ph\/0505030, 2005."},{"key":"47","doi-asserted-by":"publisher","unstructured":"Tien Trung Pham, Rodney Van Meter, and Dominic Horsman. Optimization of the solovay-kitaev algorithm. Physical Review A\u2014Atomic, Molecular, and Optical Physics, 87(5):052332, 2013. doi:10.1103\/PhysRevA.87.052332.","DOI":"10.1103\/PhysRevA.87.052332"},{"key":"48","unstructured":"Greg Kuperberg. Breaking the cubic barrier in the solovay-kitaev algorithm. arXiv preprint arXiv:2306.13158, 2023."},{"key":"49","doi-asserted-by":"publisher","unstructured":"Lorenzo Laneve and Stefan Wolf. On multivariate polynomials achievable with quantum signal processing. Quantum, 9:1641, February 2025. doi:10.22331\/q-2025-02-20-1641.","DOI":"10.22331\/q-2025-02-20-1641"},{"key":"50","doi-asserted-by":"crossref","unstructured":"Leopold Fej\u00e9r. \u00dcber trigonometrische polynome. 1916.","DOI":"10.1515\/crll.1916.146.53"},{"key":"51","doi-asserted-by":"crossref","unstructured":"Frigyes Riesz. \u00fcber ein problem des herrn carath\u00e9odory. JOURNAL FUR DIE REINE UND ANGEWANDTE MATHEMATIK, 146:83\u201387, 1916.","DOI":"10.1515\/crll.1916.146.83"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Wim van Dam, G Mauro D\u2019Ariano, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Optimal quantum circuits for general phase estimation. Physical review letters, 98(9):090501, 2007. doi:10.1103\/PhysRevLett.98.090501.","DOI":"10.1103\/PhysRevLett.98.090501"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Wim Van Dam, G Mauro D'Ariano, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Optimal phase estimation in quantum networks. Journal of Physics A: Mathematical and Theoretical, 40(28):7971, 2007. doi:10.1088\/1751-8113\/40\/28\/S07.","DOI":"10.1088\/1751-8113\/40\/28\/S07"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Wojciech G\u00f3recki, Rafa\u0142 Demkowicz-Dobrza\u0144ski, Howard M Wiseman, and Dominic W Berry. $\\pi$-corrected heisenberg limit. Physical review letters, 124(3):030501, 2020. doi:10.1103\/PhysRevLett.124.030501.","DOI":"10.1103\/PhysRevLett.124.030501"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Yuan Liu, Shraddha Singh, Kevin C. Smith, Eleanor Crane, John M. Martyn, Alec Eickbusch, Alexander Schuckert, Richard D. Li, Jasmine Sinanan-Singh, Micheline B. Soley, Takahiro Tsunoda, Isaac L. Chuang, Nathan Wiebe, and Steven M. Girvin. Hybrid oscillator-qubit quantum processors: Instruction set architectures, abstract machine models, and applications. PRX Quantum, 7:010201, Jan 2026. doi:10.1103\/4rf7-9tfx.","DOI":"10.1103\/4rf7-9tfx"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-03-27-2048\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T12:05:33Z","timestamp":1774613133000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-03-27-2048\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,27]]},"references-count":56,"URL":"https:\/\/doi.org\/10.22331\/q-2026-03-27-2048","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,27]]},"article-number":"2048"}}