Pure quantum gradient descent algorithm and full quantum variational eigensolver

Abstract

Optimization problems are prevalent in various fields, and the gradient-based gradient descent algorithm is a widely adopted optimization method. However, in classical computing, computing the numerical gradient for a function with d variables necessitates at least d+1 function evaluations, resulting in a computational complexity of O(d). As the number of variables increases, the classical gradient estimation methods require substantial resources, ultimately surpassing the capabilities of classical computers. Fortunately, leveraging the principles of superposition and entanglement in quantum mechanics, quantum computers can achieve genuine parallel computing, leading to exponential acceleration over classical algorithms in some cases. In this paper, we propose a novel quantum-based gradient calculation method that requires only a single oracle calculation to obtain the numerical gradient result for a multivariate function. The complexity of this algorithm is just O(1). Building upon this approach, we successfully implemented the quantum gradient descent algorithm and applied it to the variational quantum eigensolver (VQE), creating a pure quantum variational optimization algorithm. Compared with classical gradient-based optimization algorithm, this quantum optimization algorithm has remarkable complexity advantages, providing an efficient solution to optimization problems.The proposed quantum-based method shows promise in enhancing the performance of optimization algorithms, highlighting the potential of quantum computing in this field.

Graphical abstract

Keywords

quantum algorithm / gradient descent / variational quantum algorithm

References

[1] E.FarhiJ. Goldstone, A quantum approximate optimization algorithm, arXiv: 1411.4028 (2014)

[2] E.FarhiJ. GoldstoneS.GutmannM.Sipser, Quantum computation by adiabatic evolution, arXiv: quant-ph/0001106 (2000)

[3] G. G. Guerreschi, A. Y. Matsuura. Qaoa for max-cut requires hundreds of qubits for quantum speed-up. Sci. Rep., 2019, 6(1): 6903

[4] M.A. Nielsen, Neural Networks and Deep Learning, Determination Press, 2015

[5] M.SchuldI. Sinayskiy, The quest for a quantum neural network, arXiv: 1408.7005 (2014)

[6] V. Dunjko, J. M. Taylor, H. J. Briegel. Quantumenhanced machine learning. Phys. Rev. Lett., 2016, 117(13): 130501

[7] T.Sakuma, Application of deep quantum neural networks to finance, arXiv: 2011.07319 (2020)

[8] R.OrusS. MugelE.Lizaso, Quantum computing for finance: Overview and prospects, arXiv: 1807.03890v2 (2018)

[9] D. J. Egger, C. Gambella, J. Marecek, S. McFaddin, M. Mevissen, R. Raymond, A. Simonetto, S. Woerner, E. Yndurain. Quantum computing for finance: State-of-the-art and future prospects. IEEE Trans. Quant. Eng., 2020, 1: 3101724

[10] R. P. Feynmen. Forces in molecules. Phys. Rev. Lett., 1939, 56: 340

[11] D. A. Fedorov, M. J. Otten, S. K. Gray, Y. Alexeev. Ab initio molecular dynamics on quantum computers. J. Chem. Phys., 2021, 154(16): 164103

[12] V. Gandhi, G. Prasad, D. Coyle, L. Behera, T. M. McGinnity. Quantum neural network-based EEG filtering for a brain–computer interface. IEEE Trans. Neural Netw. Learn. Syst., 2014, 25(2): 278

[13] A.PeruzzoJ. McCleanP.Shadbolt, ., A variational eigenvalue solver on a quantum processor, arXiv: 1304.3061 (2013)

[14] S. Wei, H. Li, G. Long. A full quantum eigensolver for quantum chemistry simulations. Research, 2020, 2020: 1486935

[15] S.Ruder, An overview of gradient descent optimization algorithms, arXiv: 1609.04747 (2016)

[16] J. R. McClean, J. Romero, R. Babbush, A. Aspuru-Guzik. The theory of variational hybrid quantumclassical algorithms. New J. Phys., 2016, 18(2): 023023

[17] M.CerezoA. ArrasmithR.BabbushS.C. BenjaminS.Endo K.FujiiJ. R. McCleanK.MitaraiX.YuanL.Cincio P.J. Coles, Variational quantum algorithms, arXiv: 2012.09265 (2020)

[18] S. Y. Hou, G. Feng, Z. Wu, H. Zou, W. Shi, J. Zeng, C. Cao, S. Yu, Z. Sheng, X. Rao, B. Ren, D. Lu, J. Zou, G. Miao, J. Xiang, B. Zeng. Spinq gemini: A desktop quantum computing platform for education and research. EPJ Quantum Technol., 2021, 8(1): 20

[19] G. Yuan, T. Li, W. Hu. A conjugate gradient algorithm and its application in large-scale optimization problems and image restoration. J. Inequal. Appl., 2019, 2019(1): 247

[20] C. G. Broyden. The convergence of a class of double-rank minimization algorithms (1): General considerations. IMA J. Appl. Math., 1970, 6(1): 76

