Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$
Summarize this article with:
AbstractQuantum 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 $U(N)$, which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on $U(2)$ 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$-interval decision achieving $O(d)$ query complexity with a $\log_2 N$ improvement over iterative $U(2)$-QSP requiring $O(d\log_2 N)$ queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.Popular summaryQuantum Signal Processing (QSP) is a powerful method for implementing polynomial transformations on quantum computers, underpinning many of the most efficient quantum algorithms known today — from Hamiltonian simulation to quantum search and amplitude estimation. In the standard framework, a circuit alternates a programmable single-qubit gate with a fixed unitary oracle, producing one independent polynomial function of that oracle as output. This single-qubit restriction, however, means only one transformation can be realized at a time. We generalize QSP by replacing the single-qubit ancilla with an N-dimensional one, using arbitrary N×N unitary rotations in place of single-qubit phase gates. A single circuit can then simultaneously realize an entire matrix of polynomial transformations. We fully characterize which set of polynomial matrices are achievable and give explicit recursive algorithms for constructing the required circuits. This richer framework unlocks three concrete advantages. First, functions of two variables arise naturally, sidestepping the algebraic difficulties of existing multivariate QSP approaches. Second, deciding membership across N disjoint intervals costs only O(d) oracle queries regardless of N — a logarithmic factor improvement over iterating standard QSP. Third, quantum amplitude estimation achieves the fundamental Heisenberg limit in a single non-adaptive measurement, eliminating the rounds of classical feedback that conventional methods require.► BibTeX data@article{Lu2026quantumsignal, doi = {10.22331/q-2026-03-27-2048}, url = {https://doi.org/10.22331/q-2026-03-27-2048}, title = {Quantum {S}ignal {P}rocessing and {Q}uantum {S}ingular {V}alue {T}ransformation on {$U(N)$}}, author = {Lu, Xi and Liu, Yuan and Lin, Hongwei}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2048}, month = mar, year = {2026} }► References [1] 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. https://doi.org/10.1103/PhysRevLett.118.010501 [2] András Gilyén, 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–204, 2019. doi:10.1145/3313276.3316366. https://doi.org/10.1145/3313276.3316366 [3] 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. https://doi.org/10.1103/PRXQuantum.2.040203 [4] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. doi:10.22331/q-2019-07-12-163. https://doi.org/10.22331/q-2019-07-12-163 [5] 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. https://doi.org/10.1103/PRXQuantum.5.020332 [6] 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–1950, 2017. doi:10.1137/16M1087072. https://doi.org/10.1137/16M1087072 [7] 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. https://doi.org/10.1103/PRXQuantum.3.040305 [8] 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. https://doi.org/10.1103/PhysRevLett.113.210501 [9] Patrick Rall and Bryce Fuller. Amplitude estimation from quantum signal processing. Quantum, 7:937, 2023. doi:10.22331/q-2023-03-02-937. https://doi.org/10.22331/q-2023-03-02-937 [10] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum-enhanced measurements: beating the standard quantum limit. Science, 306(5700):1330–1336, 2004. doi:10.1126/science.1104149. https://doi.org/10.1126/science.1104149 [11] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum metrology. Physical review letters, 96(1):010401, 2006. doi:10.1103/PhysRevLett.96.010401. https://doi.org/10.1103/PhysRevLett.96.010401 [12] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Advances in quantum metrology. Nature photonics, 5(4):222–229, 2011. doi:10.1038/nphoton.2011.35. https://doi.org/10.1038/nphoton.2011.35 [13] 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. https://doi.org/10.1098/rspa.2015.0301 [14] 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–925, 2016. doi:10.1145/2897518.2897585. https://doi.org/10.1145/2897518.2897585 [15] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 899–912, 2016. doi:10.1145/2897518.2897544. https://doi.org/10.1145/2897518.2897544 [16] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 325–338, 2018. doi:10.1145/3188745.3188802. https://doi.org/10.1145/3188745.3188802 [17] 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. arXiv:2203.07263 [18] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. Quantum tomography using state-preparation unitaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1265–1318. SIAM, 2023. doi:10.1137/1.9781611977554.ch47. https://doi.org/10.1137/1.9781611977554.ch47 [19] 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. https://doi.org/10.1103/PhysRevA.75.012328 [20] Ivan Kassal, Stephen P Jordan, Peter J Love, Masoud Mohseni, and Alán Aspuru-Guzik. Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences, 105(48):18681–18686, 2008. doi:10.1073/pnas.0808245105. https://doi.org/10.1073/pnas.0808245105 [21] 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. https://doi.org/10.1103/PhysRevResearch.4.033173 [22] William J Huggins, Kianna Wan, Jarrod McClean, Thomas E O’Brien, 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. https://doi.org/10.1103/PhysRevLett.129.240501 [23] 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. arXiv:2402.14791 [24] Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games. arXiv preprint arXiv:1904.03180, 2019. arXiv:1904.03180 [25] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):4213, 2014. doi:10.1038/ncomms5213. https://doi.org/10.1038/ncomms5213 [26] Nathan Wiebe, Ashish Kapoor, and Krysta M Svore. Quantum deep learning. arXiv preprint arXiv:1412.3489, 2014. arXiv:1412.3489 [27] 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–356, 2015. doi:10.26421/QIC15.3-4-7. https://doi.org/10.26421/QIC15.3-4-7 [28] 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. [29] 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. https://doi.org/10.22331/q-2023-06-02-1031 [30] 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–827, 2024. doi:10.1137/22M1484298. https://doi.org/10.1137/22M1484298 [31] 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. arXiv:2003.02831 [32] Lexing Ying. Stable factorization for phase factors of quantum signal processing. Quantum, 6:842, 2022. doi:10.22331/q-2022-10-20-842. https://doi.org/10.22331/q-2022-10-20-842 [33] 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. https://doi.org/10.1103/PhysRevA.103.042419 [34] Lorenzo Laneve. Quantum signal processing over su (n): exponential speed-up for polynomial transformations under shor-like assumptions. arXiv preprint arXiv:2311.03949, 2023. arXiv:2311.03949 [35] 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. arXiv:2406.02086 [36] Guang Hao Low and Yuan Su. Quantum eigenvalue processing. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1051–1062, 2024. doi:10.1109/FOCS61266.2024.00070. https://doi.org/10.1109/FOCS61266.2024.00070 [37] 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. https://doi.org/10.22331/q-2022-09-20-811 [38] Balázs Németh, Blanka Kövér, Boglárka Kulcsár, Roland Botond Miklósi, and András Gilyén. On variants of multivariate quantum signal processing and their characterizations. arXiv preprint arXiv:2312.09072, 2023. arXiv:2312.09072 [39] 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. https://doi.org/10.1038/s41534-023-00762-0 [40] 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. https://doi.org/10.1103/PhysRevApplied.23.034073 [41] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. arXiv preprint quant-ph/0005055, 2000. arXiv:quant-ph/0005055 [42] Danial Motlagh and Nathan Wiebe. Generalized quantum signal processing. PRX Quantum, 5(2):020368, 2024. doi:10.1103/PRXQuantum.5.020368. https://doi.org/10.1103/PRXQuantum.5.020368 [43] Andrew M Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. arXiv preprint arXiv:1202.5822, 2012. arXiv:1202.5822 [44] Norbert Wiener and Pesi Masani. The prediction theory of multivariate stochastic processes. Acta mathematica, 98(1):111–150, 1957. doi:10.1007/BF02404472. https://doi.org/10.1007/BF02404472 [45] 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–751, 2014. doi:10.1017/S0308210512001552. https://doi.org/10.1017/S0308210512001552 [46] 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. https://doi.org/10.22331/q-2024-07-30-1427 [47] Christopher M Dawson and Michael A Nielsen. The solovay-kitaev algorithm. arXiv preprint quant-ph/0505030, 2005. arXiv:quant-ph/0505030 [48] Tien Trung Pham, Rodney Van Meter, and Dominic Horsman. Optimization of the solovay-kitaev algorithm. Physical Review A—Atomic, Molecular, and Optical Physics, 87(5):052332, 2013. doi:10.1103/PhysRevA.87.052332. https://doi.org/10.1103/PhysRevA.87.052332 [49] Greg Kuperberg. Breaking the cubic barrier in the solovay-kitaev algorithm. arXiv preprint arXiv:2306.13158, 2023. arXiv:2306.13158 [50] 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. https://doi.org/10.22331/q-2025-02-20-1641 [51] Leopold Fejér. Über trigonometrische polynome. 1916. [52] Frigyes Riesz. über ein problem des herrn carathéodory. JOURNAL FUR DIE REINE UND ANGEWANDTE MATHEMATIK, 146:83–87, 1916. [53] Wim van Dam, G Mauro D’Ariano, 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. https://doi.org/10.1103/PhysRevLett.98.090501 [54] 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. https://doi.org/10.1088/1751-8113/40/28/S07 [55] Wojciech Górecki, Rafał Demkowicz-Dobrzański, Howard M Wiseman, and Dominic W Berry. $\pi$-corrected heisenberg limit. Physical review letters, 124(3):030501, 2020. doi:10.1103/PhysRevLett.124.030501. https://doi.org/10.1103/PhysRevLett.124.030501 [56] 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. https://doi.org/10.1103/4rf7-9tfxCited byCould not fetch Crossref cited-by data during last attempt 2026-03-27 12:01:27: Could not fetch cited-by data for 10.22331/q-2026-03-27-2048 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-27 12:01:27: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractQuantum 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 $U(N)$, which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on $U(2)$ 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$-interval decision achieving $O(d)$ query complexity with a $\log_2 N$ improvement over iterative $U(2)$-QSP requiring $O(d\log_2 N)$ queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.Popular summaryQuantum Signal Processing (QSP) is a powerful method for implementing polynomial transformations on quantum computers, underpinning many of the most efficient quantum algorithms known today — from Hamiltonian simulation to quantum search and amplitude estimation. In the standard framework, a circuit alternates a programmable single-qubit gate with a fixed unitary oracle, producing one independent polynomial function of that oracle as output. This single-qubit restriction, however, means only one transformation can be realized at a time. We generalize QSP by replacing the single-qubit ancilla with an N-dimensional one, using arbitrary N×N unitary rotations in place of single-qubit phase gates. A single circuit can then simultaneously realize an entire matrix of polynomial transformations. We fully characterize which set of polynomial matrices are achievable and give explicit recursive algorithms for constructing the required circuits. This richer framework unlocks three concrete advantages. First, functions of two variables arise naturally, sidestepping the algebraic difficulties of existing multivariate QSP approaches. Second, deciding membership across N disjoint intervals costs only O(d) oracle queries regardless of N — a logarithmic factor improvement over iterating standard QSP. Third, quantum amplitude estimation achieves the fundamental Heisenberg limit in a single non-adaptive measurement, eliminating the rounds of classical feedback that conventional methods require.► BibTeX data@article{Lu2026quantumsignal, doi = {10.22331/q-2026-03-27-2048}, url = {https://doi.org/10.22331/q-2026-03-27-2048}, title = {Quantum {S}ignal {P}rocessing and {Q}uantum {S}ingular {V}alue {T}ransformation on {$U(N)$}}, author = {Lu, Xi and Liu, Yuan and Lin, Hongwei}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2048}, month = mar, year = {2026} }► References [1] 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. https://doi.org/10.1103/PhysRevLett.118.010501 [2] András Gilyén, 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–204, 2019. doi:10.1145/3313276.3316366. https://doi.org/10.1145/3313276.3316366 [3] 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. https://doi.org/10.1103/PRXQuantum.2.040203 [4] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. doi:10.22331/q-2019-07-12-163. https://doi.org/10.22331/q-2019-07-12-163 [5] 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. https://doi.org/10.1103/PRXQuantum.5.020332 [6] 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–1950, 2017. doi:10.1137/16M1087072. https://doi.org/10.1137/16M1087072 [7] 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. https://doi.org/10.1103/PRXQuantum.3.040305 [8] 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. https://doi.org/10.1103/PhysRevLett.113.210501 [9] Patrick Rall and Bryce Fuller. Amplitude estimation from quantum signal processing. Quantum, 7:937, 2023. doi:10.22331/q-2023-03-02-937. https://doi.org/10.22331/q-2023-03-02-937 [10] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum-enhanced measurements: beating the standard quantum limit. Science, 306(5700):1330–1336, 2004. doi:10.1126/science.1104149. https://doi.org/10.1126/science.1104149 [11] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum metrology. Physical review letters, 96(1):010401, 2006. doi:10.1103/PhysRevLett.96.010401. https://doi.org/10.1103/PhysRevLett.96.010401 [12] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Advances in quantum metrology. Nature photonics, 5(4):222–229, 2011. doi:10.1038/nphoton.2011.35. https://doi.org/10.1038/nphoton.2011.35 [13] 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. https://doi.org/10.1098/rspa.2015.0301 [14] 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–925, 2016. doi:10.1145/2897518.2897585. https://doi.org/10.1145/2897518.2897585 [15] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 899–912, 2016. doi:10.1145/2897518.2897544. https://doi.org/10.1145/2897518.2897544 [16] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 325–338, 2018. doi:10.1145/3188745.3188802. https://doi.org/10.1145/3188745.3188802 [17] 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. arXiv:2203.07263 [18] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. Quantum tomography using state-preparation unitaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1265–1318. SIAM, 2023. doi:10.1137/1.9781611977554.ch47. https://doi.org/10.1137/1.9781611977554.ch47 [19] 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. https://doi.org/10.1103/PhysRevA.75.012328 [20] Ivan Kassal, Stephen P Jordan, Peter J Love, Masoud Mohseni, and Alán Aspuru-Guzik. Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences, 105(48):18681–18686, 2008. doi:10.1073/pnas.0808245105. https://doi.org/10.1073/pnas.0808245105 [21] 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. https://doi.org/10.1103/PhysRevResearch.4.033173 [22] William J Huggins, Kianna Wan, Jarrod McClean, Thomas E O’Brien, 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. https://doi.org/10.1103/PhysRevLett.129.240501 [23] 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. arXiv:2402.14791 [24] Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games. arXiv preprint arXiv:1904.03180, 2019. arXiv:1904.03180 [25] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):4213, 2014. doi:10.1038/ncomms5213. https://doi.org/10.1038/ncomms5213 [26] Nathan Wiebe, Ashish Kapoor, and Krysta M Svore. Quantum deep learning. arXiv preprint arXiv:1412.3489, 2014. arXiv:1412.3489 [27] 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–356, 2015. doi:10.26421/QIC15.3-4-7. https://doi.org/10.26421/QIC15.3-4-7 [28] 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. [29] 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. https://doi.org/10.22331/q-2023-06-02-1031 [30] 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–827, 2024. doi:10.1137/22M1484298. https://doi.org/10.1137/22M1484298 [31] 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. arXiv:2003.02831 [32] Lexing Ying. Stable factorization for phase factors of quantum signal processing. Quantum, 6:842, 2022. doi:10.22331/q-2022-10-20-842. https://doi.org/10.22331/q-2022-10-20-842 [33] 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. https://doi.org/10.1103/PhysRevA.103.042419 [34] Lorenzo Laneve. Quantum signal processing over su (n): exponential speed-up for polynomial transformations under shor-like assumptions. arXiv preprint arXiv:2311.03949, 2023. arXiv:2311.03949 [35] 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. arXiv:2406.02086 [36] Guang Hao Low and Yuan Su. Quantum eigenvalue processing. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1051–1062, 2024. doi:10.1109/FOCS61266.2024.00070. https://doi.org/10.1109/FOCS61266.2024.00070 [37] 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. https://doi.org/10.22331/q-2022-09-20-811 [38] Balázs Németh, Blanka Kövér, Boglárka Kulcsár, Roland Botond Miklósi, and András Gilyén. On variants of multivariate quantum signal processing and their characterizations. arXiv preprint arXiv:2312.09072, 2023. arXiv:2312.09072 [39] 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. https://doi.org/10.1038/s41534-023-00762-0 [40] 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. https://doi.org/10.1103/PhysRevApplied.23.034073 [41] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. arXiv preprint quant-ph/0005055, 2000. arXiv:quant-ph/0005055 [42] Danial Motlagh and Nathan Wiebe. Generalized quantum signal processing. PRX Quantum, 5(2):020368, 2024. doi:10.1103/PRXQuantum.5.020368. https://doi.org/10.1103/PRXQuantum.5.020368 [43] Andrew M Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. arXiv preprint arXiv:1202.5822, 2012. arXiv:1202.5822 [44] Norbert Wiener and Pesi Masani. The prediction theory of multivariate stochastic processes. Acta mathematica, 98(1):111–150, 1957. doi:10.1007/BF02404472. https://doi.org/10.1007/BF02404472 [45] 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–751, 2014. doi:10.1017/S0308210512001552. https://doi.org/10.1017/S0308210512001552 [46] 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. https://doi.org/10.22331/q-2024-07-30-1427 [47] Christopher M Dawson and Michael A Nielsen. The solovay-kitaev algorithm. arXiv preprint quant-ph/0505030, 2005. arXiv:quant-ph/0505030 [48] Tien Trung Pham, Rodney Van Meter, and Dominic Horsman. Optimization of the solovay-kitaev algorithm. Physical Review A—Atomic, Molecular, and Optical Physics, 87(5):052332, 2013. doi:10.1103/PhysRevA.87.052332. https://doi.org/10.1103/PhysRevA.87.052332 [49] Greg Kuperberg. Breaking the cubic barrier in the solovay-kitaev algorithm. arXiv preprint arXiv:2306.13158, 2023. arXiv:2306.13158 [50] 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. https://doi.org/10.22331/q-2025-02-20-1641 [51] Leopold Fejér. Über trigonometrische polynome. 1916. [52] Frigyes Riesz. über ein problem des herrn carathéodory. JOURNAL FUR DIE REINE UND ANGEWANDTE MATHEMATIK, 146:83–87, 1916. [53] Wim van Dam, G Mauro D’Ariano, 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. https://doi.org/10.1103/PhysRevLett.98.090501 [54] 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. https://doi.org/10.1088/1751-8113/40/28/S07 [55] Wojciech Górecki, Rafał Demkowicz-Dobrzański, Howard M Wiseman, and Dominic W Berry. $\pi$-corrected heisenberg limit. Physical review letters, 124(3):030501, 2020. doi:10.1103/PhysRevLett.124.030501. https://doi.org/10.1103/PhysRevLett.124.030501 [56] 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. https://doi.org/10.1103/4rf7-9tfxCited byCould not fetch Crossref cited-by data during last attempt 2026-03-27 12:01:27: Could not fetch cited-by data for 10.22331/q-2026-03-27-2048 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-27 12:01:27: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.