Pure quantum gradient descent algorithm and full quantum variational eigensolver

doi:10.1007/s11467-023-1346-7

Front. Phys.

2024, Vol. 19

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

RESEARCH ARTICLE

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

Download: PDF(7124 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords quantum algorithm gradient descent variational quantum algorithm

Corresponding Author(s): Shi-Yao Hou

Issue Date: 17 October 2023

Cite this article:

Ronghang Chen,Zhou Guang,Cong Guo, et al. Pure quantum gradient descent algorithm and full quantum variational eigensolver[J]. Front. Phys. , 2024, 19(2): 21202.

URL:

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

Fig.1 Diagram of a quantum variational algorithm optimized using gradient descent algorithm. (a) The algorithm involves the generation of a parameterized quantum circuit on a quantum computer, followed by optimization of the objective function parameters on a classical computer. This iterative process involves the exchange of data between the quantum and classical computers. (b) The algorithm utilizes a pure quantum gradient estimation approach to evolve the parameterized unitary operator on the quantum circuit, effectively replacing classical gradient algorithm. The process is repeated iteratively until the objective function is minimized. All operations of this algorithm can be efficiently performed on a quantum computer.

Fig.2 Schematic diagram of the proposed pure quantum algorithm for gradient estimation. The algorithm is designed to enable direct estimation of the gradient through the use of Hadamard gates (H) to create superposition states, QADD and QSUB gates for entanglement-free quantum addition and subtraction between qubits, an oracle (U) for evolving the gradient, and an Inverse Quantum Fourier Transform (IQFT) for extracting phase information.

Fig.3 Schematic diagram of a quantum adder without entanglement. (a) The MAJ module performs addition on the input states to obtain the sum of the two states and a carry qubit. (b) The UMA module adds the sum and the carry qubit from the MAJ module to achieve the effect of a full adder. (c) This quantum adder (QADD) uses MAJ and UMA modules to perform addition operations on the input state, and the output states are not entangled with each other, which can be used for subsequent operations on specific target qubits.

Fig.4 Schematic diagram of a quantum adder that generates entanglement. The output qubits of this type of quantum adder will become entangled with each other, making it impossible to extract information about the target qubits for subsequent calculations.

Fig.5 Schematic diagram of a quantum complement circuit. A quantum subtractor can be regarded as adding a negative number using an adder, so it is only necessary to apply the adder to the complement of the subtrahend. For example, to get the complement of

− 010

, in Step1, construct the quantum state of the value qubits of

− 010

. In Step2, take the one’s complement of the value qubits. In Step3, construct the quantum state of

| 1 ?

. Then, use a quantum adder to add

| 1 ?

to the complemented value qubits obtained in Step2 to obtain the two’s complement of

− 010

, which is represented as

| s 2 s 1 s 0 ?

in the value qubits.

Fig.6 Quantum circuit diagram and results for estimating the gradient at zero.

Fig.7 Using the pure quantum gradient estimation algorithm on Qiskit to estimate the gradient of the target function

f (x 1, x 2) = 0.1 (x 1 + x 22) 2 + 0.1 (1 + x 22) 2

at various initial points.

Fig.8 The results of quantum gradient descent of the objective function

f (x 1, x 2) = 0.1 (x 1 + x 22) 2 + 0.1 (1 + x 22) 2

at various starting points using this pure quantum gradient descent algorithm on Qiskit.

Fig.9 The ansatz for 2-qubit VQE.

θ 1, θ 2

are the parameters to be optimized.

Fig.10 Results of the full quantum variational eigensolver. The black line represents the exact ground state energy of the model, which is −3. The red line represents the optimization process using the full quantum variational eigensolver, while the blue line represents the optimization process using variational quantum eigensolver. Both optimization methods converge to −2.99 after sufficient iterations.

Fig.11 The relationship between the number of qubits encoding decimals and the error of gradient estimation in the algorithm. When m is fixed to the same value

(m = 2)

, the more qubits used to encode decimals, the smaller the error and higher the accuracy.

Fig.12 The relationship between the size of the parameter m and the error of gradient estimation in the algorithm. When the number of qubits used to encode decimals is fixed, the closer the parameter m is to the actual gradient, the smaller the error.

Fig. A1 Quantum circuit diagram for converting the ground state energy of the model into probability. Here,

| 0 ?

is an auxiliary qubit,

| ψ θ ?

is the state obtained by the ansatz in the VQE algorithm,

C (U)

is a controlled unitary operation. Using a method similar to the Hadamard test, we can obtain a probability of

(1 − ? ψ θ | U | ψ θ ?) / 2

for the outcome to be 1 on the auxiliary qubit.

Fig. B1 Quantum circuit diagram for transformation of ground state energy into probability. The probability of measuring 1 in the ancillary qubit is

(1 − ? ψ θ | H h | ψ θ ?) / 2

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

[1]	Xu-Dan Xie, Zheng-Yuan Xue, Dan-Bo Zhang. Variational quantum algorithms for scanning the complex spectrum of non-Hermitian systems[J]. Front. Phys. , 2024, 19(4): 41202-.
[2]	Bin Cheng, Xiu-Hao Deng, Xiu Gu, Yu He, Guangchong Hu, Peihao Huang, Jun Li, Ben-Chuan Lin, Dawei Lu, Yao Lu, Chudan Qiu, Hui Wang, Tao Xin, Shi Yu, Man-Hong Yung, Junkai Zeng, Song Zhang, Youpeng Zhong, Xinhua Peng, Franco Nori, Dapeng Yu. Noisy intermediate-scale quantum computers[J]. Front. Phys. , 2023, 18(2): 21308-.
[3]	Junxiang Xiao, Jingwei Wen, Shijie Wei, Guilu Long. Reconstructing unknown quantum states using variational layerwise method[J]. Front. Phys. , 2022, 17(5): 51501-.
[4]	M. AbuGhanem, A. H. Homid, M. Abdel-Aty. Cavity control as a new quantum algorithms implementation treatment[J]. Front. Phys. , 2018, 13(1): 130303-.

Viewed

Full text

Abstract

Cited

Shared

Discussed