[21] R. Fletcher. A new approach to variable metric algorithms. Comput. J., 1970, 13(3): 317

[22] D. Goldfarb. A family of variable-metric methods derived by variational means. Math. Comput., 1970, 24(109): 23

[23] D. F. Shanno. Conditioning of quasi-Newton methods for function minimization. Math. Comput., 1970, 24(111): 647

[24] P. Gao, K. Li, S. Wei, J. Gao, G. Long. Quantum gradient algorithm for general polynomials. Phys. Rev. A, 2021, 103(4): 042403

[25] M.NielsenI. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010

[26] D. P. DiVincenzo. Quantum computation. Science, 1995, 270(5234): 255

[27] J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79

[28] P.W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in: Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp 124–134

[29] T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, R. Blatt. Realization of a scalable Shor algorithm. Science, 2016, 351(6277): 1068

[30] L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 1997, 79(2): 325

[31] G. L. Long. Grover algorithm with zero theoretical failure rate. Phys. Rev. A, 2001, 64(2): 022307

[32] A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 2009, 103(15): 150502

[33] B. Duan, J. Yuan, C. H. Yu, J. Huang, C. Y. Hsieh. A survey on HHLalgorithm: From theory to application in quantum machine learning. Phys. Lett. A, 2020, 384(24): 126595

[34] S. P. Jordan. Fast quantum algorithm for numerical gradient estimation. Phys. Rev. Lett., 2005, 95(5): 050501

[35] R.WiersemaD. LewisD.WierichsJ.CarrasquillaN.Killoran, Here comes the SU(n): multivariate quantum gates and gradients, arXiv: 2303.11355 (2023)

[36] A.GilyénS.ArunachalamN.Wiebe, Optimizing quantum optimization algorithms via faster quantum gradient computation, in: Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp 1425–1444

[37] J. Li. General explicit difference formulas for numerical differentiation. J. Comput. Appl. Math., 2005, 183(1): 29

[38] W.H. PressS. A. TeukolskyW.T. Vetterling, Numerical Recipes in C, Cambridge University Press, 1992

[39] Y.LiM.Dou, A quantum addition operation method, device, electronic device and storage medium, Origin Quantum (2021)

[40] C. Zhu, R. H. Byrd, P. Lu, J. Nocedal. Algorithm 778: L-BFGS-B. ACM Trans. Math. Softw., 1997, 23(4): 550

[41] G.Aleksandrowicz, ., Qiskit: An open-source framework for quantum computing, 2019

[42] R. M. Parrish, E. G. Hohenstein, P. L. McMahon, T. J. Martínez. Quantum computation of electronic transitions using a variational quantum eigensolver. Phys. Rev. Lett., 2019, 122(23): 230401

[43] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, J. M. Gambetta. Hardwareefficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 2017, 549(7671): 242

[44] C. Hempel, C. Maier, J. Romero, J. McClean, T. Monz, H. Shen, P. Jurcevic, B. P. Lanyon, P. Love, R. Babbush, A. Aspuru-Guzik, R. Blatt, C. F. Roos. Quantum chemistry calculations on a trapped-ion quantum simulator. Phys. Rev. X, 2018, 8(3): 031022

[45] K. Mitarai, M. Negoro, M. Kitagawa, K. Fujii. Quantum circuit learning. Phys. Rev. A, 2018, 98(3): 032309

[46] M. Schuld, V. Bergholm, C. Gogolin, J. Izaac, N. Killoran. Evaluating analytic gradients on quantum hardware. Phys. Rev. A, 2019, 99(3): 032331

[47] J. Lee, W. J. Huggins, M. Head-Gordon, K. B. Whaley. Generalized unitary coupled cluster wave functions for quantum computation. J. Chem. Theory Comput., 2019, 15(1): 311

[48] D. Wecker, M. B. Hastings, M. Troyer. Progress towards practical quantum variational algorithms. Phys. Rev. A, 2015, 92(4): 042303

[49] R. Wiersema, C. Zhou, Y. de Sereville, J. F. Carrasquilla, Y. B. Kim, H. Yuen. Exploring entanglement and optimization within the hamiltonian variational ansatz. PRX Quantum, 2020, 1(2): 020319

[50] A.GilyénY.SuG.H. Low N.Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, arXiv: 1806.01838 (2018)

[51] G.H. LowI. L. Chuang, Hamiltonian simulation by qubitization, arXiv: 1610.06546 (2016)

[52] A.M. ChildsN. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, arXiv: 1202.5822 (2012)

[53] L.Bottou, Large-scale machine learning with stochastic gradient descent, in: Proceedings of COMPSTAT’2010, edited by Y. Lechevallier and G. Saporta, Physica-Verlag HD, Heidelberg, 2010, pp 177–186

Declarations

The authors declare that they have no competing interests and there are no conflicts.

Acknowledgements

R. Chen and S. Y. Hou are supported by the National Natural Science Foundation of China under Grant No. 12105195.

RIGHTS & PERMISSIONS

2023 Higher Education Press