# Pure Quantum Gradient Descent Algorithm and Full Quantum Variational
Eigensolver

Ronghang Chen  Shi-Yao Hou<EMAIL_ADDRESS>College of Physics and
Electronic Engineering, Center for Computational Sciences, Sichuan Normal
University, Chengdu 610068, China  Shenzhen SpinQ Technology Co., Ltd.,
Shenzhen, China  Cong Guo  Guanru Feng  Shenzhen SpinQ Technology Co., Ltd.,
Shenzhen, China

###### 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.

##  I Introduction

Optimization problems are a crucial research area that involves finding
parameter values that minimize or maximize an objective function subject to
given constraints [1, 2, 3]. They have broad-ranging applications in diverse
fields, including machine learning [4, 5, 6], finance[7, 8, 9], quantum
chemical calculations [10, 11], and the pharmaceutical industry [12].Gradient
descent is one of the widely used optimization methods in solving optimization
problems [13, 14]. The basic idea of the gradient descent algorithm is to
iteratively adjust the model parameters to minimize the loss function.
Specifically, the algorithm computes the gradient of the loss function for
each parameter and then updates the parameters in the opposite direction of
the gradient to minimize the loss function as rapidly as possible. This
process is repeated multiple times until convergence [15].

With the rapid development of quantum computing, variational quantum algorithm
have gained increasing attention as a means to solve optimization problems by
adjusting some parameters in a quantum circuit to minimize an objective
function [16, 17]. In optimization problems, as illustrated in Fig. 1(a), we
first create a quantum circuit with parameters to calculate the objective
function. Classical optimization algorithms, such as the gradient descent
algorithm, are then utilized to optimize the objective function on a classical
computer. The optimized parameters are then fed back into the quantum circuit,
and the optimization process continues until convergence [18, 13]. Various
classical optimization algorithms, such as the conjugate gradient method [19]
and Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm [20, 21, 22, 23], are
widely used in variational quantum algorithm. It should be noted that during
the optimization process, classical optimization algorithms continuously
measure the quantum circuit and input the results into the classical computer
for computation, which may affect the algorithm’s convergence rate. Moreover,
when employing the gradient-based gradient descent algorithm on a classical
computer, the numerical gradient calculation is the core of the algorithm,
with a complexity of $O(d)$ [24]. As the number of variables $d$ increases,
the resource consumption grows rapidly, potentially impacting the optimization
algorithm’s convergence.

(a) Schematic diagram of the Variational Quantum Algorithm

(b) Schematic diagram of the proposed pure quantum variational algorithm

Figure 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.

Quantum computers leverage the principles of superposition and entanglement to
achieve remarkable acceleration in certain problems compared to classical
computers. [25, 26, 27, 28, 29, 30, 31, 32, 33]. In the context of gradient
computation, several quantum gradient calculation methods have been proposed,
but they suffer from limitations in terms of applicability or complexity. [34,
24, 35, 36, 37]. Therefore, in this paper, we propose a pure quantum gradient
estimation method that does not require classical computation of the gradient.
For a multivariate function, this algorithm can achieve numerical gradient
computation with just one oracle calculation, and its complexity is only
$O(1)$, which does not consume additional computational resources with an
increase in the number of variables.

Figure 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.

Based on this, we implemented a quantum gradient descent algorithm based on
pure quantum gradient estimation. We conducted numerical experiments using
this algorithm and applied it to calculate the ground state energy of a small-
scale Hamiltonian in VQE [18], as shown in Fig. 1(b). The optimization process
of this algorithm does not depend on classical computation of the gradient.
The numerical experiments demonstrate that our proposed pure quantum gradient
estimation algorithm, quantum gradient descent algorithm, and its application
in the Heisenberg model have produced satisfactory results. Furthermore, this
pure gradient evolution algorithm has theoretical advantages in complexity,
which can accelerate the convergence rate of optimization problems in large-
scale problems, providing a more efficient optimization algorithm for
optimization problems.

The organizational structure of this paper is as follows: In Section II, we
present a pure quantum gradient estimation algorithm. In Section III, we
describe the quantum gradient descent algorithm which is implemented using the
proposed pure quantum gradient estimation algorithm. In Section IV, we perform
numerical experiments on the proposed pure quantum gradient estimation
algorithm and quantum gradient descent algorithm. In Section V, we combine the
quantum gradient descent algorithm with the VQE algorithm to calculate the
ground state energy of the Heisenberg model to implement the full quantum
variational eigensolver(FQVE). We analyze the errors of the algorithm in
Section VI and conclude with our findings in Section VII.

##  II Pure Quantum Gradient Estimation

The gradient of a function is widely used to locate extrema and offers an
effective solution for certain optimization problems [24]. However, in the
case of a $d$-dimensional variable in a function $f$, calculating the gradient
necessitates at least $d+1$ function evaluations using the equation:

$\frac{\partial f}{\partial
x_{i}}=\frac{f(\boldsymbol{x}-l\boldsymbol{e}_{i})-\boldsymbol{x}}{l}.$ (1)

Here, $\boldsymbol{e}_{i}$ denotes the $i$th normalized basis vector [34]. As
the number of parameters increases, the resources required to compute the
gradient grow, often surpassing the capabilities of classical computers. In
optimization problems, the computation of the function is typically the most
time-consuming task when calculating gradients. Hence, minimizing the number
of function evaluations is critical to improving the efficiency of
optimization algorithms [34, 38].

###  II.1 Quantum Algorithm for Gradient Estimation at Zero

We observe the availability of a fast quantum algorithm for computing
gradients at zero, as proposed in reference [34]. For both classical and
quantum cases, given a sufficiently small value $\boldsymbol{x}$, it holds
that:

$f(\boldsymbol{x})\cong f(\boldsymbol{0})+\boldsymbol{x}\nabla f.$ (2)

For a function of $d$ variables, the classical computation requires evaluating
the function $d+1$ times, whereas the utilization of quantum superposition
allows obtaining the gradient values of all variables using just one function
evaluation. In this quantum algorithm, for $d$ variables, a superposition
state of $n*d$ qubits is created as:

$|\boldsymbol{0}\rangle\stackrel{{\scriptstyle
H}}{{\longrightarrow}}\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta}\rangle.$
(3)

Then, an oracle is constructed as $O_{f}=e^{2\pi i(N/ml)f(\boldsymbol{x})}$,
which is applied to the superposition state resulting in a phase that contains
the function as:

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta}\rangle\stackrel{{\scriptstyle
O_{f}}}{{\longrightarrow}}\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i(N/ml)f(\boldsymbol{x})}|\boldsymbol{\delta}\rangle.$ (4)

Let $x=\frac{l}{N}\boldsymbol{\delta}$ (where $l$ is a sufficiently small
value), perform the transformation in Eq. 2, ignoring the global phase,
resulting in a phase that contains the gradient as:

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i/m[\delta_{1}\nabla f_{1}+\delta_{2}\nabla
f_{2}+\cdot\cdot\cdot+\delta_{d}\nabla f_{d}]}|\boldsymbol{\delta}\rangle.$
(5)

After applying the Inverse Quantum Fourier Transform, a state containing the
gradient can be obtained as:

$\left|\frac{N}{m}(\nabla f)_{1}\right\rangle\left|\frac{N}{m}(\nabla
f)_{2}\right\rangle\cdot\cdot\cdot\left|\frac{N}{m}(\nabla
f)_{d}\right\rangle.$ (6)

Finally, measurement in the computational basis can obtain the $\nabla f$ of
the objective function. In the above equation, $d$ represents the number of
variables in the function, $n$ represents the number of qubits, $N=2^{n}$, $m$
is an order of magnitude estimate of the actual gradient,
$\boldsymbol{\delta}$ are n-bit integers ($0$ to $N-1$), and $l$ is a
sufficiently small parameter [34].

Importantly, this algorithm is limited to computing the gradient of the
objective function at zero, and its efficiency depends on the value of the
parameter $m$. Therefore, it may not be suitable for practical applications,
such as optimization problems.

###  II.2 Pure quantum gradient estimation algorithm

We propose a pure quantum gradient estimation algorithm, as shown in Fig. 2,
that can efficiently estimate gradients at arbitrary points of the objective
function. Our algorithm provides an effective quantum gradient estimation
method for optimization problems.

