Pure quantum gradient descent algorithm and full quantum variational eigensolver

doi:10.1007/s11467-023-1346-7

Frontiers of Physics

2024, Vol. 19

Issue (2): 21202 https://doi.org/10.1007/s11467-023-1346-7

本期目录

Pure quantum gradient descent algorithm and full quantum variational eigensolver

Ronghang Chen^1,², Zhou Guang³, Cong Guo², Guanru Feng², Shi-Yao Hou^1,²(

)

¹. College of Physics and Electronic Engineering, Center for Computational Sciences, Sichuan Normal University, Chengdu 610068, China
². Shenzhen SpinQ Technology Co., Ltd., Shenzhen 518045, China
³. DEEPROUTE.AI

全文: PDF(7124 KB) HTML

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.

Key words： quantum algorithm gradient descent variational quantum algorithm

收稿日期: 2023-06-28 出版日期: 2023-10-17

Corresponding Author(s): Shi-Yao Hou

引用本文:

. [J]. Frontiers of Physics, 2024, 19(2): 21202.
Ronghang Chen, Zhou Guang, Cong Guo, Guanru Feng, Shi-Yao Hou. Pure quantum gradient descent algorithm and full quantum variational eigensolver. Front. Phys. , 2024, 19(2): 21202.

链接本文:

https://academic.hep.com.cn/fop/CN/10.1007/s11467-023-1346-7
https://academic.hep.com.cn/fop/CN/Y2024/V19/I2/21202

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

