On multivariate polynomials achievable with quantum signal processing

Lorenzo Laneve; Stefan Wolf

doi:10.22331/q-2025-02-20-1641

On multivariate polynomials achievable with quantum signal processing

Faculty of Informatics — Università della Svizzera Italiana, 6900 Lugano, Switzerland

Published:	2025-02-20, volume 9, page 1641
Editor:	Aleksandrs Belovs
Eprint:	arXiv:2407.20823v2
Doi:	https://doi.org/10.22331/q-2025-02-20-1641
Citation:	Quantum 9, 1641 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Quantum signal processing (QSP) is a framework which was proven to unify and simplify a large number of known quantum algorithms, as well as discovering new ones. QSP allows one to transform a signal embedded in a given unitary using polynomials. Characterizing which polynomials can be achieved with QSP protocols is an important part of the power of this technique, and while such a characterization is well-understood in the case of univariate signals, it is unclear which multivariate polynomials can be constructed when the signal is a vector, rather than a scalar. This work uses a slightly different formalism than what is found in the literature, and uses it to find simpler necessary conditions for decomposability, as well as a sufficient condition – the first, to the best of our knowledge, proven for a (generally inhomogeneous) multivariate polynomial in the context of quantum signal processing.

Featured image: Evolution of a bi-variate polynomial state $|\gamma(a, b)\rangle = \sum_{k, h} |\gamma_{k, h}\rangle a^k b^h$ through a 3D QSP protocol $A_2 \tilde{W} A_1 \tilde{W} A_0 |0\rangle$. Since the $A_k$'s are unitaries, the coefficients $|\gamma_{k, h}\rangle$ have to satisfy certain orthogonality conditions, and this allows us to deduce sufficient or necessary conditions for a given polynomial state to have such a decomposition.

► BibTeX data

@article{Laneve2025multivariate,
  doi = {10.22331/q-2025-02-20-1641},
  url = {https://doi.org/10.22331/q-2025-02-20-1641},
  title = {On multivariate polynomials achievable with quantum signal processing},
  author = {Laneve, Lorenzo and Wolf, Stefan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1641},
  month = feb,
  year = {2025}
}

► References

[1] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. ``Quantum Amplitude Amplification and Estimation''. Quantum Computation and Information 305, 53–74 (2002).
https://doi.org/10.1090/conm/305/05215

[2] Lov K. Grover. ``A Fast Quantum Mechanical Algorithm for Database Search''. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. Pages 212–219. Association for Computing Machinery (1996).
https://doi.org/10.1145/237814.237866

[3] Andrew M Childs and Nathan Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations''. Quantum Information and Computation 12, 901–924 (2012).
https://doi.org/10.26421/QIC12.11-12-1

[4] 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

[5] Mario Szegedy. ``Quantum speed-up of Markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004).
https://doi.org/10.1109/FOCS.2004.53

[6] A Ambainis. ``Quantum walk algorithm for element distinctness''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 22–31. (2004).
https://doi.org/10.1109/FOCS.2004.54

[7] Simon Apers, András Gilyén, and Stacey Jeffery. ``A Unified Framework of Quantum Walk Search''. In Leibniz International Proceedings in Informatics (LIPIcs). Volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021).
https://doi.org/10.4230/LIPIcs.STACS.2021.6

[8] Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita. ``Span programs and quantum time complexity''. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2020).
https://doi.org/10.4230/LIPIcs.MFCS.2020.26

[9] Andrew M Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang. ``Quantum divide and conquer'' (2022). arXiv:2210.06419.
arXiv:2210.06419

[10] Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu. ``Taming Quantum Time Complexity''. Quantum 8, 1444 (2024).
https://doi.org/10.22331/q-2024-08-23-1444

[11] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. ``Methodology of Resonant Equiangular Composite Quantum Gates''. Physical Review X 6, 41067 (2016).
https://doi.org/10.1103/PhysRevX.6.041067

[12] Guang Hao Low. ``Quantum signal processing by single-qubit dynamics''. Thesis. Massachusetts Institute of Technology. (2017). url: https://dspace.mit.edu/handle/1721.1/115025.
https://dspace.mit.edu/handle/1721.1/115025