When approximating the objective function, the Taylor series can be expressed
for an infinitesimal quantity $(x-x_{0})$ as follows: $f(x)\cong
f(x_{0})+\nabla f(x_{0})(x-x_{0})$. In our algorithm, we set
$\boldsymbol{x_{0}=\Delta x}$ (compute the gradient at this point),
$\boldsymbol{x_{1}}=\frac{l}{N}\boldsymbol{\delta}$ (where $l$ is a
sufficiently small parameter, and $x_{1}$ is a sufficiently small quantity),
and $\boldsymbol{x=x_{1}+\Delta x}$. Therefore, we obtain:

$f(\boldsymbol{x})\cong f(\boldsymbol{\Delta x})+\boldsymbol{x_{1}}\nabla
f(\boldsymbol{\Delta x}).$ (7)

Consequently, we only need to construct an oracle containing
$f(\boldsymbol{x})$.

For an objective function with $d$ variables, we first create a superposition
state (using quantum superposition, the gradient can be computed for $d$
variables simultaneously):

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta}\rangle.$
(8)

We then use a separable variable quantum adder [39] to add $\boldsymbol{\Delta
x}$ to the superposition state, resulting in

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta+\Delta
x}\rangle.$ (9)

(a) MAJ module

(b) UMA module

(c) A quantum adder without entanglement

Figure 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.

The purpose of this operation is to shift the quantum state by
$\boldsymbol{\Delta x}$ to compute the gradient at this point. The separable
variable quantum adder is used to add $\boldsymbol{\Delta x}$ to the
superposition state and ensure that the qubits do not become entangled with
each other. For example, the CNOT gate can be considered as an entangled
adder. When the input of qubit $q_{0}$ is
$\frac{\sqrt{2}}{2}\left(|0\rangle+|1\rangle\right)$, and the input of qubit
$q_{1}$ is $|0\rangle$, after passing through the CNOT gate, $q_{0}$ and
$q_{1}$ become entangled, and the output of $q_{1}$ is influenced by $q_{0}$,
making it unsuitable for subsequent calculations(shown in Fig. 4). Therefore,
we use a quantum adder without entanglement(QADD) shown in Fig. 3 in this
case.

Figure 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.

Next, we construct an oracle containing $f(\boldsymbol{x})$ in phase and apply
it to the shifted superposition state above, obtaining:

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta+\Delta
x}\rangle\stackrel{{\scriptstyle
O_{f}}}{{\longrightarrow}}\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i(\frac{N}{ml})f(\boldsymbol{x})}|\boldsymbol{\delta+\Delta x}\rangle.$ (10)

Using the above formula and ignoring the global phase, we obtain the quantum
state containing the gradient information in phase:

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i/m[\delta_{1}(\nabla f)_{1}+\delta_{2}(\nabla
f)_{2}+\cdot\cdot\cdot+\delta_{d}(\nabla f)_{d}]}|\boldsymbol{\delta+\Delta
x}\rangle.$ (11)

To extract the phase information, we need to shift the superposition state
back to the initial position, so we need a separable quantum subtractor(shown
in Fig. 5), which gives:

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i/m[\delta_{1}(\nabla f)_{1}+\delta_{2}(\nabla
f)_{2}+\cdot\cdot\cdot+\delta_{d}(\nabla f)_{d}]}|\boldsymbol{\delta}\rangle.$
(12)

Figure 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\rangle$. Then,
use a quantum adder to add $|1\rangle$ 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}\rangle$ in the value qubits.

Finally, applying the Inverse Quantum Fourier Transform yields the quantum
state containing the gradient information:

$\left|\frac{N}{m}(\nabla f(\boldsymbol{\Delta
x}))_{1}\right\rangle\cdot\cdot\cdot\left|\frac{N}{m}(\nabla
f(\boldsymbol{\Delta
x}))_{i}\right\rangle\cdot\cdot\cdot\left|\frac{N}{m}(\nabla
f(\boldsymbol{\Delta x}))_{d}\right\rangle.$ (13)

where the subscription $i$ refers to the $i$-th component of the gradient,
which is a vector. In the above formula, $d$ represents the number of
variables in the function, $n$ represents the number of qubits, $N=2^{n}$ ,
$m$ is an estimate of the order of magnitude of the actual gradient and can be
taken as $2^{n}$ , and $l$ is an extremely small parameter.

1

Input:

$f(\boldsymbol{x})$: A objective function for which the gradient is to be
computed;

$m$: One parameter estimates the order of magnitude of the gradient;

$n$: The number of qubits required to encode each variable;

$N$: $N=2^{n}$ ;

$d$: The quantity of variables;

$l$: A parameter that is small enough;

$\boldsymbol{\Delta x}$: The point at which the gradient wants to be
estimated;

$\boldsymbol{x_{1}}$: $\boldsymbol{x_{1}}=\frac{l}{N}\boldsymbol{\delta}$;

$\boldsymbol{x}$: $\boldsymbol{x}=\boldsymbol{x_{1}+\Delta x}$;

2

3Register: Utilize $n$-qubit input registers $|x_{1}\rangle$, $|x_{2}\rangle$,
…, $|x_{d}\rangle$, with each qubit initialized to $|\boldsymbol{0}\rangle$;

4Init: Apply a Hadamard gate to each qubit in the input registers, resulting
in:  $|\boldsymbol{0}\rangle\stackrel{{\scriptstyle
H}}{{\longrightarrow}}\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta}\rangle.$
(14)

5Add: Apply a quantum adder with separable variables to add
$\boldsymbol{\Delta x}$ to the superposition state:
$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta}\rangle\stackrel{{\scriptstyle
QADD}}{{\longrightarrow}}\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta+\Delta
x}\rangle.$ (15)

6Oracle: Construct an oracle $O_{f}=e^{2\pi i(N/ml)f(\boldsymbol{x})}$ that
contains the function $f(\boldsymbol{x})$ in its phase. Apply the oracle to
the input registers, resulting in:
$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta}+\Delta
x\rangle\stackrel{{\scriptstyle
O_{f}}}{{\longrightarrow}}\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i(\frac{N}{ml})f(\boldsymbol{x})}|\boldsymbol{\delta+\Delta x}\rangle.$ (16)
Ignoring the global phase, the input registers are now approximately in the
state:  $\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i/m[\delta_{1}\nabla f_{1}+\delta_{2}\nabla
f_{2}+\cdot\cdot\cdot+\delta_{d}\nabla f_{d}]}|\boldsymbol{\delta+\Delta
x}\rangle.$ (17)

7Sub: After applying a quantum subtractor to subtract $\boldsymbol{\Delta x}$
from the superposition state, the input registers are left in the state:
$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i/m[\delta_{1}(\nabla f)_{1}+\delta_{2}(\nabla f)_{2}+\cdots+\delta_{d}(\nabla
f)_{d}]}|\boldsymbol{\delta}\rangle.$ (18)

8IQFT: Apply the Inverse Quantum Fourier Transform (IQFT) to the input
registers, the quantum state can be expressed as:  $\left|\frac{N}{m}(\nabla
f(\boldsymbol{\Delta
x}))_{1}\right\rangle\cdot\cdot\cdot\left|\frac{N}{m}(\nabla
f(\boldsymbol{\Delta
x}))_{i}\right\rangle\cdot\cdot\cdot\left|\frac{N}{m}(\nabla
f(\boldsymbol{\Delta x}))_{d}\right\rangle.$ (19)

9Measure: Measure the quantum state obtained after applying IQFT in the
computational basis to obtain the components of $\nabla f$;

Result: A quantum state obtains the components of $\nabla f$.

Algorithm 1 Pure quantum gradient estimation algorithm

In the above process, the gradient estimation is for the case where
$\boldsymbol{\Delta x}$ is positive. For the case where $\boldsymbol{\Delta
x}$ is negative, we can simply subtract a positive value $\boldsymbol{\Delta
x^{+}}$ (by adding the two’s complement of $\boldsymbol{\Delta x}$ using a
quantum adder) from the initial superposition state, resulting in

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}|\boldsymbol{\delta-\Delta
x^{+}}\rangle,$ (20)

apply the oracle to add the gradient information to the phase:

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i/m[\delta_{1}(\nabla f)_{1}+\delta_{2}(\nabla
f)_{2}+\cdot\cdot\cdot+\delta_{d}(\nabla
f)_{d}]}\left|\boldsymbol{\delta-\Delta x^{+}}\right\rangle,$ (21)

