Stable factorization for phase factors of quantum signal processing

Lexing Ying

doi:10.22331/q-2022-10-20-842

Stable factorization for phase factors of quantum signal processing

Department of Mathematics, Stanford University, Stanford, CA 94305, USA

Published:	2022-10-20, volume 6, page 842
Eprint:	arXiv:2202.02671v3
Doi:	https://doi.org/10.22331/q-2022-10-20-842
Citation:	Quantum 6, 842 (2022).

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

Abstract

This paper proposes a new factorization algorithm for computing the phase factors of quantum signal processing. The proposed algorithm avoids root finding of high degree polynomials by using a key step of Prony's method and is numerically stable in the double precision arithmetics. Experimental results are reported for Hamiltonian simulation, eigenstate filtering, matrix inversion, and Fermi-Dirac operator.

► BibTeX data

@article{Ying2022stablefactorization,
  doi = {10.22331/q-2022-10-20-842},
  url = {https://doi.org/10.22331/q-2022-10-20-842},
  title = {Stable factorization for phase factors of quantum signal processing},
  author = {Ying, Lexing},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {842},
  month = oct,
  year = {2022}
}

► References

[1] R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy. Finding angles for quantum signal processing with machine precision. arXiv preprint arXiv:2003.02831, 2020. doi:10.48550/ARXIV.2003.02831.
https://doi.org/10.48550/ARXIV.2003.02831
arXiv:2003.02831

[2] A. M. Childs, R. Kothari, and R. 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

[3] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018. doi:10.1073/pnas.1801723115.
https://doi.org/10.1073/pnas.1801723115

[4] Y. Dong, X. Meng, K. B. Whaley, and L. 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

[5] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. arXiv preprint arXiv:1806.01838, 2018. doi:10.48550/arXiv.1806.01838.
https://doi.org/10.48550/arXiv.1806.01838
arXiv:1806.01838

[6] A. Gilyén, Y. Su, G. H. Low, and N. 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

[7] J. Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3:190, 2019. doi:10.22331/q-2019-10-07-190.
https://doi.org/10.22331/q-2019-10-07-190

[8] L. Lin. Lecture notes on quantum algorithms for scientific computation. arXiv preprint arXiv:2201.08309, 2022. doi:10.48550/arXiv.2201.08309.
https://doi.org/10.48550/arXiv.2201.08309
arXiv:2201.08309

[9] G. H. Low and I. 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

[10] J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. 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

[11] D. Potts and M. Tasche. Parameter estimation for nonincreasing exponential sums by Prony-like methods. Linear Algebra and its Applications, 439(4):1024–1039, 2013. doi:10.1016/j.laa.2012.10.036.
https://doi.org/10.1016/j.laa.2012.10.036

[12] R. Prony. Essai experimental et analytique. J. Ecole Polytechnique, pages 24–76, 1795.

[13] J. Van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf. Quantum SDP-solvers: Better upper and lower bounds. Quantum, 4:230, 2020. doi:10.22331/q-2020-02-14-230.
https://doi.org/10.22331/q-2020-02-14-230

[14] J. Wang, Y. Dong, and L. Lin. On the energy landscape of symmetric quantum signal processing. arXiv preprint arXiv:2110.04993, 2021. doi:10.48550/arXiv.2110.04993.
https://doi.org/10.48550/arXiv.2110.04993
arXiv:2110.04993

Cited by

[1] Jiasu Wang, Yulong Dong, and Lin Lin, "On the energy landscape of symmetric quantum signal processing", Quantum 6, 850 (2022).

[2] Michel Alexis, Gevorg Mnatsakanyan, and Christoph Thiele, "Quantum signal processing and nonlinear Fourier analysis", Revista Matemática Complutense 37 3, 655 (2024).

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

[4] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", Quantum 7, 1031 (2023).

[5] S. E. Skelton, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 150 (2024) ISBN:979-8-3315-4137-8.

[6] I. Novikau, I.Y. Dodin, and E.A. Startsev, "Encoding of linear kinetic plasma problems in quantum circuits via data compression", Journal of Plasma Physics 90 4, 805900401 (2024).

[7] Rei Sakuma, Kaito Wada, Shu Kanno, Kimberlee Keithley, Kenji Sugisaki, Takashi Abe, Hajime Nakamura, and Naoki Yamamoto, "Quantum-phase-estimation-based filtering: Performance analysis and application to low-energy spectral calculations", Physical Review A 113 1, 012602 (2026).

[8] John M. Martyn and Patrick Rall, "Halving the cost of quantum algorithms with randomization", npj Quantum Information 11 1, 47 (2025).

[9] Kaito Wada, Naoki Yamamoto, and Nobuyuki Yoshioka, "Heisenberg-Limited Adaptive Gradient Estimation for Multiple Observables", PRX Quantum 6 2, 020308 (2025).

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

[11] Bjorn K. Berntson and Christoph Sünderhauf, 2024 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) 625 (2024) ISBN:979-8-3503-5411-9.