1	Farhi E.Goldstone J., A quantum approximate optimization algorithm, arXiv: 1411.4028 (2014)
2	Farhi E.Goldstone J.Gutmann S.Sipser M., Quantum computation by adiabatic evolution, arXiv: quant-ph/0001106 (2000)
3	G. Guerreschi G., Y. Matsuura A.. Qaoa for max-cut requires hundreds of qubits for quantum speed-up. Sci. Rep., 2019, 6(1): 6903 https://doi.org/10.1038/s41598-019-43176-9
4	A. Nielsen M., Neural Networks and Deep Learning, Determination Press, 2015
5	Schuld M.Sinayskiy I., The quest for a quantum neural network, arXiv: 1408.7005 (2014)
6	Dunjko V., M. Taylor J., J. Briegel H.. Quantumenhanced machine learning. Phys. Rev. Lett., 2016, 117(13): 130501 https://doi.org/10.1103/PhysRevLett.117.130501
7	Sakuma T., Application of deep quantum neural networks to finance, arXiv: 2011.07319 (2020)
8	Orus R.Mugel S.Lizaso E., Quantum computing for finance: Overview and prospects, arXiv: 1807.03890v2 (2018)
9	J. Egger D., Gambella C., Marecek J., McFaddin S., Mevissen M., Raymond R., Simonetto A., Woerner S., Yndurain E.. Quantum computing for finance: State-of-the-art and future prospects. IEEE Trans. Quant. Eng., 2020, 1: 3101724 https://doi.org/10.1109/TQE.2020.3030314
10	P. Feynmen R.. Forces in molecules. Phys. Rev. Lett., 1939, 56: 340 https://doi.org/10.1103/PhysRev.56.340
11	A. Fedorov D., J. Otten M., K. Gray S., Alexeev Y.. Ab initio molecular dynamics on quantum computers. J. Chem. Phys., 2021, 154(16): 164103 https://doi.org/10.1063/5.0046930
12	Gandhi V., Prasad G., Coyle D., Behera L., M. McGinnity T.. Quantum neural network-based EEG filtering for a brain–computer interface. IEEE Trans. Neural Netw. Learn. Syst., 2014, 25(2): 278 https://doi.org/10.1109/TNNLS.2013.2274436
13	Peruzzo A.McClean J.Shadbolt P., et al.., A variational eigenvalue solver on a quantum processor, arXiv: 1304.3061 (2013)
14	Wei S., Li H., Long G.. A full quantum eigensolver for quantum chemistry simulations. Research, 2020, 2020: 1486935 https://doi.org/10.34133/2020/1486935
15	Ruder S., An overview of gradient descent optimization algorithms, arXiv: 1609.04747 (2016)
16	R. McClean J., Romero J., Babbush R., Aspuru-Guzik A.. The theory of variational hybrid quantumclassical algorithms. New J. Phys., 2016, 18(2): 023023 https://doi.org/10.1088/1367-2630/18/2/023023
17	Cerezo M.Arrasmith A.Babbush R.C. Benjamin S.Endo S. Fujii K.R. McClean J.Mitarai K.Yuan X.Cincio L. J. Coles P., Variational quantum algorithms, arXiv: 2012.09265 (2020)
18	Y. Hou S., Feng G., Wu Z., Zou H., Shi W., Zeng J., Cao C., Yu S., Sheng Z., Rao X., Ren B., Lu D., Zou J., Miao G., Xiang J., Zeng B.. Spinq gemini: A desktop quantum computing platform for education and research. EPJ Quantum Technol., 2021, 8(1): 20 https://doi.org/10.1140/epjqt/s40507-021-00109-8
19	Yuan G., Li T., Hu W.. A conjugate gradient algorithm and its application in large-scale optimization problems and image restoration. J. Inequal. Appl., 2019, 2019(1): 247 https://doi.org/10.1186/s13660-019-2192-6
20	G. Broyden C.. The convergence of a class of double-rank minimization algorithms (1): General considerations. IMA J. Appl. Math., 1970, 6(1): 76 https://doi.org/10.1093/imamat/6.1.76
21	Fletcher R.. A new approach to variable metric algorithms. Comput. J., 1970, 13(3): 317 https://doi.org/10.1093/comjnl/13.3.317
22	Goldfarb D.. A family of variable-metric methods derived by variational means. Math. Comput., 1970, 24(109): 23 https://doi.org/10.1090/S0025-5718-1970-0258249-6
23	F. Shanno D.. Conditioning of quasi-Newton methods for function minimization. Math. Comput., 1970, 24(111): 647 https://doi.org/10.1090/S0025-5718-1970-0274029-X
24	Gao P., Li K., Wei S., Gao J., Long G.. Quantum gradient algorithm for general polynomials. Phys. Rev. A, 2021, 103(4): 042403 https://doi.org/10.1103/PhysRevA.103.042403
25	Nielsen M.Chuang I., Quantum Computation and Quantum Information, Cambridge University Press, 2010
26	P. DiVincenzo D.. Quantum computation. Science, 1995, 270(5234): 255 https://doi.org/10.1126/science.270.5234.255
27	Preskill J.. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79 https://doi.org/10.22331/q-2018-08-06-79
28	W. Shor P., Algorithms for quantum computation: Discrete logarithms and factoring, in: Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp 124–134
29	Monz T., Nigg D., A. Martinez E., F. Brandl M., Schindler P., Rines R., X. Wang S., L. Chuang I., Blatt R.. Realization of a scalable Shor algorithm. Science, 2016, 351(6277): 1068 https://doi.org/10.1126/science.aad9480
30	K. Grover L.. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 1997, 79(2): 325 https://doi.org/10.1103/PhysRevLett.79.325
31	L. Long G.. Grover algorithm with zero theoretical failure rate. Phys. Rev. A, 2001, 64(2): 022307 https://doi.org/10.1103/PhysRevA.64.022307
32	W. Harrow A., Hassidim A., Lloyd S.. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 2009, 103(15): 150502 https://doi.org/10.1103/PhysRevLett.103.150502
33	Duan B., Yuan J., H. Yu C., Huang J., Y. Hsieh C.. A survey on HHLalgorithm: From theory to application in quantum machine learning. Phys. Lett. A, 2020, 384(24): 126595 https://doi.org/10.1016/j.physleta.2020.126595
34	P. Jordan S.. Fast quantum algorithm for numerical gradient estimation. Phys. Rev. Lett., 2005, 95(5): 050501 https://doi.org/10.1103/PhysRevLett.95.050501
35	Wiersema R.Lewis D.Wierichs D.Carrasquilla J.Killoran N., Here comes the SU(n): multivariate quantum gates and gradients, arXiv: 2303.11355 (2023)
36	Gilyén A.Arunachalam S.Wiebe N., 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	Li J.. General explicit difference formulas for numerical differentiation. J. Comput. Appl. Math., 2005, 183(1): 29 https://doi.org/10.1016/j.cam.2004.12.026
38	H. Press W.A. Teukolsky S.T. Vetterling W., Numerical Recipes in C, Cambridge University Press, 1992
39	Li Y.Dou M., A quantum addition operation method, device, electronic device and storage medium, Origin Quantum (2021)
40	Zhu C., H. Byrd R., Lu P., Nocedal J.. Algorithm 778: L-BFGS-B. ACM Trans. Math. Softw., 1997, 23(4): 550 https://doi.org/10.1145/279232.279236
41	Aleksandrowicz G., et al.., Qiskit: An open-source framework for quantum computing, 2019
42	M. Parrish R., G. Hohenstein E., L. McMahon P., J. Martínez T.. Quantum computation of electronic transitions using a variational quantum eigensolver. Phys. Rev. Lett., 2019, 122(23): 230401 https://doi.org/10.1103/PhysRevLett.122.230401
43	Kandala A., Mezzacapo A., Temme K., Takita M., Brink M., M. Chow J., M. Gambetta J.. Hardwareefficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 2017, 549(7671): 242 https://doi.org/10.1038/nature23879
44	Hempel C., Maier C., Romero J., McClean J., Monz T., Shen H., Jurcevic P., P. Lanyon B., Love P., Babbush R., Aspuru-Guzik A., Blatt R., F. Roos C.. Quantum chemistry calculations on a trapped-ion quantum simulator. Phys. Rev. X, 2018, 8(3): 031022 https://doi.org/10.1103/PhysRevX.8.031022
45	Mitarai K., Negoro M., Kitagawa M., Fujii K.. Quantum circuit learning. Phys. Rev. A, 2018, 98(3): 032309 https://doi.org/10.1103/PhysRevA.98.032309
46	Schuld M., Bergholm V., Gogolin C., Izaac J., Killoran N.. Evaluating analytic gradients on quantum hardware. Phys. Rev. A, 2019, 99(3): 032331 https://doi.org/10.1103/PhysRevA.99.032331
47	Lee J., J. Huggins W., Head-Gordon M., B. Whaley K.. Generalized unitary coupled cluster wave functions for quantum computation. J. Chem. Theory Comput., 2019, 15(1): 311 https://doi.org/10.1021/acs.jctc.8b01004
48	Wecker D., B. Hastings M., Troyer M.. Progress towards practical quantum variational algorithms. Phys. Rev. A, 2015, 92(4): 042303 https://doi.org/10.1103/PhysRevA.92.042303
49	Wiersema R., Zhou C., de Sereville Y., F. Carrasquilla J., B. Kim Y., Yuen H.. Exploring entanglement and optimization within the hamiltonian variational ansatz. PRX Quantum, 2020, 1(2): 020319 https://doi.org/10.1103/PRXQuantum.1.020319
50	Gilyén A.Su Y.H. Low G. Wiebe N., Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, arXiv: 1806.01838 (2018)
51	H. Low G.L. Chuang I., Hamiltonian simulation by qubitization, arXiv: 1610.06546 (2016)
52	M. Childs A.Wiebe N., Hamiltonian simulation using linear combinations of unitary operations, arXiv: 1202.5822 (2012)
53	Bottou L., 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

Viewed

Full text

Abstract

Cited

Shared

Discussed