and then add this positive value $\boldsymbol{\Delta x^{+}}$:

$\frac{1}{\sqrt{N^{d}}}\sum_{\boldsymbol{\delta}=0}^{N-1}e^{2\pi
i/m[\delta_{1}(\nabla f)_{1}+\delta_{2}(\nabla
f)_{2}+\cdot\cdot\cdot+\delta_{d}(\nabla f)_{d}]}|\boldsymbol{\delta}\rangle.$
(22)

Finally, the Inverse Quantum Fourier Transform can be applied to obtain a
quantum state that contains the gradient information at the negative value of
$\boldsymbol{\Delta x}$:

$\left|\frac{N}{m}(\nabla f(\boldsymbol{\Delta
x}))_{1}\right\rangle\cdot\cdot\cdot\left|\frac{N}{m}(\nabla
f(\boldsymbol{\Delta
x}))_{i}\right\rangle\cdot\cdot\cdot\left|\frac{N}{m}(\nabla
f(\boldsymbol{\Delta x}))_{d}\right\rangle.$ (23)

During the derivation presented above, we note that the evolved gradient
should have the same sign as the parameter $m$. When $m$ is fixed to be
$2^{n}$, the gradient obtained from the algorithm is positive. However, when
the actual gradient is negative, due to the periodicity of the exponential
function in the Inverse Quantum Fourier Transform, for a negative integer $k$
[34],

$\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}e^{-2\pi
ij/N|k|}|j\rangle\longrightarrow|N-|k|\rangle,$ (24)

therefore,

$\frac{1}{\sqrt{N}}\sum_{\delta=0}^{N-1}e^{-2\pi i|\frac{\nabla
f}{m}|\delta}|\delta\rangle\longrightarrow\left|N-|\frac{N}{m}\nabla
f|\right\rangle.$ (25)

Thus, the algorithm can also obtain a quantum state related to the negative
gradient, which, at $m=2^{n}$, can be understood as the two’s complement of
the negative gradient without the sign qubit.

##  III Quantum Gradient Descent Algorithm

We have implemented quantum gradient descent using the pure quantum gradient
estimation algorithm. In the classical gradient descent process [24, 19, 40],
$x^{k+1}_{i}=x^{k}_{i}-\alpha\nabla f(x^{k}_{i})$, where $\alpha$ is the
learning rate, $x^{k}_{i}$ is the $k$th iteration of the $i$th variable. In
our quantum implementation, for a positive component $\nabla f(x^{k}_{i})$ of
the gradient, we can obtain
$|x^{k+1}_{i}\rangle=\left|x^{k}_{i}-\alpha(\frac{N}{m}\nabla
f)\right\rangle$, which can be understood as normal gradient descent, where we
subtract a positive number from $x_{i}^{k}$. For a negative component $\nabla
f(x^{k}_{i})$ of the gradient, we can obtain
$\left|x^{k+1}_{i}\right\rangle=\left|x^{k}_{i}-\alpha(N-|\frac{N}{m}\nabla
f|)\right\rangle$. This can be interpreted as subtracting the two’s complement
notation of the negative gradient from $x_{i}^{k}$. In other words, adding the
absolute value of the negative number. Thus, we have
$\left|x^{k+1}_{i}\right\rangle=\left|x^{k}_{i}+\alpha(|\nabla
f(x^{k}_{i})|)\right\rangle$, which is no different from normal gradient
descent. Therefore, whether our algorithm obtains the true gradient or the
two’s complement notation of the true gradient, it does not affect the
calculation process of gradient descent.

In the gradient descent formula $x^{k+1}_{i}=x^{k}_{i}-\alpha\nabla
f(x^{k}_{i})$, quantum multiplication is required, which can be challenging
due to the large number of qubits needed for constructing a quantum
multiplier. Therefore, in the case of limited qubits, we propose a hybrid
approach that combines classical multiplication with pure quantum gradient
estimation in the gradient descent process. Specifically, we use the pure
quantum gradient estimation algorithm to estimate the gradient value of the
objective function, and then update the parameters using classical methods.
However, due to the introduction of classical computation, we need to perform
measurements after each gradient estimation and update the parameters using
classical computers, which may affect the calculation speed to some extent. In
the long run, we expect the emergence of large-scale fault tolerant quantum
computers, which will enable our quantum gradient descent algorithm to
complete calculations without repeated measurements and improve its
performance.

Analyzing the results of numerical simulations in Section IV.3, we found that
although the algorithm partially uses classical computers, it can still
effectively find the optimal value of the objective function, which can be
used in practical applications.

##  IV Results

We conducted numerical simulations of the pure quantum gradient estimation
algorithm and quantum gradient descent algorithm using Qiskit [41]. Our
results showed that these algorithms were effective in estimating the
gradients of the objective function, finding the optimal values of the
objective function.

###  IV.1 Gradient estimation at point zero

In this study, we used Qiskit [41] to numerically simulate the pure gradient
ascent. We encoded the objective function $f(x)=1.3x$ in the ground state
using four qubits, with two qubits encoding the decimal values. We set the
parameters $N=4$ and $m=4$ and conducted 1000 experiments using the
$qasm_{s}imulator$ simulator. From Fig. 6,

(a) The results of using the pure quantum gradient estimation algorithm on
Qiskit to estimate the gradient of the objective function $f(x)=1.3x$ at zero

(b) Quantum circuit diagram for estimating the gradient of the target function
$f=1.3x$ using the pure quantum gradient estimation algorithm on Qiskit

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

we observed that the state $|\frac{N}{m}\nabla f\rangle$ had a probability of
$85.2\%$ of being in the state $|0101\rangle$, which corresponds to an
estimated gradient of $1.25$ for the objective function. The small difference
between the estimated and actual gradients suggests that the algorithm was
successful in estimating the objective function’s gradient.

###  IV.2 Gradient estimation at any point

In this section, we encoded the objective function
$f(x_{1},x_{2})=0.1(x_{1}+x_{2}^{2})^{2}+0.1(1+x_{2}^{2})^{2}$ in the ground
state using four qubits, with two qubits encoding the decimal values for each
variable. It transforms a binary string $x$ of length $n$ into a quantum state
$|x\rangle=|i_{x}\rangle$ with $n$ qubits, where $|i_{x}\rangle$ is the
computational basis state. The parameters $N=4$ and $m=4$ were used, and we
conducted 1000 experiments using the $qasm\\_simulator$ [41]. The gradients of
the objective function at $(1,1.5)$, $(-2,-1.25)$, $(-2,1.25)$, and $(1,-1.5)$
are shown in Fig. 7.

(a) Experimental result of the objective function at $(1,1.5)$

(b) Experimental result of the objective function at $(-2,-1.25)$

(c) Experimental result of the objective function at $(-2,1.25)$

(d) Experimental result of the objective function at $(1,-1.5)$

Figure 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_{2}^{2})^{2}+0.1(1+x_{2}^{2})^{2}$ at various
initial points.

The results indicate that the final quantum states for each point had a
probability of $100\%$ of being in the state $|00010110\rangle$, $76.1\%$ of
being in the state $|00111000\rangle$, $76\%$ of being in the state
$|00111000\rangle$, and $100\%$ of being in the state $|00010110\rangle$,
respectively. Combining with symbolic analysis, the estimated gradient values
for each point were $(-0.25,1.5)$, $(-0.75,-2)$, $(-0.75,2)$, and
$(-0.25,-1.5)$. The small differences between the estimated and actual
gradient values suggest that the quantum gradient descent algorithm
successfully estimated the gradients of the objective function.

###  IV.3 Numerical results of gradient descent algorithm

In this study, we utilized the $qasm\\_simulator$ [41] to implement gradient
descent. Our numerical experiments demonstrate that the pure quantum gradient
estimation algorithm-based quantum gradient descent algorithm can effectively
locate the extremum of the objective function. This provides a firm foundation
for applying quantum gradient descent to optimization problems.

For the objective function
$f(x_{1},x_{2})=0.1(x_{1}+x_{2}^{2})^{2}+0.1(1+x_{2}^{2})^{2}$, Fig. 8 shows
the iteration process of quantum gradient descent from different starting
points.

