Stable factorization for phase factors of quantum signal processing

Lexing Ying

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

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


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

► 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.

[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.

[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.

[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.

[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.

[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.

[7] J. Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3:190, 2019. doi: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.

[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.

[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.

[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.

[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.

[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.

Cited by

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

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

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

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

[5] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Infinite quantum signal processing", arXiv:2209.10162, (2022).

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

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

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