On the energy landscape of symmetric quantum signal processing
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
Published: | 2022-11-03, volume 6, page 850 |
Eprint: | arXiv:2110.04993v2 |
Doi: | https://doi.org/10.22331/q-2022-11-03-850 |
Citation: | Quantum 6, 850 (2022). |
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 ${\left\lVert f\right\rVert}_{\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] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", Quantum 7, 955 (2023).
[2] Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", Quantum 7, 937 (2023).
[3] Jasmine Sinanan-Singh, Gabriel L. Mintzer, Isaac L. Chuang, and Yuan Liu, "Single-shot Quantum Signal Processing Interferometry", Quantum 8, 1427 (2024).
[4] Mario Motta, William Kirby, Ieva Liepuoniute, Kevin J Sung, Jeffrey Cohn, Antonio Mezzacapo, Katherine Klymko, Nam Nguyen, Nobuyuki Yoshioka, and Julia E Rice, "Subspace methods for electronic structure simulations on quantum computers", Electronic Structure 6 1, 013001 (2024).
[5] Mark Steudtner, Sam Morley-Short, William Pol, Sukin Sim, Cristian L. Cortes, Matthias Loipersberger, Robert M. Parrish, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Fault-tolerant quantum computation of molecular observables", Quantum 7, 1164 (2023).
[6] Kaoru Mizuta and Keisuke Fujii, "Recursive quantum eigenvalue and singular-value transformation: Analytic construction of matrix sign function by Newton iteration", Physical Review Research 6 1, L012007 (2024).
[7] Michel Alexis, Gevorg Mnatsakanyan, and Christoph Thiele, "Quantum signal processing and nonlinear Fourier analysis", Revista Matemática Complutense (2024).
[8] Sho Sugiura, Arkopal Dutt, William J. Munro, Sina Zeytinoğlu, and Isaac L. Chuang, "Power of Sequential Protocols in Hidden Quantum Channel Discrimination", Physical Review Letters 132 24, 240805 (2024).
[9] Zane M. Rossi and Isaac L. Chuang, "Semantic embedding for quantum algorithms", Journal of Mathematical Physics 64 12, 122202 (2023).
[10] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang, "Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices", SIAM Journal on Matrix Analysis and Applications 45 1, 801 (2024).
[11] 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).
[12] Zane M. Rossi, Jack L. Ceroni, and Isaac L. Chuang, "Modular quantum signal processing in many variables", arXiv:2309.16665, (2023).
[13] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Infinite quantum signal processing", arXiv:2209.10162, (2022).
[14] Zane M. Rossi and Isaac L. Chuang, "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle", Quantum 6, 811 (2022).
[15] Michel Alexis, Lin Lin, Gevorg Mnatsakanyan, Christoph Thiele, and Jiasu Wang, "Infinite quantum signal processing for arbitrary Szegő functions", arXiv:2407.05634, (2024).
[16] Zane M. Rossi, Victor M. Bastidas, William J. Munro, and Isaac L. Chuang, "Quantum signal processing with continuous variables", arXiv:2304.14383, (2023).
[17] Lexing Ying, "Stable factorization for phase factors of quantum signal processing", Quantum 6, 842 (2022).
[18] Yulong Dong, Jonathan Gross, and Murphy Yuezhen Niu, "Beyond Heisenberg Limit Quantum Metrology through Quantum Signal Processing", arXiv:2209.11207, (2022).
[19] S. E. Skelton, "Mostly Harmless Methods for QSP-Processing with Laurent Polynomials", arXiv:2408.04321, (2024).
The above citations are from Crossref's cited-by service (last updated successfully 2024-09-01 01:49:29) and SAO/NASA ADS (last updated successfully 2024-09-01 01:49:30). 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.