(a) The gradient descent process of the objective function starting at the
starting point $(0.7,1.6)$

(b) The gradient descent process of the objective function starting at the
starting point $(1,-1.6)$

(c) The gradient descent process of the objective function starting at the
starting point $(-2,1)$

(d) The gradient descent process of the objective function starting at the
starting point $(-2,-1.5)$

Figure 8: The results of quantum gradient descent of the objective function
$f(x_{1},x_{2})=0.1(x_{1}+x_{2}^{2})^{2}+0.1(1+x_{2}^{2})^{2}$ at various
starting points using this quantum gradient descent algorithm on Qiskit

All four gradient descent processes used four qubits (including two qubits
encoding decimals) to encode data. The step size $\alpha=0.05$ was used in
Fig. 8(a) and Fig. 8(b), where the starting point of Fig. 8(a) was
$(x_{1},x_{2})=(0.7,1.6)$ and the extremum found by the extended algorithm was
$(x_{1}^{{}^{\prime}},x_{2}^{{}^{\prime}})=(0.825,0.994)$, with an actual
gradient of $(-0.033,0.06)$. The starting point of Fig. 8(b) was
$(x_{1},x_{2})=(1,-1.6)$, and the extremum found by the extended algorithm was
$(x_{1}^{{}^{\prime}},x_{2}^{{}^{\prime}})=(1.09,-1.05)$, with an actual
gradient of $(-0.0025,-0.048)$.

The step size $\alpha=0.3$ was used in Fig. 8(c) and Fig. 8(d), where the
starting point of Fig. 8(c) was $(x_{1},x_{2})=(-2,1)$, and the extremum found
by the extended algorithm
was$(x_{1}^{{}^{\prime}},x_{2}^{{}^{\prime}})=(0.14,0.625)$, with an actual
gradient of $(-0.05,-0.09)$. The starting point of Fig. 8(d) was
$(x_{1},x_{2})=(-2,-1.5)$, and the extremum found by the extended algorithm
was $(x_{1}^{{}^{\prime}},x_{2}^{{}^{\prime}})=(0.2875,-0.75)$, with an actual
gradient of $(-0.055,0.04875)$.

The actual gradients of the extremum points found by the quantum gradient
descent algorithm based on pure quantum gradient estimation in all four
processes were very small, indicating that the gradient at those points could
be approximated as zero. Therefore, it can be concluded that this algorithm
successfully found the extremum of the objective function from different
starting points.

##  V Full Quantum Variational Eigensolver

Variational quantum eigensolver (VQE) is a quantum-classical hybrid algorithm
with enormous potential for application on NISQ quantum devices [13, 42, 43,
44, 18]. The objective of VQE is to find the ground state and ground state
energy of a given Hamiltonian $H$. In classical computational physics, the
variational method is commonly used to estimate the ground state energy of a
given Hamiltonian $H$: parameterize the wave function as
$|\psi\rangle=|\psi(\boldsymbol{\theta})\rangle$, update $\boldsymbol{\theta}$
to minimize the expectation value
$\langle\psi(\boldsymbol{\theta})|H|\psi(\boldsymbol{\theta})\rangle$ until
convergence.On quantum computers, VQE parameterizes the wavefunction with a
quantum circuit $U(\boldsymbol{\theta})$ applied to the initial state
$|\boldsymbol{0}\rangle=|0\rangle^{\otimes n}$, and then optimizes
$\boldsymbol{\theta}$ to minimize the expectation value
$E(\boldsymbol{\theta})=\langle\boldsymbol{0}|U^{\dagger}(\boldsymbol{\theta})HU(\boldsymbol{\theta})|\boldsymbol{0}\rangle$,
until convergence [18].

Gradient-based gradient descent is a commonly used optimization method in the
VQE. In VQE, the gradient can be directly calculated using the parameter-shift
rule [45, 46]:

$\frac{\partial E(\boldsymbol{\theta})}{\partial\theta_{i}}=(\langle
H\rangle_{\boldsymbol{\theta}_{i}^{+}}-\langle
H\rangle_{\boldsymbol{\theta}_{i}^{-}})/2,$ (26)

where
$\boldsymbol{\theta}_{i}^{\pm}=\boldsymbol{\theta}\pm\boldsymbol{e}_{i}$,
$\boldsymbol{e}_{i}$ is the ith unit vector in the parameter space [18].
Hardware-efficient ansatz [43], unitary coupled clustered ansatz [43, 47], and
Hamiltonian variational ansatz [48, 49] are common choices for
$U(\boldsymbol{\theta})$.

This article applies the quantum gradient descent algorithm to VQE to find the
ground state energy of the 2-qubit Heisenberg model and compares it with the
gradient-based traditional gradient descent algorithm. The Hamiltonian can be
written as:

$H_{h}=X_{1}\otimes X_{2}+Y_{1}\otimes Y_{2}+Z_{1}\otimes Z_{2},$ (27)

where $X_{i},Y_{i},Z_{i}$ are the Pauli operators on the $i$th qubit. The
ansatz is shown in Fig. 9, the initial parameter $\theta$ is a random number
between $0$ and $\pi$, and the learning rate $\alpha=0.25$.

Figure 9: The ansatz for 2-qubit VQE. $\theta_{1},\theta_{2}$ are the
parameters to be optimized.

1

Input:

$\boldsymbol{\theta}$: randomly initialized parameters;

$H$: hamiltonian of the model;

$R$: number of iterations;

2

3Register: each qubit is initialized to $|\boldsymbol{0}\rangle$;

4if  _$k <R$ or the objective function does not converge_ then

5 Anstaz: generate a quantum circuit using the parameters
$\boldsymbol{\theta}$: $U_{\boldsymbol{\theta}}^{k}$;

6 Circuit: generate a circuit
$\left|\psi_{\boldsymbol{\theta}}^{k}\right\rangle$ using the ansatz
$U_{\boldsymbol{\theta}}^{k}$:
$\left|\psi_{\boldsymbol{\theta}}^{k}\right\rangle=U_{\boldsymbol{\theta}}^{k}|\boldsymbol{0}\rangle;$
(28)

7 Objective function: the objective function can be expressed as
$L^{k}_{\boldsymbol{\theta}}=\left\langle\psi_{\boldsymbol{\theta}}^{k}\right|H\left|\psi_{\boldsymbol{\theta}}^{k}\right\rangle$;

8 Optimization: compute the gradient of the parameters $\boldsymbol{\theta}$
using the pure quantum gradient estimation algorithm, and update
$\boldsymbol{\theta}$ using the quantum gradient descent algorithm,
$\boldsymbol{\theta}^{k+1}=\boldsymbol{\theta}^{k}-\alpha\nabla
f(\boldsymbol{\theta}^{k});$ (29)

9else

10 Break;

11 end if

12

Result: ground state energy of the model.

Algorithm 2 Full Quantum Variational Eigensolver

Specifically, we replace the traditional gradient descent algorithm based on
gradients with the pure quantum gradient estimation algorithm and quantum
gradient descent algorithm to obtain the full quantum variational
eigensolver(FQVE).

If we want to implement the FQVE algorithm on a fully quantum circuit and
introduce our pure quantum gradient estimation algorithm, as shown in Eq. 10,
we need to construct an oracle on the phase that contains the objective
function, that is, we need to construct such an oracle:

$O_{f}:e^{2\pi
i(\frac{N}{ml})\langle\psi_{\boldsymbol{\theta}}|H_{h}|\psi_{\boldsymbol{\theta}}\rangle}.$
(30)

We notice that the problem can be addressed using the techniques, such as
block encoding technique[36, 50], Hamiltonian simulation[36, 51], described in
Appendix A. However, even for small-scale model problems mentioned in this
paper, the method in Appendix A requires a large number of qubits (more than
50 qubits), which makes it challenging to perform real experiments on current
quantum computers or simulators. Therefore, similar to the general VQE, in
this paper, we use the conventional VQE method to obtain the expected value of
the Hamiltonian and then optimize it using our pure quantum gradient descent
algorithm. Nevertheless, our FQVE algorithm performs similarly to the general
VQE algorithm on this problem. Furthermore, we look forward to the emergence
of large-scale quantum computers, where our FQVE algorithm has an advantage
over the general VQE algorithm in theory, running on fully quantum computers.

