1Department of Mathematics, University of California, Berkeley, CA 94720, USA.
2Challenge Institute for Quantum Computation, University of California, Berkeley, CA 94720, USA
3Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Symmetric quantum signal processing provides a parameterized representation of a real polynomial, which can be translated into an efficient quantum circuit for performing a wide range of computational tasks on quantum computers. For a given polynomial $f$, the parameters (called phase factors) can be obtained by solving an optimization problem. However, the cost function is non-convex, and has a very complex energy landscape with numerous global and local minima. It is therefore surprising that the solution can be robustly obtained in practice, starting from a fixed initial guess $Phi^0$ that contains no information of the input polynomial. To investigate this phenomenon, we first explicitly characterize all the global minima of the cost function. We then prove that one particular global minimum (called the maximal solution) belongs to a neighborhood of $Phi^0$, on which the cost function is strongly convex under the condition ${leftlVert frightrVert}_{infty}=mathcal{O}(d^{-1})$ with $d=mathrm{deg}(f)$. Our result provides a partial explanation of the aforementioned success of optimization algorithms.
► BibTeX data
► References
[1] D. P. Bertsekas. On the Goldstein-Levitin-Polyak gradient projection method. IEEE Transactions on automatic control, 21(2):174–184, 1976. doi:10.1109/TAC.1976.1101194.
https://doi.org/10.1109/TAC.1976.1101194
[2] S. Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231–357, 2015. doi:10.1561/2200000050.
https://doi.org/10.1561/2200000050
[3] R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy. Finding angles for quantum signal processing with machine precision, 2020. arXiv:2003.02831.
arXiv:2003.02831
[4] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. Toward the first quantum simulation with quantum speedup. Proc. Nat. Acad. Sci., 115(38):9456–9461, 2018. doi:10.1073/pnas.1801723115.
https://doi.org/10.1073/pnas.1801723115
[5] Y. Dong, X. Meng, K. B. Whaley, and L. Lin. Efficient phase factor evaluation in quantum signal processing. Phys. Rev. A, 103:042419, 2021. doi:10.1103/PhysRevA.103.042419.
https://doi.org/10.1103/PhysRevA.103.042419
[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. ACM, 2019. doi:10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366
[7] G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, third edition, 1996.
[8] 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
[9] N. J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, second edition, 2002. doi:10.1137/1.9780898718027.
https://doi.org/10.1137/1.9780898718027
[10] J. L. W. V. Jensen. Sur un nouvel et important théorème de la théorie des fonctions. Acta Mathematica, 22:359 – 364, 1900. doi:10.1007/BF02417878.
https://doi.org/10.1007/BF02417878
[11] C. T. Kelley. Iterative methods for optimization, volume 18. SIAM, 1999. doi:10.1137/1.9781611970920.
https://doi.org/10.1137/1.9781611970920
[12] L. Lin and Y. Tong. Near-optimal ground state preparation. Quantum, 4:372, 2020. doi:10.22331/q-2020-12-14-372.
https://doi.org/10.22331/q-2020-12-14-372
[13] L. Lin and Y. Tong. Optimal quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361, 2020. doi:10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361
[14] 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
[15] K. Mahler. On some inequalities for polynomials in several variables. Journal of The London Mathematical Society-second Series, pages 341–344, 1962. doi:10.1112/JLMS/S1-37.1.341.
https://doi.org/10.1112/JLMS/S1-37.1.341
[16] J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang. A grand unification of quantum algorithms. American Physical Society (APS), 2(4), 2021. doi:10.1103/PRXQuantum.2.040203.
https://doi.org/10.1103/PRXQuantum.2.040203
[17] M. A. Nielsen and I. Chuang. Quantum computation and quantum information. Cambridge Univ. Pr., 2000. doi:10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
[18] J. Nocedal and S. J. Wright. Numerical optimization. Springer Verlag, 1999. doi:10.1007/b98874.
https://doi.org/10.1007/b98874
[19] L. Ying. Stable factorization for phase factors of quantum signal processing. Quantum, 6:842, 2022. doi:10.22331/q-2022-10-20-842.
https://doi.org/10.22331/q-2022-10-20-842
Cited by
[1] Yulong Dong, Lin Lin, and Yu Tong, “Ground-State Preparation and Energy Estimation on Early Fault-Tolerant Quantum Computers via Quantum Eigenvalue Transformation of Unitary Matrices”, PRX Quantum 3 4, 040305 (2022).
[2] Zane M. Rossi and Isaac L. Chuang, “Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle”, arXiv:2205.06261.
[3] Patrick Rall and Bryce Fuller, “Amplitude Estimation from Quantum Signal Processing”, arXiv:2207.08628.
[4] Lexing Ying, “Stable factorization for phase factors of quantum signal processing”, arXiv:2202.02671.
[5] Di Fang, Lin Lin, and Yu Tong, “Time-marching based quantum solvers for time-dependent linear differential equations”, arXiv:2208.06941.
[6] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, “Infinite quantum signal processing”, arXiv:2209.10162.
[7] Yulong Dong, Jonathan Gross, and Murphy Yuezhen Niu, “Beyond Heisenberg Limit Quantum Metrology through Quantum Signal Processing”, arXiv:2209.11207.
The above citations are from SAO/NASA ADS (last updated successfully 2022-11-03 13:15:19). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2022-11-03 13:15:17: Could not fetch cited-by data for 10.22331/q-2022-11-03-850 from Crossref. This is normal if the DOI was registered recently.
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.
