Polynomial time constructive decision algorithm for multivariable quantum signal processing
Summarize this article with:
AbstractQuantum signal processing (QSP) and quantum singular value transformation (QSVT) have provided a unified framework for understanding many quantum algorithms, including factorization, matrix inversion, and Hamiltonian simulation. As a multivariable version of QSP, multivariable quantum signal processing (M-QSP) is proposed. M-QSP interleaves signal operators corresponding to each variable with signal processing operators, which provides an efficient means to perform multivariable polynomial transformations. However, the necessary and sufficient condition for what types of polynomials can be constructed by M-QSP is unknown. In this paper, we propose a classical algorithm to determine whether a given pair of multivariable Laurent polynomials can be implemented by M-QSP, which returns True or False. As one of the most important properties of this algorithm, its returning True is the necessary and sufficient condition. The proposed classical algorithm runs in polynomial time in the number of variables and signal operators. Our algorithm also provides a constructive method to select the necessary parameters for implementing M-QSP. These findings offer valuable insights for identifying practical applications of M-QSP.Featured image: An overview of how M-QSP-CDA, the proposed algorithm, works.► BibTeX data@article{Ito2026polynomialtime, doi = {10.22331/q-2026-05-12-2102}, url = {https://doi.org/10.22331/q-2026-05-12-2102}, title = {Polynomial time constructive decision algorithm for multivariable quantum signal processing}, author = {Ito, Yuki and Mori, Hitomi and Sakamoto, Kazuki and Fujii, Keisuke}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2102}, month = may, year = {2026} }► References [1] P.W. Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th Annual Symposium on Foundations of Computer Science. Pages 124–134. (1994). https://doi.org/10.1109/SFCS.1994.365700 [2] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum Algorithm for Linear Systems of Equations''.
Physical Review Letters 103, 150502 (2009). https://doi.org/10.1103/PhysRevLett.103.150502 [3] Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. ``Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem''. PRX Quantum 3, 040303 (2022). https://doi.org/10.1103/PRXQuantum.3.040303 [4] Richard P Feynman. ``Simulating physics with computers''. International Journal of Theoretical Physics 21, 467–488 (1982). https://doi.org/10.1007/BF02650179 [5] Seth Lloyd. ``Universal Quantum Simulators''. Science 273, 1073–1078 (1996). https://doi.org/10.1126/science.273.5278.1073 [6] Guang Hao Low and Isaac L. Chuang. ``Optimal Hamiltonian Simulation by Quantum Signal Processing''.
Physical Review Letters 118, 010501 (2017). https://doi.org/10.1103/PhysRevLett.118.010501 [7] 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). https://doi.org/10.1145/3313276.3316366 [8] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. ``Methodology of Resonant Equiangular Composite Quantum Gates''. Physical Review X 6, 041067 (2016). https://doi.org/10.1103/PhysRevX.6.041067 [9] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``Grand Unification of Quantum Algorithms''. PRX Quantum 2, 040203 (2021). https://doi.org/10.1103/PRXQuantum.2.040203 [10] Patrick Rall. ``Quantum algorithms for estimating physical quantities using block encodings''. Physical Review A 102, 022408 (2020). https://doi.org/10.1103/PhysRevA.102.022408 [11] Lin Lin and Yu Tong. ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems''. Quantum 4, 361 (2020). https://doi.org/10.22331/q-2020-11-11-361 [12] 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, 040305 (2022). https://doi.org/10.1103/PRXQuantum.3.040305 [13] Patrick Rall. ``Faster coherent quantum algorithms for phase, energy, and amplitude estimation''. Quantum 5, 566 (2021). https://doi.org/10.22331/q-2021-10-19-566 [14] András Gilyén and Alexander Poremba. ``Improved Quantum Algorithms for Fidelity Estimation'' (2022). arXiv:2203.15993. arXiv:2203.15993 [15] Sam McArdle, András Gilyén, and Mario Berta. ``Quantum state preparation without coherent arithmetic'' (2022). arXiv:2210.14892. arXiv:2210.14892 [16] Guang Hao Low and Isaac L. Chuang. ``Hamiltonian Simulation by Qubitization''. Quantum 3, 163 (2019). https://doi.org/10.22331/q-2019-07-12-163 [17] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation''.
In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14. Dagstuhl, Germany (2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2019.33 [18] Zane M. Rossi and Isaac L. Chuang. ``Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle''. Quantum 6, 811 (2022). https://doi.org/10.22331/q-2022-09-20-811 [19] Hitomi Mori, Kosuke Mitarai, and Keisuke Fujii. ``Efficient state preparation for multivariate Monte Carlo simulation'' (2024). arXiv:2409.07336. arXiv:2409.07336 [20] Niladri Gomes, Hokiat Lim, and Nathan Wiebe. ``Multivariable QSP and Bosonic Quantum Simulation using Iterated Quantum Signal Processing'' (2024). arXiv:2408.03254. arXiv:2408.03254 [21] Hitomi Mori, Kaoru Mizuta, and Keisuke Fujii. ``Comment on "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle"''. Quantum 8, 1512 (2024). https://doi.org/10.22331/q-2024-10-29-1512 [22] 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'' (2023). arXiv:2312.09072. arXiv:2312.09072 [23] Lorenzo Laneve and Stefan Wolf. ``On multivariate polynomials achievable with quantum signal processing''. Quantum 9, 1641 (2025). https://doi.org/10.22331/q-2025-02-20-1641 [24] Jeongwan Haah. ``Product Decomposition of Periodic Functions in Quantum Signal Processing''. Quantum 3, 190 (2019). https://doi.org/10.22331/q-2019-10-07-190 [25] Zane M. Rossi, Jack L. Ceroni, and Isaac L. Chuang. ``Modular quantum signal processing in many variables''. Quantum 9, 1776 (2025). https://doi.org/10.22331/q-2025-06-18-1776 [26] Michel Alexis, Gevorg Mnatsakanyan, and Christoph Thiele. ``Quantum signal processing and nonlinear Fourier analysis''. Revista Matemática Complutense 37, 655–694 (2024). https://doi.org/10.1007/s13163-024-00494-5 [27] Michel Alexis, Lin Lin, Gevorg Mnatsakanyan, Christoph Thiele, and Jiasu Wang. ``Infinite quantum signal processing for arbitrary Szegő functions''. Communications on Pure and Applied Mathematics 79, 123–174 (2026). https://doi.org/10.1002/cpa.70007 [28] Hongkang Ni and Lexing Ying. ``Fast Phase Factor Finding for Quantum Signal Processing'' (2024). arXiv:2410.06409. arXiv:2410.06409 [29] Lorenzo Laneve. ``Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent'' (2025). arXiv:2503.03026. arXiv:2503.03026 [30] Hongkang Ni, Rahul Sarkar, Lexing Ying, and Lin Lin. ``Inverse nonlinear fast Fourier transform on SU(2) with applications to quantum signal processing'' (2025). arXiv:2505.12615. arXiv:2505.12615 [31] Lorenzo Laneve. ``An adversary bound for quantum signal processing''. Quantum 10, 2025 (2026). https://doi.org/10.22331/q-2026-03-13-2025 [32] Bjorn K. Berntson and Christoph Sünderhauf. ``Complementary Polynomials in Quantum Signal Processing''. Communications in Mathematical Physics 406, 161 (2025). https://doi.org/10.1007/s00220-025-05302-9 [33] Danial Motlagh and Nathan Wiebe. ``Generalized Quantum Signal Processing''. PRX Quantum 5, 020368 (2024). https://doi.org/10.1103/PRXQuantum.5.020368Cited by[1] Lorenzo Laneve, "Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent", arXiv:2503.03026, (2025). [2] Hitomi Mori, Kaoru Mizuta, and Keisuke Fujii, "Comment on "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle"", Quantum 8, 1512 (2024). [3] Teerawat Chalermpusitarak, Kai Schwennicke, Ivan Kassal, and Ting Rei Tan, "Programmable generation of arbitrary continuous-variable anharmonicities and nonlinear couplings", arXiv:2511.22286, (2025). [4] Lorenzo Laneve, "An adversary bound for quantum signal processing", Quantum 10, 2025 (2026). [5] Jungsoo Hong, Seong Ho Kim, Seung Kyu Min, and Joonsuk Huh, "Oscillator-qubit generalized quantum signal processing for vibronic models: a case study of uracil cation", arXiv:2510.10495, (2025). The above citations are from SAO/NASA ADS (last updated successfully 2026-05-12 13:54:34). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-05-12 13:54:33: Could not fetch cited-by data for 10.22331/q-2026-05-12-2102 from Crossref. This is normal if the DOI was registered recently.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 (QSP) and quantum singular value transformation (QSVT) have provided a unified framework for understanding many quantum algorithms, including factorization, matrix inversion, and Hamiltonian simulation. As a multivariable version of QSP, multivariable quantum signal processing (M-QSP) is proposed. M-QSP interleaves signal operators corresponding to each variable with signal processing operators, which provides an efficient means to perform multivariable polynomial transformations. However, the necessary and sufficient condition for what types of polynomials can be constructed by M-QSP is unknown. In this paper, we propose a classical algorithm to determine whether a given pair of multivariable Laurent polynomials can be implemented by M-QSP, which returns True or False. As one of the most important properties of this algorithm, its returning True is the necessary and sufficient condition. The proposed classical algorithm runs in polynomial time in the number of variables and signal operators. Our algorithm also provides a constructive method to select the necessary parameters for implementing M-QSP. These findings offer valuable insights for identifying practical applications of M-QSP.Featured image: An overview of how M-QSP-CDA, the proposed algorithm, works.► BibTeX data@article{Ito2026polynomialtime, doi = {10.22331/q-2026-05-12-2102}, url = {https://doi.org/10.22331/q-2026-05-12-2102}, title = {Polynomial time constructive decision algorithm for multivariable quantum signal processing}, author = {Ito, Yuki and Mori, Hitomi and Sakamoto, Kazuki and Fujii, Keisuke}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2102}, month = may, year = {2026} }► References [1] P.W. Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th Annual Symposium on Foundations of Computer Science. Pages 124–134. (1994). https://doi.org/10.1109/SFCS.1994.365700 [2] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum Algorithm for Linear Systems of Equations''.
Physical Review Letters 103, 150502 (2009). https://doi.org/10.1103/PhysRevLett.103.150502 [3] Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. ``Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem''. PRX Quantum 3, 040303 (2022). https://doi.org/10.1103/PRXQuantum.3.040303 [4] Richard P Feynman. ``Simulating physics with computers''. International Journal of Theoretical Physics 21, 467–488 (1982). https://doi.org/10.1007/BF02650179 [5] Seth Lloyd. ``Universal Quantum Simulators''. Science 273, 1073–1078 (1996). https://doi.org/10.1126/science.273.5278.1073 [6] Guang Hao Low and Isaac L. Chuang. ``Optimal Hamiltonian Simulation by Quantum Signal Processing''.
Physical Review Letters 118, 010501 (2017). https://doi.org/10.1103/PhysRevLett.118.010501 [7] 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). https://doi.org/10.1145/3313276.3316366 [8] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. ``Methodology of Resonant Equiangular Composite Quantum Gates''. Physical Review X 6, 041067 (2016). https://doi.org/10.1103/PhysRevX.6.041067 [9] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``Grand Unification of Quantum Algorithms''. PRX Quantum 2, 040203 (2021). https://doi.org/10.1103/PRXQuantum.2.040203 [10] Patrick Rall. ``Quantum algorithms for estimating physical quantities using block encodings''. Physical Review A 102, 022408 (2020). https://doi.org/10.1103/PhysRevA.102.022408 [11] Lin Lin and Yu Tong. ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems''. Quantum 4, 361 (2020). https://doi.org/10.22331/q-2020-11-11-361 [12] 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, 040305 (2022). https://doi.org/10.1103/PRXQuantum.3.040305 [13] Patrick Rall. ``Faster coherent quantum algorithms for phase, energy, and amplitude estimation''. Quantum 5, 566 (2021). https://doi.org/10.22331/q-2021-10-19-566 [14] András Gilyén and Alexander Poremba. ``Improved Quantum Algorithms for Fidelity Estimation'' (2022). arXiv:2203.15993. arXiv:2203.15993 [15] Sam McArdle, András Gilyén, and Mario Berta. ``Quantum state preparation without coherent arithmetic'' (2022). arXiv:2210.14892. arXiv:2210.14892 [16] Guang Hao Low and Isaac L. Chuang. ``Hamiltonian Simulation by Qubitization''. Quantum 3, 163 (2019). https://doi.org/10.22331/q-2019-07-12-163 [17] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation''.
In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14. Dagstuhl, Germany (2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2019.33 [18] Zane M. Rossi and Isaac L. Chuang. ``Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle''. Quantum 6, 811 (2022). https://doi.org/10.22331/q-2022-09-20-811 [19] Hitomi Mori, Kosuke Mitarai, and Keisuke Fujii. ``Efficient state preparation for multivariate Monte Carlo simulation'' (2024). arXiv:2409.07336. arXiv:2409.07336 [20] Niladri Gomes, Hokiat Lim, and Nathan Wiebe. ``Multivariable QSP and Bosonic Quantum Simulation using Iterated Quantum Signal Processing'' (2024). arXiv:2408.03254. arXiv:2408.03254 [21] Hitomi Mori, Kaoru Mizuta, and Keisuke Fujii. ``Comment on "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle"''. Quantum 8, 1512 (2024). https://doi.org/10.22331/q-2024-10-29-1512 [22] 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'' (2023). arXiv:2312.09072. arXiv:2312.09072 [23] Lorenzo Laneve and Stefan Wolf. ``On multivariate polynomials achievable with quantum signal processing''. Quantum 9, 1641 (2025). https://doi.org/10.22331/q-2025-02-20-1641 [24] Jeongwan Haah. ``Product Decomposition of Periodic Functions in Quantum Signal Processing''. Quantum 3, 190 (2019). https://doi.org/10.22331/q-2019-10-07-190 [25] Zane M. Rossi, Jack L. Ceroni, and Isaac L. Chuang. ``Modular quantum signal processing in many variables''. Quantum 9, 1776 (2025). https://doi.org/10.22331/q-2025-06-18-1776 [26] Michel Alexis, Gevorg Mnatsakanyan, and Christoph Thiele. ``Quantum signal processing and nonlinear Fourier analysis''. Revista Matemática Complutense 37, 655–694 (2024). https://doi.org/10.1007/s13163-024-00494-5 [27] Michel Alexis, Lin Lin, Gevorg Mnatsakanyan, Christoph Thiele, and Jiasu Wang. ``Infinite quantum signal processing for arbitrary Szegő functions''. Communications on Pure and Applied Mathematics 79, 123–174 (2026). https://doi.org/10.1002/cpa.70007 [28] Hongkang Ni and Lexing Ying. ``Fast Phase Factor Finding for Quantum Signal Processing'' (2024). arXiv:2410.06409. arXiv:2410.06409 [29] Lorenzo Laneve. ``Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent'' (2025). arXiv:2503.03026. arXiv:2503.03026 [30] Hongkang Ni, Rahul Sarkar, Lexing Ying, and Lin Lin. ``Inverse nonlinear fast Fourier transform on SU(2) with applications to quantum signal processing'' (2025). arXiv:2505.12615. arXiv:2505.12615 [31] Lorenzo Laneve. ``An adversary bound for quantum signal processing''. Quantum 10, 2025 (2026). https://doi.org/10.22331/q-2026-03-13-2025 [32] Bjorn K. Berntson and Christoph Sünderhauf. ``Complementary Polynomials in Quantum Signal Processing''. Communications in Mathematical Physics 406, 161 (2025). https://doi.org/10.1007/s00220-025-05302-9 [33] Danial Motlagh and Nathan Wiebe. ``Generalized Quantum Signal Processing''. PRX Quantum 5, 020368 (2024). https://doi.org/10.1103/PRXQuantum.5.020368Cited by[1] Lorenzo Laneve, "Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent", arXiv:2503.03026, (2025). [2] Hitomi Mori, Kaoru Mizuta, and Keisuke Fujii, "Comment on "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle"", Quantum 8, 1512 (2024). [3] Teerawat Chalermpusitarak, Kai Schwennicke, Ivan Kassal, and Ting Rei Tan, "Programmable generation of arbitrary continuous-variable anharmonicities and nonlinear couplings", arXiv:2511.22286, (2025). [4] Lorenzo Laneve, "An adversary bound for quantum signal processing", Quantum 10, 2025 (2026). [5] Jungsoo Hong, Seong Ho Kim, Seung Kyu Min, and Joonsuk Huh, "Oscillator-qubit generalized quantum signal processing for vibronic models: a case study of uracil cation", arXiv:2510.10495, (2025). The above citations are from SAO/NASA ADS (last updated successfully 2026-05-12 13:54:34). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-05-12 13:54:33: Could not fetch cited-by data for 10.22331/q-2026-05-12-2102 from Crossref. This is normal if the DOI was registered recently.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.