We encode the parameters using four qubits, with two qubits for decimal
representation. We compare the performance of the method to the classical
gradient descent algorithm, and present the raw data results in Fig. 10.

Figure 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.

Our experiments demonstrate that, after sufficient iterations, both the
quantum and classical gradient descent algorithms can find the ground state
energy of this model. Interestingly, we observe that the quantum gradient
descent algorithm performs almost as well as the classical gradient descent
algorithm for small-scale parameters in VQE. However, for large-scale
parameters ($N$), the quantum gradient descent algorithm (complexity $O(1)$)
has a significant advantage over the classical gradient descent algorithm
(complexity $O(N)$) in terms of complexity.

##  VI The Impact of Numerical Errors

In Section IV, we conducted numerical experiments and observed that our
algorithm produced a gradient of $1.25$ for the objective function $f=1.3x$,
encoded with two qubits to represent the decimal number. As illustrated in
Fig. 11, increasing the number of qubits used for encoding the decimal numbers
improved the precision of the algorithm’s output for the same objective
function.

Figure 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.

This is because the precision of numerical representation in a quantum state
increases with the number of qubits used for encoding the decimal numbers.
Therefore, increasing the number of qubits used for encoding decimal numbers
could improve the precision of the algorithm, given sufficient computing
resources.

Furthermore, we noted that the parameter $m$ is another factor that influences
the estimation of the gradient. The parameter $m$ provides an approximate
estimate of the magnitude of the actual gradient, which is typically larger
than the actual gradient. If $m$ is smaller than the actual gradient, the
quantum state $\left|\frac{N}{m}\nabla f(\boldsymbol{\Delta x})\right\rangle$
obtained by the algorithm will be larger than the value $N$ that can be
represented by $n$ qubits.

Figure 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.

And as shown in Fig. 12, for the objective function $f=1.3x$, the estimation
provided by the algorithm becomes more accurate as the value of $m$ approaches
the actual gradient.

##  VII conclusion

In this work, we propose an effective pure quantum gradient estimation
algorithm for estimating numerical gradients. The algorithm has a theoretical
computational complexity of $O(1)$[34], which provides significant advantages
over classical algorithm with a computational complexity of $O(d)$. Numerical
simulation results using Qiskit[41] demonstrate that the algorithm can
successfully estimate the gradient of a complex objective function. Our error
analysis shows that increasing the number of encoding quantum bits can improve
the accuracy of the algorithm to some extent. Building upon this algorithm, we
implement a quantum gradient descent algorithm, which, despite being limited
by hardware qubit counts, performs well in finding the extremum of a
relatively complex objective function, as demonstrated by our numerical
simulations. When solving for the ground state energy of a small-scale
Hamiltonian [18, 14], the performance of our full quantum variational
eigensolver is comparable to that of variational quantum eigensolver. However,
for large-scale Hamiltonian , our algorithm has a significant theoretical
advantage. These results suggest that our algorithm provides a more efficient
quantum optimization method than classical optimization algorithm, which
theoretically can improve convergence speed and increase the precision of
optimization problems.

## Acknowledgement

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

##  Appendix A Converting a probability oracle to a phase oracle

To combine our quantum gradient descent algorithm with VQE to form a new full
quantum variational eigensolver, it is necessary to put the objective function
$L_{\boldsymbol{\theta}}=\langle\psi_{\boldsymbol{\theta}}|H_{h}|\psi_{\boldsymbol{\theta}}\rangle$
into the phase as shown in Eq. 10 [36], that is, we need to construct such an
oracle:

$O_{f}:e^{2\pi
i(\frac{N}{ml})\langle\psi_{\boldsymbol{\theta}}|H_{h}|\psi_{\boldsymbol{\theta}}\rangle}.$
(31)

We note that the objective function can be transformed into a probability
oracle, and then the block encoding technique can be used to transform this
probability oracle into a block encoding of a diagonal matrix containing
probabilities[36, 50]. Next, the Hamiltonian simulation can be used to
implement putting this probability oracle into the phase[51]. Then, our
proposed pure quantum gradient estimation algorithm can be used to estimate
the gradient of the objective function.

Regarding the Hamiltonian of the model $H_{h}=\sum_{j=1}^{M}a_{j}U_{j}$, we
construct
$\text{prepareW:}|0\rangle\longrightarrow\sum_{j}\sqrt{a_{j}}|j\rangle$ and
$\text{selectH:}=\sum_{j}|j\rangle\langle j|\otimes U_{j}$. Under the
assumption that $\sum_{j}a_{j}=1$ note that

$\displaystyle\langle
0|\langle\psi_{\boldsymbol{\theta}}|\text{prepareW}^{\dagger}(\text{selectH})\text{perpareW}|0\rangle|\psi_{\boldsymbol{\theta}}\rangle$
(32) $\displaystyle=\sum_{j}\sum_{k}\sqrt{a_{j}a_{k}}\langle
k|j\rangle\otimes\langle\psi_{\boldsymbol{\theta}}|U_{j}|\psi_{\boldsymbol{\theta}}\rangle$
$\displaystyle=\left\langle\psi_{\boldsymbol{\theta}}\right|\sum_{j}a_{j}U_{j}\left|\psi_{\boldsymbol{\theta}}\right\rangle$
$\displaystyle=\langle\psi_{\boldsymbol{\theta}}|H_{h}|\psi_{\boldsymbol{\theta}}\rangle.$

We can use a technique similar to the Hadamard test as shown in Fig. 13 to
transform the objective function into a probability[36].

Figure 13: Quantum circuit diagram for converting the ground state energy of
the model into probability. Here, $|0\rangle$ is an auxiliary qubit,
$|\psi_{\boldsymbol{\theta}}\rangle$ 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-\langle\psi_{\boldsymbol{\theta}}|U|\psi_{\boldsymbol{\theta}}\rangle)/2$
for the outcome to be 1 on the auxiliary qubit.

We can obtain: $HC(U)H|0\rangle|\psi_{\boldsymbol{\theta}}\rangle$, where
$C(U)$ is a controlled unitary operation,then we can obtain:

$\displaystyle\frac{H(|0\rangle|\psi_{\boldsymbol{\theta}}\rangle+|1\rangle
U|\psi_{\boldsymbol{\theta}}\rangle)}{\sqrt{2}}$ (33)
$\displaystyle=|0\rangle\left(\frac{(1+U)|\psi_{\boldsymbol{\theta}}\rangle}{2}\right)+|1\rangle\left(\frac{(1-U)|\psi_{\boldsymbol{\theta}}\rangle}{2}\right).$

Therefore, by measuring the first qubit, we obtain a probability of
$(1-\langle\psi_{\boldsymbol{\theta}}|U|\psi_{\boldsymbol{\theta}}\rangle)/2$
for the outcome to be 1. The combination with Eq. 32 leads to a probability of
$(1-\langle\psi_{\boldsymbol{\theta}}|H_{h}|\psi_{\boldsymbol{\theta}}\rangle)/2$
for the outcome to be 1[36]. Thus we obtain a probability oracle $O_{p}$ for
the expected ground state energy of the model, resulting in:

$O_{p}|0\rangle|\psi_{\boldsymbol{\theta}}\rangle\longrightarrow\sqrt{p}|1\rangle|\psi_{0}\rangle+\sqrt{1-p}|0\rangle|\psi_{1}\rangle,$
(34)

where $|\psi_{0}\rangle$ and $|\psi_{1}\rangle$ are arbitrar quantum states,
and
$p=(1-\langle\psi_{\boldsymbol{\theta}}|H_{h}|\psi_{\boldsymbol{\theta}}\rangle)/2$.

Then we use the block encoding technique to transform this probability oracle
into a block encoding of a diagonal matrix containing probabilities. Due to

$(\langle\boldsymbol{0}|\otimes I)(O_{p}^{\dagger}(Z\otimes
I)O_{p})(|\boldsymbol{0}\rangle\otimes I)=\text{diag}(1-2p),$ (35)

$(O_{p}^{\dagger}(Z\otimes I)O_{p})$ is a block encoding of a diagonal matrix
with diagonal elements of $(1-2p)$[50]. Finally, we use the Hamiltonian
simulation technique[51] to transfer this block encoding into the phase to
implement the phase oracle in Eq. 10. Then we use our proposed pure quantum
gradient estimation algorithm to estimate the gradient of the objective
function.