[13] 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. ACM (2019).
https://doi.org/10.1145/3313276.3316366

[14] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``A Grand Unification of Quantum Algorithms''. PRX Quantum 2, 40203 (2021).
https://doi.org/10.1103/PRXQuantum.2.040203

[15] Camille Jordan. ``Essai sur la géométrie à n dimensions''. Bulletin de la Société mathématique de France 2, 103–174 (1875).
https://doi.org/10.24033/bsmf.90

[16] 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

[17] Guang Hao Low and Isaac L Chuang. ``Hamiltonian Simulation by Uniform Spectral Amplification'' (2017). arXiv:1707.05391.
arXiv:1707.05391

[18] Seth Lloyd, Bobak T. Kiani, David R. M. Arvidsson-Shukur, Samuel Bosch, Giacomo De Palma, William M. Kaminsky, Zi-Wen Liu, and Milad Marvian. ``Hamiltonian singular value transformation and inverse block encoding'' (2021). arXiv:2104.01410.
arXiv:2104.01410

[19] 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

[20] John M. Martyn, Yuan Liu, Zachary E. Chin, and Isaac L. Chuang. ``Efficient fully-coherent quantum signal processing algorithms for real-time dynamics simulation''. The Journal of Chemical Physics 158, 024106 (2023).
https://doi.org/10.1063/5.0124385

[21] Sam McArdle, András Gilyén, and Mario Berta. ``Quantum state preparation without coherent arithmetic'' (2022). arXiv:2210.14892.
arXiv:2210.14892

[22] Lorenzo Laneve. ``Robust black-box quantum-state preparation via quantum signal processing'' (2023). arXiv:2305.04705.
arXiv:2305.04705

[23] 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

[24] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy. ``Finding Angles for Quantum Signal Processing with Machine Precision'' (2020). arXiv:2003.02831.
arXiv:2003.02831

[25] Yulong Dong, Xiang Meng, K Birgitta Whaley, and Lin Lin. ``Efficient phase-factor evaluation in quantum signal processing''. Physical Review A 103, 42419 (2021).
https://doi.org/10.1103/PhysRevA.103.042419

[26] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang. ``Infinite quantum signal processing''. Quantum 8, 1558 (2024).
https://doi.org/10.22331/q-2024-12-10-1558

[27] Jiasu Wang, Yulong Dong, and Lin Lin. ``On the energy landscape of symmetric quantum signal processing''. Quantum 6, 850 (2022).
https://doi.org/10.22331/q-2022-11-03-850

[28] Kaoru Mizuta and Keisuke Fujii. ``Recursive quantum eigenvalue and singular-value transformation: Analytic construction of matrix sign function by Newton iteration''. Physical Review Research 6, L012007 (2024).
https://doi.org/10.1103/PhysRevResearch.6.L012007

[29] Zane M. Rossi and Isaac L. Chuang. ``Semantic embedding for quantum algorithms''. Journal of Mathematical Physics 64, 122202 (2023).
https://doi.org/10.1063/5.0160910

[30] Zane M. Rossi, Jack L. Ceroni, and Isaac L. Chuang. ``Modular quantum signal processing in many variables'' (2023). arXiv:2309.16665.
arXiv:2309.16665

[31] Zane M Rossi, Victor M Bastidas, William J Munro, and Isaac L Chuang. ``Quantum signal processing with continuous variables'' (2023). arXiv:2304.14383.
arXiv:2304.14383

[32] Danial Motlagh and Nathan Wiebe. ``Generalized Quantum Signal Processing''. PRX Quantum 5, 020368 (2024).
https://doi.org/10.1103/PRXQuantum.5.020368

[33] Lorenzo Laneve. ``Quantum signal processing over SU(N)'' (2024). arXiv:2311.03949.
arXiv:2311.03949

[34] V. M. Bastidas and K. J. Joven. ``Complexification of Quantum Signal Processing and its Ramifications'' (2024). arXiv:2407.04780.
arXiv:2407.04780

