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