By utilizing the various techniques mentioned above, we can put the objective
function in VQE into the phase of our proposed pure quantum gradient
estimation algorithm, resulting in a full quantum variational eigensolver.

## References

  * [1] E. Farhi and J. Goldstone, A quantum approximate optimization algorithm, arXiv:1411.4028.
  * [2] E. Farhi, J. Goldstone, and et al, Quantum computation by adiabatic evolution, arXiv:quant-ph/0001106.
  * G.G.Guerreschi and A.Y.Matsuura [2019] G.G.Guerreschi and A.Y.Matsuura, Qaoa for max-cut requires hundreds of qubits for quantum speed-up, Scientific Reports 6 (2019).
  * Nielsen [2015] M. A. Nielsen,  _Neural Networks and Deep Learning_ (Determination Press, 2015).
  * [5] M. Schuld and I. Sinayskiy, The quest for a quantum neural network, arXiv:1408.7005.
  * Dunjko  _et al._ [2016] V. Dunjko, J. M. Taylor, and H. J. Briegel, Quantum-enhanced machine learning, Physical Review Letters 117 (2016).
  * [7] T. Sakuma, Application of deep quantum neural networks to finance, arXiv:2011.07319.
  * [8] R. Orus, S. Mugel, and E. Lizaso, Quantum computing for finance: overview and prospects, arXiv:1807.03890v2.
  * J.Egger  _et al._ [2020] D. J.Egger, C. Gambella, and et al, Quantum computing for finance: State of the art and future prospects, IEEE Transactions on Quantum Engineering (2020).
  * R.P.Feynmen [1939] R.P.Feynmen, Forces in molecules, Physical Review Letters 56 (1939).
  * Fedorov  _et al._ [2021] D. A. Fedorov, M. J. Otten, S. K. Gray, and Y. Alexeev, Ab initio molecular dynamics on quantum computers, The Journal of Chemical Physics 154 (2021).
  * Gandhi  _et al._ [2014] V. Gandhi, G. Prasad, and et al, Quantum neural network-based eeg filtering for a brain–computer interface, IEEE Transactions on Neural Networks and Learning Systems 25 (2014).
  * [13] A. Peruzzo, J. McClean, P. Shadbolt, and et al, A variational eigenvalue solver on a quantum processor, arXiv:1304.3061.
  * Wei  _et al._ [2020] S. Wei, H. Li, and G. Long, A full quantum eigensolver for quantum chemistry simulations, Research 2020 (2020).
  * [15] S. Ruder, An overview of gradient descent optimization algorithms, arXiv:1609.04747.
  * McClean  _et al._ [2016] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms, New Journal of Physics 18 (2016).
  * [17] M. Cerezo, A. Arrasmith, R. Babbush, and et al, Variational quantum algorithms, arXiv:2012.09265.
  * Hou  _et al._ [2021] 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, and B. Zeng, Spinq gemini: a desktop quantum computing platform for education and research, EPJ Quantum Technology (2021).
  * Yuan  _et al._ [2019] G. Yuan, T. Li, and W. Hu, A conjugate gradient algorithm and its application in large-scale optimization problems and image restoration, Journal of Inequalities and Applications 2019 (2019).
  * BROYDEN [1970] C. G. BROYDEN, The Convergence of a Class of Double-rank Minimization Algorithms 1. General Considerations, IMA Journal of Applied Mathematics 6, 76 (1970), http://oup.prod.sis.lan/imamat/article-pdf/6/1/76/2233756/6-1-76.pdf .
  * Fletcher [1970] R. Fletcher, A new approach to variable metric algorithms, The Computer Journal 13, 317 (1970), http://oup.prod.sis.lan/comjnl/article-pdf/13/3/317/988678/130317.pdf .
  * Goldfarb [1970] D. Goldfarb, A family of variable-metric methods derived by variational means, Mathematics of Computing 24, 23 (1970).
  * Shanno [1970] D. F. Shanno, Conditioning of quasi-Newton methods for function minimization, Mathematics of Computing 24, 647 (1970).
  * Gao  _et al._ [2021] P. Gao, K. Li, S. Wei, J. Gao, and G. Long, Quantum gradient algorithm for general polynomials, Physical Review A 103 (2021).
  * Nielsen and Chuang [2010] M. Nielsen and I. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, 2010).
  * DiVincenzo [1995] D. P. DiVincenzo, Quantum computation, Science 270, 255 (1995).
  * John [2018] P. John, Quantum computing in the nisq era and beyond, Quantum 2, 79 (2018).
  * Shor [1994] P. W. Shor, Algorithms for quantum computation:discrete logarithms and factoring (Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994) pp. 124–134.
  * Monz  _et al._ [2016] T. Monz, D. Nigg, E. A. Martinez, and et al, Realization of a scalable shor algorithm, Science 351 (2016).
  * Grover [1997] L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Physical Review Letters 79, 325 (1997).
  * G.L.Long [2001] G.L.Long, Grover algorithm with zero theoretical failure rate, Physics Review A 64 (2001).
  * Harrow  _et al._ [2009] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103 (2009).
  * Duan  _et al._ [2020] B. Duan, J. Yuan, C.-H. Yu, and et al, A survey on hhl algorithm: From theory to application in quantum machine learning, Physics Review A 384 (2020).
  * P.Jordan [2005] S. P.Jordan, Fast quantum algorithm for numerical gradient estimation, Physical Review Letters 95 (2005).
  * [35] R. Wiersema, D. Lewis, D. Wierichs, J. Carrasquilla, and N. Killoran, Here comes the su(n): multivariate quantum gates and gradients, arXiv:2303.11355.
  * Gilyén [2019] A. Gilyén, Optimizing quantum optimization algorithms via faster quantum gradient computation (Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, 2019) pp. 1425–1444.
  * Li [2005] J. Li, General explicit difference formulas for numerical differentiation, Journal of Computational and Applied Mathematics 183, 29 (2005).
  * Press  _et al._ [1992] W. H. Press, S. A. Teukolsky, and W. T. Vetterling,  _Numerical Recipes in C_ (Cambridge University Press, 1992).
  * Li and Dou [2021] Y. Li and M. Dou,  _A quantum addition operation method, device, electronic device and storage medium_ , Origin Quantum (2021).
  * Zhu  _et al._ [1997] C. Zhu, R. H.Byrd, P. Lu, and J. Nocedal, L-bfgs-b: Fortran subroutines for large-scale bound constrained optimization, ACM Transactions on Mathematical Software 23 (1997).
  * tA v  _et al._ [2021] A. tA v, M. S. ANIS, Abby-Mitchell, and et al, Qiskit: An open-source framework for quantum computing (2021).
  * M.Parrish  _et al._ [2019] R. M.Parrish, E. G.Hohenstein, and et al, Quantum computation of electronic transitions using a variational quantum eigensolver, Physical Review Letters 122 (2019).
  * Kandala  _et al._ [2017] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017).
  * Hempel  _et al._ [2018] 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, and C. F. Roos, Quantum chemistry calculations on a trapped-ion quantum simulator, Physics Review X 8, 031022 (2018).
  * K.Mitarai  _et al._ [2018] K.Mitarai, M.Negoro, M.Kitagawa, and K.Fujii, Quantum circuit learning, Physics Review A 98, 032309 (2018).
  * Schuld  _et al._ [2019] M. Schuld, V. Bergholm, and N. K. Christian Gogolin, Josh Izaac, Evaluating analytic gradients on quantum hardware, Physics Review A 99, 032331 (2019).
  * Lee  _et al._ [2018] J. Lee, W. J. Huggins, M. Head-Gordon, and K. B. Whaley, Generalized unitary coupled cluster wave functions for quantum computation, Journal of Chemical Theory and Computation 15, 311 (2018).
  * Wecker  _et al._ [2015] D. Wecker, M. B.Hastings, and M. Troyer, Progress towards practical quantum variational algorithms, Physics Review A 92, 042303 (2015).
  * Wiersema  _et al._ [2020] R. Wiersema, C. Zhou, Y. de Sereville, J. F. Carrasquilla, Y. B. Kim, and H. Yuen, Exploring entanglement and optimization within the hamiltonian variational ansatz, PRX Quantum 1, 020319 (2020).
  * [50] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond:exponential improvements for quantum matrix arithmetics, arXiv:1806.01838.
  * [51] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, arXiv:1610.06546.