[35] 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

[36] 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

[37] Yonah Borns-Weil, Tahsin Saffat, and Zachary Stier. ``A Quantum Algorithm for Functions of Multiple Commuting Hermitian Matrices'' (2023). arXiv:2302.11139.
arXiv:2302.11139

[38] 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

[39] Ewin Tang and Kevin Tian. ``A CS guide to the quantum singular value transformation'' (2023). arXiv:2302.14324.
arXiv:2302.14324

[40] Elias M. Stein and Rami Shakarchi. ``Fourier Analysis: An Introduction''. Princeton University Press. (2011). url: https://press.princeton.edu/books/hardcover/9780691113845/fourier-analysis.
https://press.princeton.edu/books/hardcover/9780691113845/fourier-analysis

[41] Martin Roelfs. ``Geometric Invariant Decomposition of SU(3)''. Advances in Applied Clifford Algebras 33, 5 (2022).
https://doi.org/10.1007/s00006-022-01252-w

[42] Martin Idel and Michael M. Wolf. ``Sinkhorn normal form for unitary matrices''. Linear Algebra and its Applications 471, 76–84 (2015).
https://doi.org/10.1016/j.laa.2014.12.031

[43] Dominic W. Berry, Danial Motlagh, Giacomo Pantaleoni, and Nathan Wiebe. ``Doubling the efficiency of Hamiltonian simulation via generalized quantum signal processing''. Physical Review A 110, 012612 (2024).
https://doi.org/10.1103/PhysRevA.110.012612

[44] Jeffrey S. Geronimo and Hugo J. Woerdeman. ``Positive extensions, Fejér-Riesz factorization and autoregressive filters in two variables''. Annals of Mathematics 160, 839–906 (2004).
https://doi.org/10.4007/ANNALS.2004.160.839

[45] Abdulmtalb Hussen and Abdelbaset Zeyani. ``Fejer-Riesz Theorem and Its Generalization''. International Journal of Scientific and Research Publications (IJSRP) 11, 286–292 (2021).
https://doi.org/10.29322/IJSRP.11.06.2021.p11437

Cited by

[1] Xi Lu, Yuan Liu, and Hongwei Lin, "Quantum Signal Processing and Quantum Singular Value Transformation on U(N)", Quantum 10, 2048 (2026).

[2] Christopher F. Kane, Siddharth Hariprakash, Neel S. Modi, Michael Kreshchuk, and Christian W Bauer, "Block encoding bosons by signal processing", Quantum 9, 1747 (2025).

[3] Aishwarya Majumdar, Bojko N. Bakalov, Dror Baron, and Yuan Liu, ICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 1 (2025) ISBN:979-8-3503-6874-1.

[4] Kidus Tessma, Hrvoje Kukina, and Jakub Szefer, 2025 IEEE 43rd International Conference on Computer Design (ICCD) 342 (2025) ISBN:979-8-3315-0346-8.

[5] Jungsoo Hong, Seong Ho Kim, Seung Kyu Min, and Joonsuk Huh, "Oscillator–qubit generalized quantum signal processing: a case study of the uracil cation vibronic model", Chemical Science 17 24, 11911 (2026).

[6] Yuki Ito, Hitomi Mori, Kazuki Sakamoto, and Keisuke Fujii, "Polynomial time constructive decision algorithm for multivariable quantum signal processing", Quantum 10, 2102 (2026).

[7] Lorenzo Laneve, "An adversary bound for quantum signal processing", Quantum 10, 2025 (2026).

[8] 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).

[9] Yuki Ito, Hitomi Mori, Kazuki Sakamoto, and Keisuke Fujii, "Polynomial time constructive decision algorithm for multivariable quantum signal processing", arXiv:2410.02332, (2024).

[10] S. E. Skelton, "The Hitchhiker's Guide to QSP pre-processing", arXiv:2501.05977, (2025).

[11] Pierre-Antoine Bernard and Nathan Wiebe, "Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory", arXiv:2605.05321, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 03:08:30) and SAO/NASA ADS (last updated successfully 2026-08-09 03:08:31). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.