[12] Bjorn K. Berntson and Christoph Sünderhauf, "Complementary Polynomials in Quantum Signal Processing", Communications in Mathematical Physics 406 7, 161 (2025).

[13] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", Quantum 7, 955 (2023).

[14] Lin Lin, Volume 7: Invited Lectures: Sections 15–20 57 (2026) ISBN:978-1-61197-872-8.

[15] Yuan Liu, John M. Martyn, Jasmine Sinanan-Singh, Kevin C. Smith, Steven M. Girvin, and Isaac L. Chuang, "Toward Mixed Analog-Digital Quantum Signal Processing: Quantum AD/DA Conversion and the Fourier Transform", IEEE Transactions on Signal Processing 73, 3641 (2025).

[16] Hongkang Ni and Lexing Ying, "Fast Phase Factor Finding for Quantum Signal Processing", SIAM Journal on Scientific Computing 48 4, B651 (2026).

[17] 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 1, 010201 (2026).

[18] John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, and Isaac L. Chuang, "Parallel Quantum Signal Processing Via Polynomial Factorization", Quantum 9, 1834 (2025).

[19] Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, and Dominic W. Berry, "Quantum linear system solvers: A survey of algorithms and applications", Reviews of Modern Physics 98 2, 025005 (2026).

[20] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Robust Iterative Method for Symmetric Quantum Signal Processing in All Parameter Regimes", SIAM Journal on Scientific Computing 46 5, A2951 (2024).

[21] Andreea-Iulia Lefterovici, Michael Perk, Debora Ramacciotti, Antonio F. Rotundo, Shawn E. Skelton, and Martin Steinbach, "Beyond Asymptotic Scaling: Comparing Functional Quantum Linear Solvers", IEEE Transactions on Quantum Engineering 7, 1 (2026).

[22] Youle Wang, "Resource-efficient quantum phase estimation by randomization", Quantum Science and Technology 10 3, 035036 (2025).

[23] Kevin J. Joven, Elin Ranjan Das, Joel Bierman, Aishwarya Majumdar, Masoud Hakimi Heris, and Yuan Liu, "Scalable quantum computational science: A perspective from block-encodings and polynomial transformations", APL Computational Physics 2 1, 010901 (2026).

[24] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Infinite quantum signal processing", Quantum 8, 1558 (2024).

[25] Hongkang Ni and Lexing Ying, "Quantum wave packet transforms with compact frequency support: Implementations for wavelets and Gabor atoms", Applied and Computational Harmonic Analysis 82, 101850 (2026).

[26] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[27] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang, "Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices", arXiv:2203.10236, (2022).

[28] Michel Alexis, Lin Lin, Gevorg Mnatsakanyan, Christoph Thiele, and Jiasu Wang, "Infinite quantum signal processing for arbitrary Szegő functions", arXiv:2407.05634, (2024).

[29] I. Novikau and I. Joseph, "Estimating QSVT angles for matrix inversion with large condition numbers", Journal of Computational Physics 525, 113767 (2025).

[30] I. Novikau, I. Y. Dodin, and E. A. Startsev, "Simulation of Linear Non-Hermitian Boundary-Value Problems with Quantum Singular-Value Transformation", Physical Review Applied 19 5, 054012 (2023).

[31] Ivan Novikau and Ilon Joseph, "Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems", arXiv:2410.03985, (2024).

[32] Sean Greenaway, William Pol, and Sukin Sim, "A case study against QSVT: assessment of quantum phase estimation improved by signal processing techniques", arXiv:2404.01396, (2024).

[33] S. E. Skelton, "Mostly Harmless Methods for QSP-Processing with Laurent Polynomials", arXiv:2408.04321, (2024).

[34] Tyler Kharazi, Ahmad M. Alkadri, Kranthi K. Mandadapu, and K. Birgitta Whaley, "Provable Quantum Speedups for Reaction-Rate Estimation in High-Dimensional Fokker-Planck Dynamics", arXiv:2601.15523, (2026).

[35] I. Novikau and I. Joseph, "Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems", Computer Physics Communications 309, 109498 (2025).

[36] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", arXiv:2301.08908, (2023).

[37] Kunal Marwaha, "The QAOA on the ring of disagrees", arXiv:2606.29562, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 14:25:38) and SAO/NASA ADS (last updated successfully 2026-08-10 14:25:40). 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.