A One-Line Proof of Leversha’s “Quartet of Isogonal Conjugates” Theorem

Shalosh B. EKHAD

In [L], Gerry Leversha spent quite a few pages, using human ingenuity and lots
of previous knowledge, to prove the following elegant theorem (see [W] for the
definition of Isogonal Conjugate).

Leversha’s Quartet Theorem ([L]): Let $ABCD$ be a quadrilateral which is not
cyclic. Let $A^{*}$ be the isogonal conjugate of $A$ with respect to $\Delta
BCD$, and similarly let $B^{*}$, $C^{*}$, $D^{*}$ the isogonal conjugates of
$\Delta ADC$, $\Delta ABD$, $\Delta ABC$ respectively. Then $A$,$B$,$C$, and
$D$ are the circumcenters of $\Delta B^{*}C^{*}D^{*}$, $\Delta
A^{*}C^{*}D^{*}$, $\Delta A^{*}D^{*}D^{*}$, and $\Delta A^{*}C^{*}B^{*}$.

Proof: Download the Maple package RENE.txt freely available from Doron
Zeilberger’s website https://sites.math.rutgers.edu/~zeilberg/PG/RENE.txt ,
start Maple, and type read ‘RENE.txt‘: followed by Leversha();, and in one
nano-second, you would get that it is true. The Maple code for proving
Leversha’s theorem is as follows:

T1 := Te(m, n); T2 := Te(m1, n1); A := [0, 0]; B := T1[3]; C := T2[3];
evalb(DeSq(IsogonalConjugate(m1, n1, B), A) = DeSq(IsogonalConjugate(m, n, C),
A))

Explanation by Doron Zeilberger

Without loss of generality (by translating, rotating, and shrinking) we can
assume that $A=(0,0)$, $D=(1,0)$,

$tan({1\over 2}\angle BAD)=m\quad,\quad tan({1\over 2}\angle ADB)=n\quad,\quad
tan({1\over 2}\angle CAD)=M\quad,\quad tan({1\over 2}\angle ADC)=N\quad,$

so now $\Delta ADB$ and $\Delta ADC$ are what are called (in RENE.txt),
Te(m,n) and Te(M,N). Using the straightforward IsogonalConjugate macro we get
$B^{*}$ and $C^{*}$ and we just check that the ‘distance-squared’ (DeSq),
between $A$ and $B^{*}$ and $A$ and $C^{*}$ are the same. Of course, this is
also true about the distance between $A$ and $B^{*}$ and $A$ and $D^{*}$, and
by the transitivity of the $=$ relation, all three distances are equal and
hence indeed $A$ is the circumcenter of $\Delta B^{*}C^{*}D^{*}$.

But using this ‘analytic’ approach (rather than Leversha’s synthetic approach)
gives much more. LevershaRadius(m,n,M,N) gives that the exact value of the
circumradius of $\Delta B^{*}C^{*}D^{*}$ is

${{\left(N-n\right)\left(Nn+1\right)\left({m}^{2}+1\right)\left({M}^{2}+1\right)\over\left((MN-1)(mn-1)+(M+N)(n+m)\right)\left(MN(n+m)-mn(M+N)+M+N-m-n\right)}}\quad.$

RENE.txt can also tell you the exact locations of $B^{*}$ and $C^{*}$:

$B^{*}\,=\,(\,{{\left(Mm+M-m+1\right)\left(Mm-M+m+1\right)\left(Nn+1\right)\left(N-n\right)\over\left(MN(mn-1)+(M+N)(m+n)-mn+1\right)\left(MN(m+n)-mn(M+N)+M+N-m-n\right)}}\,,$
${{2\,\left(Nn+1\right)\left(N-n\right)\left(Mm+1\right)\left(M-m\right)\over\left(MN(mn-1)+(M+N)(m+n)-mn+1\right)\left(MN(m+n)-mn(M+N)+M+N-m-n\right)}})\quad,$
$C^{*}\,=\,(\,{{\left(Mm+M-m+1\right)\left(Mm-M+m+1\right)\left(Nn+1\right)\left(-n+N\right)\over\left(MN(mn-1)+(M+N)(m+n)-mn+1\right)\left(MN(m+n)-mn(M+N)+M+N-m-n\right)}}\,,$
$-\,{{2\,\left(Nn+1\right)\left(-n+N\right)\left(Mm+1\right)\left(-m+M\right)\over\left(MN(mn-1)+(M+N)(m+n)-mn+1\right)\left(MN(m+n)-mn(M+N)+M+N-m-n\right)}})\quad.$

So we have a nice lagniappe, we have proved something stronger than the fact
that $B^{*}$ and $C^{*}$ are equidistant from $A$. It turns out that $B^{*}$
and $C^{*}$ are mirror-images of each other with respect to the line $AD$. Of
course this is true for all the other five combinations.

References

[L] Gerry Leversha, A quartet of isogonal conjugates, The Mathematical
Gazette, 100, issue 548, (July, 2016), 336-341, (Note 100.23). Available from
JSTOR.

[W] The Wikipedia Foundation, Isogonal Conjugate
https://en.wikipedia.org/wiki/Isogonal_conjugate

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers
University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd.,
Piscataway, NJ 08854-8019, USA. Email: ShaloshBEkhad at gmail dot com .


