Stable factorization for phase factors of quantum signal processing

Source Node: 1727328

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.

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.

[embedded content]

â–º 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.
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] Di Fang, Lin Lin, and Yu Tong, “Time-marching based quantum solvers for time-dependent linear differential equations”, arXiv:2208.06941.

[2] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, “Infinite quantum signal processing”, arXiv:2209.10162.

The above citations are from SAO/NASA ADS (last updated successfully 2022-10-21 13:49:48). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2022-10-21 13:49:46).

Time Stamp:

More from Quantum Journal