* [17] Joel Dahne and Bruno Salvy  “Computation of Tight Enclosures for Laplacian Eigenvalues”  In _SIAM J. Sci. Comput._ 42.5 Society for Industrial & Applied Mathematics (SIAM), 2020, pp. A3210–A3232  DOI: 10.1137/20m1326520
  * [18] “NIST Digital Library of Mathematical Functions” F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds., http://dlmf.nist.gov/, Release 1.1.4 of 2022-01-15  URL: http://dlmf.nist.gov/
  * [19] Mats Ehrnström, Ola I.. Mæhlen and Kristoffer Varholm  “On the precise cusped behaviour of extreme solutions to Whitham-type equations”  arXiv, 2023  DOI: 10.48550/ARXIV.2302.08856
  * [20] Mats Ehrnström and Erik Wahlén  “On Whitham’s conjecture of a highest cusped wave for a nonlocal dispersive equation”  In _Annales de l’Institut Henri Poincaré C, Analyse non linéaire_ 36.6 Elsevier BV, 2019, pp. 1603–1637  DOI: 10.1016/j.anihpc.2019.02.006
  * [21] Mats Ehrnström and Yuexun Wang  “Enhanced Existence Time of Solutions to the Fractional Korteweg–de Vries Equation”  In _SIAM J. Math. Anal._ 51.4 Society for Industrial & Applied Mathematics (SIAM), 2019, pp. 3298–3323  DOI: 10.1137/19m1237867
  * [22] Alberto Enciso, Javier Gómez-Serrano and Bruno Vergara  “Convexity of Whitham’s highest cusped wave”, 2018  arXiv:1810.10935 [math.AP]
  * [23] Jordi-Lluís Figueras, Marcio Gameiro, Jean-Philippe Lessard and Rafael Llave  “A Framework for the Numerical Computation and A Posteriori Verification of Invariant Objects of Evolution Equations”  In _SIAM Journal on Applied Dynamical Systems_ 16.2 Society for Industrial & Applied Mathematics (SIAM), 2017, pp. 1070–1088  DOI: 10.1137/16m1073777
  * [24] Jordi-Lluís Figueras and Rafael Llave  “Numerical Computations and Computer Assisted Proofs of Periodic Orbits of the Kuramoto–Sivashinsky Equation”  In _SIAM Journal on Applied Dynamical Systems_ 16.2 Society for Industrial & Applied Mathematics (SIAM), 2017, pp. 834–852  DOI: 10.1137/16m1073790
  * [25] Marcio Gameiro and Jean-Philippe Lessard  “A Posteriori Verification of Invariant Objects of Evolution Equations: Periodic Orbits in the Kuramoto–Sivashinsky PDE”  In _SIAM Journal on Applied Dynamical Systems_ 16.1 Society for Industrial & Applied Mathematics (SIAM), 2017, pp. 687–728  DOI: 10.1137/16m1073789
  * [26] Javier Gómez-Serrano  “Computer-assisted proofs in PDE: a survey”  In _SeMA Journal_ 76.3 Springer ScienceBusiness Media LLC, 2019, pp. 459–484  DOI: 10.1007/s40324-019-00186-x
  * [27] Javier Gómez-Serrano and Rafael Granero-Belinchón  “On turning waves for the inhomogeneous Muskat problem: A computer-assisted proof”  In _Nonlinearity_ 27.6 IOP Publishing, 2014, pp. 1471–1498  DOI: 10.1088/0951-7715/27/6/1471
  * [28] H.. Gould  “Coefficient Identities for Powers of Taylor and Dirichlet Series”  In _The American Mathematical Monthly_ 81.1 JSTOR, 1974, pp. 3  DOI: 10.2307/2318904
  * [29] Susanna Haziot, Vera Hur, Walter Strauss, J. Toland, Erik Wahlén, Samuel Walsh and Miles Wheeler  “Traveling water waves — the ebb and flow of two centuries”  In _Quarterly of Applied Mathematics_ 80.2 American Mathematical Society (AMS), 2022, pp. 317–401  DOI: 10.1090/qam/1614
  * [30] Fredrik Hildrum and Jun Xue  “Periodic Hölder waves in a class of negative-order dispersive equations”  In _Journal of Differential Equations_ 343 Elsevier BV, 2023, pp. 752–789  DOI: 10.1016/j.jde.2022.10.023
  * [31] John K. Hunter  “The Burgers–Hilbert Equation”  In _Theory, Numerics and Applications of Hyperbolic Problems II_ Cham: Springer International Publishing, 2018, pp. 41–57  DOI: 10.1007/978-3-319-91548-7˙3
  * [32] John K. Hunter and Mihaela Ifrim  “Enhanced Life Span of Smooth Solutions of a Burgers–Hilbert Equation”  In _SIAM J. Math. Anal._ 44.3 Society for Industrial & Applied Mathematics (SIAM), 2012, pp. 2039–2052  DOI: 10.1137/110849791
  * [33] John K. Hunter, Mihaela Ifrim, Daniel Tataru and Tak Kwong Wong  “Long time solutions for a Burgers-Hilbert equation via a modified energy method”  In _Proc. Amer. Math. Soc._ 143.8 American Mathematical Society (AMS), 2015, pp. 3407–3412  DOI: 10.1090/proc/12215
  * [34] Vera Mikyoung Hur  “On the formation of singularities for surface water waves”  In _Communications on Pure and Applied Analysis_ 11.4 American Institute of Mathematical Sciences (AIMS), 2012, pp. 1465–1474  DOI: 10.3934/cpaa.2012.11.1465
  * [35] Vera Mikyoung Hur  “Wave breaking in the Whitham equation”  In _Advances in Mathematics_ 317 Elsevier BV, 2017, pp. 410–437  DOI: 10.1016/j.aim.2017.07.006
  * [36] Vera Mikyoung Hur and Lizheng Tao  “Wave breaking for the Whitham equation with fractional dispersion”  In _Nonlinearity_ 27.12 IOP Publishing, 2014, pp. 2937–2949  DOI: 10.1088/0951-7715/27/12/2937
  * [37] F. Johansson  “Fast and rigorous computation of special functions to high precision”, 2014
  * [38] F. Johansson  “Numerical integration in arbitrary-precision ball arithmetic”  In _Mathematical Software – ICMS 2018_ Springer Lecture Notes in Computer Science, 2018, pp. 255–263  DOI: 10.1007/978-3-319-96418-8˙30
  * [39] Fredrik Johansson  “A fast algorithm for reversion of power series”  In _Math. Comp._ 84.291 American Mathematical Society (AMS), 2014, pp. 475–484  DOI: 10.1090/s0025-5718-2014-02857-3
  * [40] Fredrik Johansson  “Arb: A C Library for Ball Arithmetic”  In _ACM Commun. Comput. Algebra_ 47.3/4 Association for Computing Machinery (ACM), 2014, pp. 166–169  DOI: 10.1145/2576802.2576828
  * [41] Fredrik Johansson  “Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic”  In _IEEE Trans. Comput._ 66.8 Institute of ElectricalElectronics Engineers (IEEE), 2017, pp. 1281–1292  DOI: 10.1109/tc.2017.2690633
  * [42] Fredrik Johansson  “Computing Hypergeometric Functions Rigorously”  In _ACM Transactions on Mathematical Software_ 45.3 Association for Computing Machinery (ACM), 2019, pp. 1–26  DOI: 10.1145/3328732
  * [43] Fredrik Johansson  “Rigorous high-precision computation of the Hurwitz zeta function and its derivatives”  In _Numer Algor_ 69.2 Springer ScienceBusiness Media LLC, 2014, pp. 253–270  DOI: 10.1007/s11075-014-9893-1
  * [44] Mioara Maria Joldes  “Rigorous Polynomial Approximations and Applications”, 2011  URL: https://tel.archives-ouvertes.fr/tel-00657843
  * [45] Christian Klein and Jean-Claude Saut  “A numerical approach to blow-up issues for dispersive perturbations of Burgers’ equation”  In _Physica D: Nonlinear Phenomena_ 295-296 Elsevier BV, 2015, pp. 46–65  DOI: 10.1016/j.physd.2014.12.004
  * [46] W. Krämer and S. Wedner  “Two adaptive Gauss-Legendre type algorithms for the verified computation of definite integrals”  In _Reliable Computing_ 2.3 Springer ScienceBusiness Media LLC, 1996, pp. 241–253  DOI: 10.1007/bf02391698
  * [47] Felipe Linares, Didier Pilod and Jean-Claude Saut  “Dispersive Perturbations of Burgers and Hyperbolic Equations I: Local Theory”  In _SIAM J. Math. Anal._ 46.2 Society for Industrial & Applied Mathematics (SIAM), 2014, pp. 1505–1537  DOI: 10.1137/130912001
  * [48] Patrick Kofod Mogensen, Kristoffer Carlsson, Sébastien Villemot, Spencer Lyon, Matthieu Gomez, Christopher Rackauckas, Tim Holy, David Widmann, Tony Kelman, Daniel Karrasch, Antoine Levitt, Asbjørn Nilsen Riseth, Carlo Lucibello, Changhyun Kwon, David Barton, Julia TagBot, Mateusz Baran, Miles Lubin, Sarthak Choudhury, Simon Byrne, Simon Christ, Takafumi Arakaki, Troels Arnfred Bojesen, benneti and Miguel Raz Guzmán Macedo  “JuliaNLSolvers/NLsolve.jl: v4.5.1”  Zenodo, 2020  DOI: 10.5281/zenodo.4404703
  * [49] Ramon E. Moore  “Methods and Applications of Interval Analysis”  Society for IndustrialApplied Mathematics, 1979  DOI: 10.1137/1.9781611970906
  * [50] Sung-Jin Oh and Federico Pasqualotto  “Gradient blow-up for dispersive and dissipative perturbations of the Burgers equation”, 2021  arXiv:2107.07172v1 [math.AP]
  * [51] Magnus Christie Ørke  “Highest waves for fractional Korteweg–De Vries and Degasperis–Procesi equations”, 2022  arXiv:2201.13159v1 [math.AP]
  * [52] Oscar Riaño  “On persistence properties in weighted spaces for solutions of the fractional Korteweg–de Vries equation”  In _Nonlinearity_ 34.7 IOP Publishing, 2021, pp. 4604–4660  DOI: 10.1088/1361-6544/abf5bd
  * [53] G.G. Stokes and J.W.S. Rayleigh  “Mathematical and Physical Papers; Volume 1”  Creative Media Partners, LLC, 2018  URL: https://books.google.se/books?id=2g%5C_kswEACAAJ
  * [54] Warwick Tucker  “Validated Numerics”  Princeton, NJ: Princeton University Press, 2011, pp. xii+138  DOI: 10.1515/9781400838974
  * [55] G.. Whitham  “Linear and Nonlinear Waves”  John Wiley & Sons, Inc., 1999  DOI: 10.1002/9781118032954
  * [56] Gerald Beresford Whitham  “Variational methods and applications to water waves”  In _Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences_ 299.1456 The Royal Society, 1967, pp. 6–25  DOI: 10.1098/rspa.1967.0119

Joel Dahne
---
Department of Mathematics
Uppsala University
Lägerhyddsvägen 1, 752 37, Uppsala, Sweden
Email<EMAIL_ADDRESS>