# On a Unified and Simplified Proof for the Ergodic Convergence Rates of PPM,
PDHG and ADMM

Haihao Lu The University of Chicago, Booth School of Business
(haihao.lu@chicagobooth.edu). Jinwen Yang The University of Chicago,
Department of Statistics (jinweny@uchicago.edu).

(May 2023)

###### Abstract

We present a unified viewpoint of proximal point method (PPM), primal-dual
hybrid gradient (PDHG) and alternating direction method of multipliers (ADMM)
for solving convex-concave primal-dual problems. This viewpoint shows the
equivalence of these three algorithms upto a norm change, and it leads to a
four-line simple proof of their $\mathcal{O}(1/k)$ ergodic rates. The simple
proof technique is not limited to these three algorithms, but can also be
utilized to analyze related algorithms, such as gradient descent, linearized
PDHG, inexact algorithms, just to name a few.

##  1 Introduction

We study three classic algorithms, proximal point method (PPM), primal-dual
hybrid gradient method (PDHG) and alternating direction method of multipliers
(ADMM), for solving a convex-concave primal-dual problem,

$\min_{x\in\mathbb{R}^{n}}\max_{\lambda\in\mathbb{R}^{m}}\;L(x,\lambda)\ ,$
(1)

where $L(x,\lambda)$ is lower semicontinuous convex in the primal variable
$x$, upper semicontinuous concave in the dual variable $\lambda$. Such convex-
concave primal-dual problems and their primal and/or dual forms have various
applications in image processing, statistics, conic programming, etc.

While PDHG and ADMM are extensively studied in the optimization literature and
widely used in practice, the proofs of their $\mathcal{O}(1/k)$ ergodic
convergence rate are still viewed as “technical” with non-trivial mathematical
manipulations. These proofs make it difficult to gain intuitions about the
extrapolation steps in PDHG and the carefully-chosen cyclic rule in ADMM and
to extend these algorithms in other settings. In this paper, we provide a
unified viewpoint of PPM, PDHG and ADMM. This viewpoint clearly shows that
PDHG and ADMM are variants of PPM with different choices of norms.
Furthermore, this viewpoint leads to a four-line simple and unified proof
(Theorem 1) of the $\mathcal{O}(1/k)$ ergodic rate for these three algorithms.
Indeed, this viewpoint was also mentioned in [8, 15], which provides an
approximate PPM interpretation of PDHG, but such connection was not further
explored to obtain convergence analysis. Recently, [12, 10, 17] show the
equivalence of ADMM/DRS and PDHG up to a change of norm, which can also be
clearly obtained from the such interpretation.

We believe this perspective provides a fundamental understanding of these
three algorithms, which can also facilitate developing new variants of these
algorithms. Indeed, this viewpoint and the convergence result is not limited
to analyze these three algorithms, and can also be easily extended to analyze
other first-order methods, such as gradient descent for convex optimization,
linearized PDHG, inexact algorithms, just to name a few.

In 1976, Rockafellar proposed proximal point method (PPM) in his seminal work
[14]. PPM was initially designed to solve monotone inclusion problems. As a
special case of monotone inclusion, primal-dual problems can be solved
utilizing PPM, as described in Algorithm 1. PPM can be viewed as an implicit
discretization of gradient flow when the objective $L(x,\lambda)$ is
sufficiently differentiable. However, PPM requires solving an implicit
equation jointly in the primal and the dual variable, which are often
computationally challenging. A more practical class of algorithms is the
operator splitting methods which alternatively update the primal and the dual
variables. The two most popular operator splitting algorithms are perhaps
primal-dual hybrid gradient method (PDHG) [4, 5] and alternating direction
method of multipliers (ADMM) [7, 6, 3].

Algorithm 1 PPM for (1)

0: initial point $(x^{0},\lambda^{0})$, step-size $\eta>0$.

1: for $k=0,1,...$ do

2:
$(x^{k+1},\lambda^{k+1}):=\arg\min_{x}\arg\max_{\lambda}\left\\{L(x,\lambda)+\frac{1}{2\eta}\|x-x^{k}\|_{2}^{2}-\frac{1}{2\eta}\|\lambda-\lambda^{k}\|_{2}^{2}\right\\}$

3: end for

PDHG was initially designed for image processing applications [4], and it is
recently used as the base algorithm in a new linear programming (LP) solver
PDLP [1] that aims to significantly scale up LP. PDHG [4] solves the composite
minimization problem

$\min_{x}\;f(x)+g(Ax)\ ,$

and its primal-dual formulation,

$\min_{x}\max_{\lambda}\;L(x,\lambda)=f(x)-\lambda^{T}Ax-g^{*}(\lambda)\ ,$
(2)

where $f$ and $g$ are lower semi-continuous convex functions,
$g^{*}(\lambda):=\max_{y}\\{\lambda^{T}y-g(y)\\}$ is the conjugate function of
function $g$. The update rule of PDHG is presented in Algorithm 2. The ergodic
rate of PDHG was first shown in [4], and a simplified proof was presented in
[5].

Algorithm 2 PDHG for (2)

0: initial point $(x^{0},\lambda^{0})$, step-size $\eta>0$.

1: for $k=0,1,...$ do

2: $x^{k+1}:=\arg\min_{x}\left\\{f(x)-\langle
A^{T}\lambda^{k},x-x^{k}\rangle+\frac{1}{2\eta}\|x-x^{k}\|_{2}^{2}\right\\}$

3: $\lambda^{k+1}:=\arg\min_{\lambda}\left\\{g^{*}(\lambda)+\langle
A(2x^{k+1}-x^{k}),\lambda-\lambda^{k}\rangle+\frac{1}{2\eta}\|\lambda-\lambda^{k}\|_{2}^{2}\right\\}$

4: end for

ADMM solves the following linearly constrained minimization problem:

$\displaystyle\begin{split}&\ \min_{x,y}\;f(x)+g(y)\\\
&\quad\mathrm{s.t.}\;Ax+By=b\ ,\end{split}$ (3)

and its primal-dual form

$\displaystyle\min_{x}\max_{\lambda}\;L(x,y,\lambda)=f(x)+g(y)-\lambda^{T}(Ax+By-b)\
,$ (4)

where $f$ and $g$ are lower semi-continuous convex functions. The update rule
of ADMM is presented in Algorithm 3. ADMM can be viewed as a Douglas-Rachford
splitting method [7] for optimizing the dual problem to (3). The eventual
convergence result of ADMM was presented in [6], and the first
$\mathcal{O}(1/k)$ ergodic convergence rate of ADMM was obtained in [9]. It is
used as the base algorithm for the conic programming solver SCS [13] and the
quadratic programming solver OSQP [16]. More applications and a comprehensive
discussion on ADMM can be found in [3].

Algorithm 3 ADMM for (3)

0: initial point $(x^{0},\lambda^{0})$, step-size $\eta>0$.

1: for $k=0,1,...$ do

2: $y^{k+1}:=\arg\min_{y}\left\\{g(y)-\langle
B^{T}\lambda^{k},y\rangle+\frac{\eta}{2}\|Ax^{k}+By-b\|_{2}^{2}\right\\}$

3: $\lambda^{k+1}:=\lambda^{k}-\eta(Ax^{k}+By^{k+1}-b)$

4: $x^{k+1}:=\arg\min_{x}\left\\{f(x)-\langle
A^{T}\lambda^{k+1},x\rangle+\frac{\eta}{2}\|Ax+By^{k+1}-b\|_{2}^{2}\right\\}$

5: end for

##  2 Main results

In this section, we present a unified and simplified proof for ergodic rates
of PPM, PDHG and ADMM. We start with presenting a generic algorithm and show
that PPM, PDHG and ADMM are special cases of this generic algorithm with a
different choice of norm. Then we show the $\mathcal{O}(1/k)$ ergodic rate of
this generic algorithm. As a direct consequence, this shows the ergodic rate
of the three algorithms, and show the equivalence of these algorithms upto a
norm.

We denote $z=(x,\lambda)$ as the primal-dual solution pair and
$\mathcal{F}(z)=\mathcal{F}(x,\lambda)=\begin{pmatrix}\partial_{x}L(x,\lambda)\\\
-\partial_{\lambda}L(x,\lambda)\end{pmatrix}$ as the sub-gradient of the
objective (more precisely, the gradient over the primal variable $x$ and the
negative gradient over the dual variable $\lambda$). We consider a generic
algorithm with iterate update rule:

$P(z^{k}-z^{k+1})\in\mathcal{F}(z^{k+1})\ ,$ (5)

where $P\in\mathbb{R}^{(m+n)\times(m+n)}$ is a positive semi-definite matrix.

Next, we show that the iterate updates of PPM, PDHG and ADMM all follow with
(5) with a proper choice of matrix $P$.

######  Lemma 1.

The update rule of PPM (Algorithm 1) for the primal-dual problem (1) is an
instance of (5) with $P=\frac{1}{\eta}I$.

###### Proof.

This can be obtained directly from the first-order stationary condition of the
update rule of PPM. ∎

######  Lemma 2.

The update rule of PDHG (Algorithm 2) for the primal-dual problem (2) is an
instance of (5) with $P=\begin{pmatrix}\frac{1}{\eta}I&A^{T}\\\
A&\frac{1}{\eta}I\end{pmatrix}$.

###### Proof.

Notice that we have $\mathcal{F}(z)=\begin{pmatrix}\partial
f(x)-A^{T}\lambda\\\ \partial g^{*}(\lambda)+Ax\end{pmatrix}$ for the
objective $L(x,\lambda)$ defined in (2). The first-order optimality condition
of update rules in Algorithm 2 are

$\displaystyle\begin{split}&0\in\partial
f(x^{k+1})+\frac{1}{\eta}(x^{k+1}-x^{k}-\eta A^{T}\lambda^{k})\\\
&0\in\partial
g^{*}(\lambda^{k+1})+\frac{1}{\eta}(\lambda^{k+1}-\lambda^{k}+\eta
A(2x^{k+1}-x^{k}))\ .\end{split}$

Rearranging the above update rules, we reach at

$\displaystyle\begin{split}&\frac{1}{\eta}(x^{k}-x^{k+1})+A^{T}(\lambda^{k}-\lambda^{k+1})\in\partial
f(x^{k+1})-A^{T}\lambda^{k+1}\\\
&\frac{1}{\eta}(\lambda^{k}-\lambda^{k+1})+A(x^{k}-x^{k+1})\in\partial
g^{*}(\lambda^{k+1})+Ax^{k+1}\end{split}$

that is,

$P(z^{k}-z^{k+1})\in\mathcal{F}(z^{k+1})\ .$

∎

######  Lemma 3.

The update rule of ADMM (Algorithm 3) for the primal-dual problem (4) is an
instance of (5) with $P=\begin{pmatrix}0&0&0\\\ 0&\eta A^{T}A&-A^{T}\\\
0&-A&\frac{1}{\eta}I\end{pmatrix}$.

###### Proof.

Notice that we have $\mathcal{F}(z)=\begin{pmatrix}\partial
g(y^{k+1})-B^{T}\lambda^{k+1}\\\ \partial f(x^{k+1})-A^{T}\lambda^{k+1}\\\
Ax^{k+1}+By^{k+1}-b\end{pmatrix}$ for the objective $L(x,y,\lambda)$ defined
in (4). By utilizing the first-order optimality conditions, we can rewrite the
three update rules in Algorithm 2 on $y^{k+1},\lambda^{k+1},x^{k+1}$ as

$\displaystyle\begin{split}0&\in\partial g(y^{k+1})+\eta
B^{T}(Ax^{k}+By^{k+1}-b-\frac{1}{\eta}\lambda^{k})=\partial g(y^{k+1})+\eta
B^{T}\frac{1}{\eta}(\lambda^{k}-\lambda^{k+1}-\lambda^{k})=\partial
g(y^{k+1})-B^{T}\lambda^{k+1}\ ,\end{split}$ (6)
$\displaystyle\begin{split}\frac{1}{\eta}(\lambda^{k}-\lambda^{k+1})-A(x^{k}-x^{k+1})=By^{k+1}+Ax^{k+1}-b\
,\end{split}$ (7) $\displaystyle\begin{split}0&\in\partial f(x^{k+1})+\eta
A^{T}(Ax^{k+1}+By^{k+1}-b-\frac{1}{\eta}\lambda^{k+1})=\partial
f(x^{k+1})+\eta
A^{T}(Ax^{k+1}-Ax^{k}+\frac{1}{\eta}\lambda^{k}-\frac{2}{\eta}\lambda^{k+1})\
.\end{split}$ (8)

Rearranging (6), (8) and (7), we reach

$P(z^{k}-z^{k+1})=\begin{pmatrix}0&0&0\\\ 0&\eta A^{T}A&-A^{T}\\\
0&-A&\frac{1}{\eta}I\end{pmatrix}\begin{pmatrix}y^{k}-y^{k+1}\\\
x^{k}-x^{k+1}\\\
\lambda^{k}-\lambda^{k+1}\end{pmatrix}\in\begin{pmatrix}\partial
g(y^{k+1})-B^{T}\lambda^{k+1}\\\ \partial f(x^{k+1})-A^{T}\lambda^{k+1}\\\
Ax^{k+1}+By^{k+1}-b\end{pmatrix}=\mathcal{F}(z^{k+1})\ .$

∎

The above three lemmas clearly show the connections and differences among PPM,
ADMM and PDHG: they share very similar update rules (i.e., (5)) with a
different choice of the matrix $P$. Indeed, these $P$ norm matrices appear in
the analysis of ADMM [9] and PDHG [5] without many intuitions, and our
viewpoint of (5) make clear where they come from.

The next theorem is our main result, which shows the ergodic rate of any
algorithm with update rule (5) when $P$ is positive semi-definite.

######  Theorem 1.

Consider an iterate update rule (5) with a positive semi-definite matrix $P$
for solving a convex-concave primal-dual problem (1). The iterates
$\\{z^{k}=(x^{k},\lambda^{k})\\}_{k=1,...,\infty}$ are obtained from this
iterate update rule and the initial solution $z^{0}=(x^{0},\lambda^{0})$.
Denote
$\bar{z}^{k}=(\bar{x}^{k},\bar{\lambda}^{k})=\frac{1}{k}\sum_{i=1}^{k}z^{i}$
as the average iterate. Then it holds for any $k\geq 1$ and a primal-dual
solution $z=(x,\lambda)$ that

$L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{\|z-z^{0}\|^{2}_{P}}{2k}\
.$

###### Proof.

Denote $w^{k+1}=P(z^{k}-z^{k+1})\in\mathcal{F}(z^{k+1})$. It then holds by
convexity-concavity of $L(x,\lambda)$ that

$\displaystyle\begin{split}&L(x^{k+1},\lambda)-L(x,\lambda^{k+1})\
=L(x^{k+1},\lambda)-L(x^{k+1},\lambda^{k+1})+L(x^{k+1},\lambda^{k+1})-L(x,\lambda^{k+1})\\\
\leq&\left\langle w^{k+1},z^{k+1}-z\right\rangle\ =\left\langle
z^{k}-z^{k+1},z^{k+1}-z\right\rangle_{P}=\frac{1}{2}\|z^{k}-z\|_{P}^{2}-\frac{1}{2}\|z^{k+1}-z\|_{P}^{2}-\frac{1}{2}\|z^{k}-z^{k+1}\|_{P}^{2}\\\
\ \leq&\frac{1}{2}\|z^{k}-z\|_{P}^{2}-\frac{1}{2}\|z^{k+1}-z\|_{P}^{2}\
,\end{split}$ (9)

where the last inequality follows from the fact that $\|\cdot\|_{P}$ is a
semi-norm. We finish the proof by noticing

$\displaystyle\begin{split}L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{1}{k}\sum_{i=0}^{k-1}L(x^{i+1},\lambda)-L(x,\lambda^{i+1})\leq\frac{1}{2k}\|z^{0}-z\|_{P}^{2}\
,\end{split}$

where the first inequality comes from convexity-concavity of $L(x,\lambda)$
and the telescoping using (9). ∎

Utilizing Theorem 1 and noticing that PPM (Algorithm 1), PDHG (Algorithm 2)
and ADMM (Algorithm 3) are special case of the update rule (5) with a
different choice $P$, we directly obtain the following ergodic rate of the
three algorithms.

######  Corollary 1.

Consider PPM (Algorithm 1) for solving a convex-concave primal-dual problem
(1). Denote
$\bar{z}^{k}=(\bar{x}^{k},\bar{\lambda}^{k})=\frac{1}{k}\sum_{i=1}^{k}z^{i}$
as the average iterate. Then it holds for any $\eta>0$, $k\geq 1$, and
$z=(x,\lambda)$ that

$L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{\|z-z^{0}\|^{2}_{2}}{2\eta
k}\ .$

######  Corollary 2.

Consider PDHG (Algorithm 2) for solving a convex-concave primal-dual problem
of the form (2). Denote
$\bar{z}^{k}=(\bar{x}^{k},\bar{\lambda}^{k})=\frac{1}{k}\sum_{i=1}^{k}z^{i}$
as the average iterate. Then it holds for any $0<\eta\leq 1/\|A\|_{2}$, $k\geq
1$, and $z=(x,\lambda)$ that

$L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{\|z-z^{0}\|^{2}_{P}}{2k}\
,$

where $P=\begin{pmatrix}\frac{1}{\eta}I&A^{T}\\\
A&\frac{1}{\eta}I\end{pmatrix}$.

######  Corollary 3.

Consider ADMM (Algorithm 3) for solving a convex-concave primal-dual problem
of the form (4). Denote
$\bar{z}^{k}=(\bar{y}^{k},\bar{x}^{k},\bar{\lambda}^{k})=\frac{1}{k}\sum_{i=1}^{k}z^{i}$
as the average iterate. Then it holds for any $\eta>0$, $k\geq 1$, and
$z=(y,x,\lambda)$ that

$L(\bar{x}^{k},\bar{y}^{k},\lambda)-L(x,y,\bar{\lambda}^{k})\leq\frac{\|z-z^{0}\|^{2}_{P}}{2k}\
,$

where $P=\begin{pmatrix}0&0&0\\\ 0&\eta A^{T}A&-A^{T}\\\
0&-A&\frac{1}{\eta}I\end{pmatrix}$. By choosing $x=x^{*}$ and $y=y^{*}$ as the
optimal solutions to the primal problem and noticing the optimal primal
objective value $F^{*}=f(x^{*})+g(y^{*})=L(x^{*},y^{*},\bar{\lambda}^{k})$, it
holds for any $\lambda$ that

$f(\bar{x}^{k})+g(\bar{y}^{k})-\lambda^{T}(A\bar{x}^{k}+B\bar{y}^{k}-b)-F^{*}\leq\frac{\|(y^{*},x^{*},\lambda)-(y^{0},x^{0},\lambda^{0})\|_{P}^{2}}{2k}\
.$ (10)

######  Remark 1.

The left-hand-side of (10) measures the optimality and feasibility of the
solution $(\bar{x}^{k},\bar{y}^{k})$ to the primal problem (3), see [2,
Theorem 3.60].

##  3 Extensions

The update rules of PPM, PDHG and ADMM require solving a proximal (implicit)
oracle, because the right-hand-side of (5) depends on $z^{k+1}$. This step in
general can be computationally expensive. In this section, we discuss two
types of extensions to avoid this issue: linearized methods and inexact
methods.

###  3.1 Linearized methods

Instead of using $F(z^{k+1})$ in (5), we consider a generic update rule:

$P(z^{k}-z^{k+1})\in F^{k+1}\ ,$ (11)

where $P\in\mathbb{R}^{(m+n)\times(m+n)}$ is a positive semi-definite matrix
and $F^{k+1}$ is an approximation to the sub-differential
$\mathcal{F}(z^{k+1})$ so that (11) is inexpensive to solve.

Two economic examples of the linearized methods are gradient descent for
minimization problems and linearized PDHG for primal-dual problems.

  * •

Gradient descent [11]. Consider a minimization problem $\min_{x}f(x)$ where
$f(x)$ is a convex and $L$-smooth function (i.e., $\nabla f(x)$ is
$L$-Lipschitz continuous). Gradient descent has update rule
$x^{k+1}=x^{k}-\eta\nabla f(x^{k})$, where $\eta$ is the step-size of the
algorithm. It is easy to see that gradient descent is an instance of (11) with
$z^{k}=x^{k}$ (one can view that the Lagrangian function $L(x,y)$ is
independent of $y$), $P=\frac{1}{\eta}I$ and $F^{k+1}=\nabla f(x^{k})$.

  * •

Linearized PDHG [5]. Linearized PDHG, which is formally stated in Algorithm 4,
solves (2) without the need of solving proximal oracles. Similar to the proof
of Lemma 2, we can rewrite the update rule of linearized PDHG as an instance
of (11) with $P=\frac{1}{\eta}I$ and $F^{k+1}=\begin{pmatrix}\nabla
f(x^{k})-A^{T}\lambda^{k+1}\\\ \nabla
g^{*}(\lambda^{k})+Ax^{k+1}\end{pmatrix}$.

Algorithm 4 Linearized PDHG for (2)

0: initial point $(x^{0},\lambda^{0})$, step-size $\eta>0$.

1: for $k=0,1,...$ do

2: $x^{k+1}:=x^{k}-\eta(\nabla f(x^{k})-A^{T}\lambda^{k})$

3: $\lambda^{k+1}:=\lambda^{k}-\eta(\nabla
g^{*}(\lambda^{k})+A(2x^{k+1}-x^{k}))$

4: end for

To guarantee the convergence property of the algorithms, $F^{k+1}$ should well
approximate $\mathcal{F}(z^{k+1})$, which is formalized in the following
assumptions:

######  Assumption 1.

Consider iterates $\\{z^{k}=(x^{k},\lambda^{k})\\}$ from algorithm with update
rule (11).

  1. (i)

There exists a matrix $E\succeq 0$ such that for any $z=(x,y)$,

$L(x^{k+1},\lambda)-L(x,\lambda^{k+1})\leq\langle
F^{k+1},z^{k+1}-z\rangle+\frac{1}{2}\|z^{k}-z^{k+1}\|_{E}^{2}\ .$ (12)

  2. (ii)

It holds that $P\succeq E$.

When $F^{k+1}=F(z^{k+1})$, Assumption 1 (i) holds with $E=0$. The matrix $E$,
in principle, measures the difference between $F^{k+1}$ and $F(z^{k+1})$.
Assumption 1 (ii) indicates that such difference (i.e. $E$) is not too large
compared to the matrix $P$.

The next theorem shows that an algorithm with update rule (11) has
$\mathcal{O}(1/k)$ sublinear rate under Assumption 1:

######  Theorem 2.

Consider an iterate update rule (11) with a positive semi-definite matrix $P$
for solving a convex-concave primal-dual problem (2). The iterates
$\\{z^{k}=(x^{k},\lambda^{k})\\}_{k=1,...,\infty}$ are obtained from this
iterate update rule (11), and the initial solution
$z^{0}=(x^{0},\lambda^{0})$. Denote
$\bar{z}^{k}=(\bar{x}^{k},\bar{\lambda}^{k})=\frac{1}{k}\sum_{i=1}^{k}z^{i}$
as the average iterate. Suppose Assumption 1 holds. Then it holds for any
$k\geq 1$ and a primal-dual solution $z=(x,\lambda)$ that

$L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{\|z-z^{0}\|^{2}_{P}}{2k}\
.$

###### Proof.

It holds by Assumption 1 that

$\displaystyle\begin{split}L(x^{k+1},\lambda)-L(x,\lambda^{k+1})&\ \leq\langle
F^{k+1},z^{k+1}-z\rangle+\frac{1}{2}\|z^{k}-z^{k+1}\|_{E}^{2}=\langle
z^{k}-z^{k+1},z^{k+1}-z\rangle_{P}+\frac{1}{2}\|z^{k}-z^{k+1}\|_{E}^{2}\\\ &\
=\frac{1}{2}\|z^{k}-z\|_{P}^{2}-\frac{1}{2}\|z^{k+1}-z\|_{P}^{2}-\frac{1}{2}\|z^{k}-z^{k+1}\|_{P}^{2}+\frac{1}{2}\|z^{k}-z^{k+1}\|_{E}^{2}\\\
&\ \leq\frac{1}{2}\|z^{k}-z\|_{P}^{2}-\frac{1}{2}\|z^{k+1}-z\|_{P}^{2}\
,\end{split}$

where the last inequality follows from $P\succeq E$. We finish the proof by
noticing

$\displaystyle\begin{split}L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{1}{k}\sum_{i=0}^{k-1}L(x^{i+1},\lambda)-L(x,\lambda^{i+1})\leq\frac{1}{2k}\|z^{0}-z\|_{P}^{2}\
.\end{split}$

∎

As a direct consequence of Theorem 2, we can directly obtain the
$\mathcal{O}(1/k)$ sublinear convergence rate of gradient descent and
linearized PDHG by checking Assumption 1 holds:

######  Corollary 4.

Consider gradient descent for solving a convex $L$-smooth minimization problem
$\min_{x}f(x)$. Denote $\bar{x}^{k}=\frac{1}{k}\sum_{i=1}^{k}x^{i}$ as the
average iterate. Then it holds for any $0<\eta\leq 1/L$, $k\geq 1$, and
$x\in\mathrm{dom}(f)$ that

$f(\bar{x}^{k})-f(x)\leq\frac{\|x-x^{0}\|^{2}}{2\eta k}\ .$

###### Proof.

We just need to verify that Assumption 1 holds. From the $L$-smoothness and
convexity of the function $f$, we have

$\displaystyle\begin{split}&f(x^{k+1})-f(x)\
=f(x^{k+1})-f(x^{k})+f(x^{k})-f(x)\\\ \ \leq&\langle\nabla
f(x^{k}),x^{k+1}-x^{k}\rangle+\frac{L}{2}\|x^{k}-x^{k+1}\|_{2}^{2}+\langle\nabla
f(x^{k}),x^{k}-x\rangle=\langle\nabla
f(x^{k}),x^{k+1}-x\rangle+\frac{L}{2}\|x^{k}-x^{k+1}\|_{2}^{2}\ ,\end{split}$
(13)

which finishes the proof by utilizing Theorem 2. ∎

######  Corollary 5.

Consider Linearized PDHG (Algorithm 4) for solving a convex-concave primal-
dual problem of the form (2). Denote
$\bar{z}^{k}=(\bar{x}^{k},\bar{\lambda}^{k})=\frac{1}{k}\sum_{i=1}^{k}z^{i}$
as the average iterate. Suppose both $f$ and $g^{*}$ are $L$-smooth convex
functions. Then it holds for any $0<\eta\leq 1/(L+\|A\|_{2})$, $k\geq 1$, and
$z=(x,\lambda)$ that

$L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{\|z-z^{0}\|^{2}_{P}}{2k}\
,$

where $P=\begin{pmatrix}\frac{1}{\eta}I&A^{T}\\\
A&\frac{1}{\eta}I\end{pmatrix}$.

###### Proof.

We just need to verify that Assumption 1 holds. It holds from the smoothness
and convexity of functions $f$ and $g^{*}$ that

$\displaystyle\begin{split}L(x^{k+1},\lambda)-L(x^{k+1},\lambda^{k+1})&=g^{*}(\lambda^{k+1})-g^{*}(\lambda)-(x^{k+1})^{T}A^{T}(\lambda-\lambda^{k+1})\\\
&\leq(\nabla
g^{*}(\lambda^{k+1})+Ax^{k+1})^{T}(\lambda^{k+1}-\lambda)+\frac{L}{2}\|\lambda^{k}-\lambda^{k+1}\|_{2}^{2}\
,\end{split}$ (14)
$\displaystyle\begin{split}L(x^{k+1},\lambda^{k+1})-L(x,\lambda^{k+1})&=f(x^{k+1})-f(x)-(\lambda^{k+1})^{T}A(x^{k+1}-x)\\\
&\leq(\nabla
f(x^{k})-A^{T}\lambda^{k+1})^{T}(x^{k+1}-x)+\frac{L}{2}\|x^{k}-x^{k+1}\|_{2}^{2}\
.\end{split}$ (15)

Combine (14) and (15) and we have

$\displaystyle\begin{split}L(x^{k+1},\lambda)-L(x,\lambda^{k+1})&=L(x^{k+1},\lambda)-L(x^{k+1},\lambda^{k+1})+L(x^{k+1},\lambda^{k+1})-L(x,\lambda^{k+1})\\\
&\leq\langle F^{k+1},z^{k+1}-z\rangle+\frac{L}{2}\|z^{k}-z^{k+1}\|_{2}^{2}\
,\end{split}$

which implies Assumption 1 (i) holds with $E=LI$. Furthermore, with the choice
of stepsize $\eta\leq\frac{1}{L+\|A\|_{2}}$, it holds that
$P-E=\begin{pmatrix}\left({\frac{1}{\eta}-L}\right)I&A^{T}\\\
A&\left({\frac{1}{\eta}-L}\right)I\end{pmatrix}\succeq 0$. The result follows
from application of Theorem 2. ∎

###  3.2 Inexact methods

Another typical way to avoid the potentially-expensive proximal steps is to
update the iterates by inexactly solving (5). In this section, we consider
inexact methods with updates,

$\mathcal{P}(z^{k}-z^{k+1})+\epsilon^{k+1}\in\mathcal{F}(z^{k+1})\ ,$ (16)

where $\epsilon^{k+1}$ is the error for iteration $k+1$. The next theorem
shows that as long as the total error, $\sum_{i=1}^{k}\|\epsilon^{i}\|_{2}$ is
controllable, then the inexact algorithm obtains a reasonable convergence
guarantee when the constraint set of the problem is bounded.

######  Theorem 3.

Consider an iterate update rule (16) with a positive semi-definite matrix $P$
for solving a convex-concave primal-dual problem with bounded region $Z$.
Denote $D$ the diameter of $Z$. The iterates
$\\{z^{k}=(x^{k},\lambda^{k})\\}_{k=1,...,\infty}$ are obtained form the
iterate update rule (16) and the initial solution $z^{0}=(x^{0},\lambda^{0})$.
Denote
$\bar{z}^{k}=(\bar{x}^{k},\bar{\lambda}^{k})=\frac{1}{k}\sum_{i=1}^{k}z^{i}$
as the average iterate. Then it holds for any $k\geq 1$ and a primal-dual
solution $z=(x,\lambda)\in Z$ that

$L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{\|z-z^{0}\|^{2}_{\mathcal{P}}}{2k}+\frac{D\sum_{i=1}^{k}\|\epsilon^{i}\|_{2}}{k}\
.$

######  Remark 2.

Utilizing Theorem 3, we can obtain the convergence guarantees for inexact PDHG
and inexact ADMM. Notice that $\epsilon^{i}$ is essentially the error in
(sub-)gradient of the minimization sub-problem. One can utilize standard
first-order methods (such as gradient descent and accelerated gradient
descent) for the sub-problem with carefully chosen tolerance $\epsilon^{i}$ so
that $\sum_{i=1}^{k}\|\epsilon^{i}\|_{2}$ is bounded.

###### Proof.

Denote $w^{k+1}=(w_{x}^{k+1},w_{\lambda}^{k+1})\in\mathcal{F}(z^{k+1})$. It
then holds by convexity-concavity of $L(x,\lambda)$ that

$\displaystyle\begin{split}&L(x^{k+1},\lambda)-L(x,\lambda^{k+1})\
=L(x^{k+1},\lambda)-L(x^{k+1},\lambda^{k+1})+L(x^{k+1},\lambda^{k+1})-L(x,\lambda^{k+1})\\\
\leq&\left\langle w^{k+1},z^{k+1}-z\right\rangle\ =\left\langle
z^{k}-z^{k+1},z^{k+1}-z\right\rangle_{P}+\langle\epsilon^{k+1},z^{k+1}-z\rangle\\\
=&\frac{1}{2}\|z^{k}-z\|_{P}^{2}-\frac{1}{2}\|z^{k+1}-z\|_{P}^{2}-\frac{1}{2}\|z^{k}-z^{k+1}\|_{P}^{2}+\langle\epsilon^{k+1},z^{k+1}-z\rangle\\\
\
\leq&\frac{1}{2}\|z^{k}-z\|_{P}^{2}-\frac{1}{2}\|z^{k+1}-z\|_{P}^{2}+\langle\epsilon^{k+1},z^{k+1}-z\rangle\\\
\
\leq&\frac{1}{2}\|z^{k}-z\|_{P}^{2}-\frac{1}{2}\|z^{k+1}-z\|_{P}^{2}+D\|\epsilon^{k+1}\|_{2}\
,\end{split}$ (17)

where the last inequality follows from Cauchy-Schwarz inequlity that
$\langle\epsilon^{k+1},z^{k+1}-z\rangle\leq\|\epsilon^{k+1}\|_{2}\|z^{k+1}-z\|_{2}$
and $\|z^{k}-z\|_{2}\leq D$ by the definition of $D$ as diameter of $Z$. We
finish the proof by noticing

$\displaystyle\begin{split}L(\bar{x}^{k},\lambda)-L(x,\bar{\lambda}^{k})\leq\frac{1}{k}\sum_{i=0}^{k-1}L(x^{i+1},\lambda)-L(x,\lambda^{i+1})\leq\frac{1}{2k}\|z^{0}-z\|_{P}^{2}+\frac{D\sum_{i=1}^{k}\|\epsilon^{i}\|_{2}}{k}\
,\end{split}$

where the first inequality comes from convexity-concavity of $L(x,\lambda)$
and the second is from the telescoping. ∎

## Acknowledgement

This work was motivated by obtaining a “teachable” proof on the ergodic rates
of PDHG and ADMM when the first author teaches UChicago BUSN 36919 in 2023.
The authors would like to thank the students of BUSN 36919 for their helpful
discussions during the classes.

## References

  * [1] David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy, _Practical large-scale linear programming using primal-dual hybrid gradient_ , Advances in Neural Information Processing Systems 34 (2021), 20243–20257.
  * [2] Amir Beck, _First-order methods in optimization_ , SIAM, 2017.
  * [3] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al., _Distributed optimization and statistical learning via the alternating direction method of multipliers_ , Foundations and Trends® in Machine learning 3 (2011), no. 1, 1–122.
  * [4] Antonin Chambolle and Thomas Pock, _A first-order primal-dual algorithm for convex problems with applications to imaging_ , Journal of mathematical imaging and vision 40 (2011), 120–145.
  * [5] , _On the ergodic convergence rates of a first-order primal–dual algorithm_ , Mathematical Programming 159 (2016), no. 1-2, 253–287.
  * [6] Jonathan Eckstein and Dimitri P Bertsekas, _On the douglas—rachford splitting method and the proximal point algorithm for maximal monotone operators_ , Mathematical programming 55 (1992), 293–318.
  * [7] R Glowinski and A Marrocco, _Approximation par éléments finis d’ordre un et résolution par pénalisation-dualité d’une classe de problèmes non linéaires. rairo. rech. opér_ , Recherche Opérationelle 9 (1975), no. 2, 41–76.
  * [8] Bingsheng He and Xiaoming Yuan, _Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective_ , SIAM Journal on Imaging Sciences 5 (2012), no. 1, 119–149.
  * [9] , _On the o(1/n) convergence rate of the douglas–rachford alternating direction method_ , SIAM Journal on Numerical Analysis 50 (2012), no. 2, 700–709.
  * [10] Yanli Liu, Yunbei Xu, and Wotao Yin, _Acceleration of primal–dual methods by preconditioning and simple subproblem procedures_ , Journal of Scientific Computing 86 (2021), no. 2, 21.
  * [11] Yurii Nesterov, _Introductory lectures on convex optimization: A basic course_ , vol. 87, Springer Science & Business Media, 2003.
  * [12] Daniel O’Connor and Lieven Vandenberghe, _On the equivalence of the primal-dual hybrid gradient method and douglas–rachford splitting_ , Mathematical Programming 179 (2020), no. 1-2, 85–108.
  * [13] Brendan O’donoghue, Eric Chu, Neal Parikh, and Stephen Boyd, _Conic optimization via operator splitting and homogeneous self-dual embedding_ , Journal of Optimization Theory and Applications 169 (2016), 1042–1068.
  * [14] R Tyrrell Rockafellar, _Monotone operators and the proximal point algorithm_ , SIAM journal on control and optimization 14 (1976), no. 5, 877–898.
  * [15] Ron Shefi and Marc Teboulle, _Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization_ , SIAM Journal on Optimization 24 (2014), no. 1, 269–297.
  * [16] Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, and Stephen Boyd, _Osqp: An operator splitting solver for quadratic programs_ , Mathematical Programming Computation 12 (2020), no. 4, 637–672.
  * [17] Ming Yan, _A new primal–dual algorithm for minimizing the sum of three functions with a linear operator_ , Journal of Scientific Computing 76 (2018), 1698–1717.


mydate [],

# Non-adiabatic theory of the hydrogen bond. Quantum computation?

I. Hubač<EMAIL_ADDRESS>Institute of Physics and Research Centre of
Theoretical Physics and Astrophysics, Silesian University in Opava, Bezručovo
nám. 1150/13, 746 01 Opava, Czech Republic  S. Wilson  ’This paper is
dedicated to the memory of Dr. Stephen Wilson DSC who passed away on 2nd
September, 2020. He played an instrumental role in the initial stages of the
study presented here. The Physical and Theoretical Chemistry Laboratory,
University of Oxford

###### Abstract

The hydrogen bond is usually described within the clamped nucleus
approximation in which electronic and vibrational motions are considered
separately. This approach leads to a double-well potential which facilitates
proton tunnelling. In this work, the hydrogen bond is described by a formalism
based on the non-adiabatic Hamiltonian in which electronic and vibrational
motions are coupled. Quasi-degeneracy associated with the hydrogen bond
supports this approach which is shown to afford an alternative picture of
proton tunnelling.

hydrogen bond, proton tunnelling, non-adiabatic hamiltonian, electron-phonon
interactions, quasi-particles

hydrogen bond, proton tunnelling, non-adiabatic hamiltonian, electron-phonon
interactions, quasi-particles

##  I Introduction

The importance of the hydrogen bond in chemistry and molecular biology cannot
be over-emphasized. For example, hydrogen bonding supports an efficient and
versatile bonding mechanism for biological macromolecules since, although weak
in comparison with covalent and other types of bonds, large numbers of
hydrogen bonds can stabilize macromolecular systems without reducing
flexibility. In 2011, a IUPAC Task Group (Physical and Biophysical Chemistry
Division) [1, 2] recommended a modern evidence-based definition of hydrogen
bonding.

> _‘The hydrogen bond is an attractive interaction between a hydrogen atom
> from a molecule or a molecular fragment XH in which X is more
> electronegative than H, and an atom or a group of atoms in the same or a
> different molecule, in which there is evidence of bond formation.’_

The Task Group state a _‘typical hydrogen bond may be depicted as XH … YZ,
where the three dots denote the bond.’_ Implicit in this picture of the
hydrogen bond is the assumption of the separation of electronic and nuclear
motion contained in the clamped-nucleus or Born-Oppenheimer approximation [3,
4, 5, 6, 7, 8]; an approximation which underpins the concept of molecular
structure [9]. The iupac paper [2] recognizes that _‘One of the most powerful
tools to study hydrogen-bonded systems, or intermolecular interactions in
general, is computational chemistry.’_ Typical examples can be found in an
extensive literature, e.g. [10, 11, 12, 13]. Molecular electronic structure
theory [14] is almost invariably based on the clamped-nucleus approximation
which in turn is dependent _‘on the large ratio between electronic and nuclear
masses’_ [15]. The normal hydrogen atom nucleus, i.e. a proton, is the
lightest of nuclei and therefore its motion is more susceptible to coupling
with the motions of electrons than other, heavier atoms.

The clamped-nucleus treatment of the hydrogen bond leads to a double-well
potential generated by the electrons in which motion of the proton takes
place. The double-well potential allows proton tunnelling.

Electrons are fermions. They are indistinguishable. They can be described by
quantum mechanical many-body theories.

Nuclei can be treated through their vibrational motion. The quantum mechanical
description of the nuclei in a molecule and their interactions with the
electrons can be achieved by introducing a quasi-particle, the phonon. The
phonon is widely used in the study of condensed matter systems. The phonon is
associated with the vibrations of the nuclei about some assumed equilibrium
positions. Our previous work described the general theory of electron-phonon
interactions in molecules [16]. Here we describe the application of this
theoretical apparatus to hydrogen bonds.

In the present study, the _non-adiabatic_ theory of the hydrogen bond is
considered. It involves the quantum mechanical treatment of coupled electronic
and nuclear motion. The key idea is to use effective quasiparticles that
consist of electrons dressed in _phonons_. This construction lends itself
naturally to an image of a Kitaev-like chain of quasiparticles that is a
source of delocalized Majorana fermions. In this way, a pair of hydrogen bonds
(such as A-T base pair) may be endowed with a single quantum bit. Hence, we
point out a possible role of hydrogen bonds as facilitators of quantum
computation that may take place in DNA.

##  II The clamped-nucleus approximation for hydrogen bonds

The separation of electronic and nuclear motion in molecular systems is
ubiquitous in quantum chemistry. This clamped-nucleus or Born-Oppenheimer
approximation [3, 4, 5, 6, 8] underpins the concept of molecular structure
[9]. Physically, because of the large disparity of the electron and nuclear
masses, the electrons are said to adapt instantaneous to any change in the
positions of the nuclei. The electrons generate an effective potential in
which the nuclear motion takes place.

The electronic structure problem [14] can be attacked by exploiting many-body
methods. The many-body problem [17] is attacked first by solving a mean-field
model in which the averaged interactions of the electrons are described and
then by developing a series of corrections, _i.e._ electron correlation. The
total molecular electronic Hamiltonian for a system of M nuclei and N
electrons is written as

$\mathcal{H}_{e}=\sum_{p=1}^{N}h_{p}+\sum_{p>q}^{N}g_{pq}\,,$ (1)

where the one-electron term is the sum of a term describing the kinetic energy
of the electrons and a term arising from the Coulomb attraction between the
electrons and the nuclei:

$h_{p}=-\frac{1}{2}\triangledown_{p}^{2}+\sum_{A=1}^{M}\frac{Z_{A}}{r_{pA}}\,.$
(2)

The two-electron term

$g_{pq}=\frac{1}{r_{pq}}$ (3)

is associated with the Coulomb repulsions between the electrons. Independent
electron models employ an N-electron Hamiltonian of the form:

$\mathcal{H}_{\rm eff}=\sum_{p=1}^{N}(h_{p}+u_{p})\,,$ (4)

where $u_{p}$ is a one-electron, mean-field potential.

The $N$-electron Hamiltonian is written as a sum of $N$ one-electron
Hamiltonians, while $u_{p}$ provides a description of the averaged
interactions between the electrons and also the screening of the nuclear
charges. The total molecular electronic Hamiltonian can be written as

$\mathcal{H}_{e}=\mathcal{H}_{\rm
eff}+\left\\{\sum_{p>q}^{N}g_{pq}-\sum_{p}^{N}u_{p}\right\\}$ (5)

The terms in parenthesis, which are dubbed the ‘fluctuation potential’, will
be small if the independent electron model is well chosen. Much progress was
achieved by employing second quantization formalism. Electronic Hamiltonian
can be written in the so-called normal product (N product) form:

$\displaystyle\mathcal{H}_{e}=$
$\displaystyle\langle\phi_{0}|H|\phi_{0}\rangle+\sum_{i_{1},i_{2}}\langle
i_{1}|f|i_{2}\rangle N[a_{i_{1}}^{+}a_{i_{2}}]$
$\displaystyle+\frac{1}{2}\sum_{i_{1}i_{2}i_{3}i_{4}}\langle
i_{1}i_{2}|g|i_{3}i_{4}\rangle
N[a_{i_{1}}^{+}a_{i_{2}}^{+}a_{i_{4}}a_{i_{3}}]$

This led to diagrammatic many-body Rayleigh-Schr$\ddot{o}$dinger perturbation
theory (MBPT) and coupled cluster (CC) methods [18].

##  III Non-adiabatic Hamiltonian and quasiparticle description of hydrogen
bonds

A description of molecular systems which goes beyond the clamped-nucleus
approximation involves the quantum mechanical treatment of both electronic and
nuclear motion [19]. Detail treatment of separation of electronic and nuclear
motion can be found in the book by Born and Huang (see Appendix VIII) [5].

According to Born and Huang [5] when spacing between two minima
$|E_{i}-E_{j}|$ is comparable to vibrational quantum $\hbar\omega$, we cannot
use Born-Oppenheimer (BO) approximation. Specifically, the condition for using
BO approximation is

$\frac{\hbar\omega}{|E_{i}-E_{j}|}\ll 1\,.$ (7)

In case when this condition is not valid we have to take into consideration
also the coupling of electronic and vibrational motions.

Double-well H-bond potential in DNA is quasi-degenerate (see Fig.1). The
difference between energy levels of both minima being comparable to
$\hbar\omega$ puts us precisely into the situation where validity of BO
approximation is questionable.

Figure 1: Schematic representation of a hydrogen bond in the Born-Oppenheimer
approximation

In our previous work [20, 21, 22] we developed non-adiabatic molecular
Hamiltonian. It is based on second quantization and mixing fermion and boson
statistic. This is quasi-particle concept. We have also shown that our
molecular non-adiabatic Hamiltonian is fully equivalent with non-adiabatic
Hamiltonian used in solid state physics. The creation and annihilation
operators from electronic Hamiltonian are combined with creation and
annihilation operators of harmonic oscillator. The basic idea is the
construction of fermion creation and annihilation operators as depending on
normal coordinate and corresponding momentum of harmonic oscillator.

The quasiparticle transformation relating the crude adiabatic representation
with our new quasiparticle representation may then be written as follows:

$\displaystyle\bar{a}_{P}$
$\displaystyle=a_{P}+\sum\limits_{Q}\sum\limits_{k=1}^{\infty}\frac{1}{k!}\sum\limits_{r_{1}\dots
r_{k}}C_{PQ}^{r_{1}\dots r_{k}}B_{r_{1}}\dots B_{r_{k}}a_{Q}\,,$ (8)
$\displaystyle\bar{a}_{P}^{\dagger}$
$\displaystyle=a_{P}^{\dagger}+\sum\limits_{Q}\sum\limits_{k=1}^{\infty}\frac{1}{k!}\sum\limits_{r_{1}\dots
r_{k}}C_{PQ}^{r_{1}\dots r_{k}}B_{r_{1}}\dots B_{r_{k}}a_{Q}^{\dagger}\,,$ (9)

where $B_{r_{i}}$ are normal coordinates and $C_{PQ}$ are expansion
coefficients. In second quantization, normal coordinates $B$ and corresponding
momentum $\widetilde{B}$ are defined as:

$\displaystyle B$ $\displaystyle=b+b^{\dagger}\,,$ (10)
$\displaystyle\widetilde{B}$ $\displaystyle=b-b^{\dagger}\,.$ (11)

Vibrational Hamiltonian $H_{\rm vibr}$ is given as:

$\displaystyle H_{\rm vibr}$
$\displaystyle=\sum\limits_{r}\hbar\omega_{r}\left(b_{r}^{\dagger}b_{r}+\frac{1}{2}\right)\,,$
(12)

where $b_{r}^{\dagger}$ and $b_{r}$ are bosonic creation and annihilation
operators, respectively. Schematically, quasiparticle transformation is
facilitated by Bogoliubov-like transformation:

$\displaystyle\bar{a}_{P}$ $\displaystyle=\sum_{Q}C_{PQ}(B)a_{Q}\,,$ (13)
$\displaystyle\bar{a}_{P}^{\dagger}$
$\displaystyle=\sum_{Q}C_{PQ}(B)^{\dagger}a_{Q}^{\dagger}\,.$ (14)

This can be generalized to also include momenta as [23]

$\displaystyle\bar{a}_{P}$
$\displaystyle=\sum\limits_{Q}C_{PQ}(B,\tilde{B})a_{Q}\,,$ (15)
$\displaystyle\bar{a}_{P}^{\dagger}$
$\displaystyle=\sum\limits_{Q}C_{PQ}(B,\tilde{B})^{\dagger}a_{Q}^{\dagger}\,.$
(16)

Note that this quasiparticle transformations are completely general without
any departure from exactness, provided that we can specify coefficients
$C_{PQ}$. Without going into details, however, let us now apply the
quasiparticle description to H-bonds to develop the following intuition. Since
the electrons directly couples to vibrations (position and momentum) of the
proton that is delocalized along the hydrogen bond, _the phonon-dressed
fermions ( $\bar{a}_{P}$,$\bar{a}_{P}^{\dagger}$) are thus linearly
delocalized on the hydrogen bond as well_. We propose that due to this
dependence the quasi-particles forms a one-dimensional chain along the bond
that is very similar to a Kitaev chain [24]. The key ingredient is the
effective one-dimensionality. It is known that Kitaev chain represent a stable
coherent state. Formally, this is described using effective Majorana operators
into which any fermionic operator can be decomposed. Schematically:

$\displaystyle\bar{a}_{P}$ $\displaystyle=\gamma_{P,1}+i\gamma_{P,2}\,,$ (17)
$\displaystyle\bar{a}_{P}^{\dagger}$
$\displaystyle=\gamma_{P,1}-i\gamma_{P,2}\,,$ (18)

where $\gamma_{P,1}$ and $\gamma_{P,2}$ are Majorana operators. The edge state
generated by a pair of Majorana operators is delocalized and thus stable
agains local decoherence (see Fig. 2).

##  IV Quantum computation on H-bond of DNA

Let us now assume that our intuitive picture of H-bonds is correct and let us
see what that could imply for the nature of quantum computation that may be
taking place in DNA.

Since A-T base pairs involve two H-bonds, we have four Majorana states on
their edges. Four Majorana form one q-bit. On the other hand, one C-G base
pair has three H-bonds and yields three q-bits that form an entangled state
with quantum entropy (see [16]). In our RAGtime [25] paper, we studied how
effective dynamics of DNA strand may lead to decoherence111This is a
_configurational decoherence_ , not a decoherence in a traditional sense that
concerns a stability of a quantum information due to environment. of H-bonds,
resulting in braiding [24]. Specifically, in [25] paper, we studied the effect
of collision of 2 solitons on double-well H-bonds in DNA. In this way, we
simulated de-coherence, however, the particular mechanism of the decoherence
is not important here. In line with the arguments of Löwdin [26, 27], we can
envisage the braiding on q-bits A-T (T-A) as we set out below.

Figure 2: A Kitaev chain. In product of fermion operators
$c_{1},c_{2}...c_{i}...c_{r}$ each operator is written as a sum of two
Majorana operators $\gamma_{i,1}$ and $\gamma_{i,2}$. The Majorana operators
are then recoupled so as to leave the isolated $\gamma$ operators
$\gamma_{i,1}$ and $\gamma_{i,2}$ at either end of the chain. (The notation of
Leijnse and Flensberg [24])

As we have discussed [16], we treat double-well H-bond potential in DNA as a
non-adiabatic system. Within this, we apply quasiparticle transformation of
non-adiabatic Hamiltonians [16]. This concept leads us to Majorana fermions
and Kitaev chains.

Owing to some dynamics, let us assume that the bond distance between A and T
molecules becomes temporarily shorter. This changes the coupling between the
electronic and the vibrational motions, which is the form of decoherence. As a
result, the double-well potential becomes closer to a single-well one or the
difference between two minima change. Either way, the condition for the
applicability of the BO approximation (7) will be again fulfilled. The protom
may change its position along the potential energy curve. After that, as the
source of de-coherence ceases, the phonon-electron coupling becomes again
dominant and we return to non-adiabatic quasiparticle description. However,
the value of the q-bit on the hydrogen bond has been flipped. This is the
braiding of A - T into ${\rm A}^{*}$ \- ${\rm T}^{*}$ systems. Schematically,
initial states of the two H-bonds

are in this way transformed into:

This is nothing but the braiding as an exchange of
($\gamma_{1}\gamma_{2}\gamma_{3}\gamma_{4}$) into
($\gamma_{1}\gamma_{3}\gamma_{2}\gamma_{4}$) (we follow the notation for A, T,
${\rm A}^{*}$ and ${\rm T}^{*}$ the notation of Löwdin [26, 27]).

Therefore, due to braiding, we have (A - T) $\rightarrow$ (${\rm A}^{*}$ \-
${\rm T}^{*}$). If we assign (A - T) a q-bit $|0\rangle=\left({1\atop
0}\right)$, (${\rm A}^{*}$ \- ${\rm T}^{*}$) q-bit is $|1\rangle=\left({0\atop
1}\right)$. This can lead to computation with one q-bit.

Since one q-bit changes can be extended throughout the DNA we believe that it
can play some role in correction of mutation in DNA or other mechanisms.

Of course, at this point it is impossible to say, whether our speculation is
realized in Nature. A particularly unclear point is the stability of quantum
information. If quantum computing is somehow undergoing in DNA, there must be
some quantum error-correcting mechanism at play, especially in view of (or
because?) mRNA transcription and DNA replication. However, as classic would
say: if quantum computing is possible, it would be strange if Nature did not
find a use for it.

##  V Conclusion

The Born-Oppenheimer (BO) approximation leading to the separation of
vibrational and electronic motion is the main tool used in quantum chemistry
computational programs. The use of this approximation is based on the
disparity between the mass of electron with respect to the nuclei.

As discussed by Born and Huang (Appendix VIII), there are situations when the
use of this this is questionable. Particulary in the case of quasi-degeneracy
in electronic states. Such a situation appears in double-well H-bond potential
in DNA. According to Born and Huang, in such a case we have to take into
account coupling between electronic and vibrational motion.

BO approximation was applied on double-well H-bond potential by Löwdin, who
studied proton tunnelling on double-well potential. However, proton-tunnelling
was not found even using most sophisticated quantum chemistry methods. This
support our idea of quasiparticles based on coupling vibrational and
electronic motion. Hence, it seems that Löwdin’s idea of tunnelling can be
reconsidered as braiding quantum information on hydrogen bonds. Such an
approach lead us to different interpretation of double-well H-bond potential.
As discussed by Lövdin, quoting Delbrück and Schrödinger [28]:

> ‘… These authors emphasized that there ought to be a close parallelism
> between the immense stability of the hereditary substance over thousands of
> years and the stationary state of giant molecule of ‘aperiodic solid,’ and
> that further the discontinuous changes of the genetic code leading to
> mutations should correspond to ‘quantum jumps’ between various stationary
> states. It seems now as if these quantum jumps would be associated with
> proton transfer within the nucleotide bases in the DNA molecule.’ [26]

According to our idea, the stability of DNA is due to coherent state connected
with Majorana fermions (Kitaev chain) on double-well H-bond potential.
Discontinuous changes and quantum jumps are due to decoherence, braiding and
change of q-bits (quantum information).

## Acknowledgement

I.H.wants to thank Mrs. Kathryn Wilson, J. Motyćka MSc, Dr. F. Blaschke and O.
N. Karpíšek MSc for help with preparing the manuscript.

## References

  * [1] R.A. Klein J. Sadlej S. Scheiner I. Alkorta D.C. Clary R.H. Crabtree J.J. Dannenberg P. Hobza H.G. Kjaergaard A.C. Legon B. Mennucci D.J. Nesbitt E. Arunan, G.R. Desiraju.  Definition of the hydrogen bond (iupac recommendations 2011).  Pure Appl. Chem., 83, 1637, (2011).
  * [2] R.A. Klein J. Sadlej S. Scheiner I. Alkorta D.C. Clary R.H. Crabtree J.J. Dannenberg P. Hobza H.G. Kjaergaard A.C. Legon B. Mennucci D.J. Nesbitt E. Arunan, G.R. Desiraju.  Defining thr hydrogen bond: An account ( iupac technical report ).  Pure Appl. Chem., 83, 1637, (2011).
  * [3] M. Born and J.R. Oppenheimer.  Zur quantentheorie der molekuelen.  Ann. Phys., Leipzig, 84, 457, (1927).
  * [4] Max Born.  Die Gültigkeitsgrenze der Theorie der idealen Kristalle und ihre Überwindung, pages 1–16.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1951.
  * [5] M. Born and K. Huang.  Dynamical theory of crystal lattices.  Oxford University Press, (1954).
  * [6] S.M. Blinder.  On the quantum theory of molecules.  with emendations by Brian Sutcliffe and Wolf Geppert, published as an appendix to, (September 2001).
  * [7] W. Kolos and L. Wolniewicz.  Nonadiabatic theory for diatomic molecules and its application to the hydrogen molecule.  Rev. Mod. Phys., 35, 473, (1963).
  * [8] B.T. Sutcliffe.  Handbook of Molecular Physics and Quantum Chemistry Fundamentals 599.  John Wiley, Chichester, (2003).
  * [9] B.T. Sutcliffe.  Handbook of Molecular Physics and Quantum Chemistry Fundamentals 588.  John Wiley, Chichester, (2003).
  * [10] T.H. Dunning K.A. Peterson.  Benchmark calculations with correlated molecular wave functions. vii. the structure and binding energy of the hf dimer.  J. Chem. Phys., 102, 2032, (1995).
  * [11] S. Scheiner.  Ab initio studies of hydrogen bonds: The water dimer paradigm.  Annu. Rev. Phys. Chem., 45, 23, (1994).
  * [12] S. Leutwyler J.A. Frey.  An ab initio benchmark study of hydrogen bonded formamide dimers.  J. Phys. Chem. A, 110, 12512, (2006).
  * [13] C.D. Sherrill T.P. Tauer, M.E. Derrick.  Estimates of the ab initio limit for sulfur-$\pi$ interactions: The h2s-benzene dimer.  J. Phys. Chem. A, 109, 191, (2005).
  * [14] P.F. Bernath S. Wilson and R. McWeeny (eds.).  Handbook of Molecular Physics and Quantum Chemistry 2 Molecular Electronic Structure.  John Wiley, Chichester, (2003).
  * [15] R. McWeeny.  Methods of Molecular Quantum Mechanics.  Academic Press, London, (1989).
  * [16] Miloslav Švec Ivan Hubač and Stephen Wilson.  Quantum entanglement and quantum information in biological systems (dna).  Proceedings of RAGtime, 19, 1 - 5 Nov., (2017).
  * [17] S. Wilson.  Electron correlation in molecules.  Clarendon Press, Oxford, (1984).
  * [18] J. Paldus and Čížek.  Time-independent diagrammatic approach to perturbation theory of fermion systems.  Adv. Quantum Chem., 9, 105-97, (1975)).
  * [19] E. Mátyus.  Pre-born-oppenheimer molecular structure theory.  Molec. Phys., 117, 590609, (2019).
  * [20] I. Hubač and M. Svrček.  The quasiparticle concept in vibrational-electronic problems in molecules.  Rev. Modern Phys, 33, pp. 403-443, ISSN 1097-461X, (1988)).
  * [21] I. Hubač and M. Svrček.  Many-Body Perturbation Theory for Vibrational Electronic Molecular Hamiltonian, in S.Wilson and G. H. F. Diercksen, editors,, volume 293, pp. 471-512, ISBN 978-1-4615-7419-4.  NATO ASI Series (Series B: Physics), Springer, Boston, (1992)).
  * [22] I. Hubač and M. Svrček.  Many-Body Perturbation Theory for Vibrational Electronic Molecular Hamiltonian, in S.Wilson and G. H. F. Diercksen, editors,, volume 4, Molecular vibrations.  Springer US, ISBN 9780306441684, (1992)).
  * [23] M. Svrček.  Ph.d. theis.  Faculty of Mathematics and Physics, Comenius University, Bratislava, (1986).
  * [24] M. Leijnse and K. Flensberg.  Semiconductor Science and Technology, volume 27.  2012\.
  * [25] O. Nicolas Karpíšek M. Švec I. Hubač, F. Blaschke and S. Wilson.  Quantum information in biomolecules: transcription and replication of dna using a soliton model.  Proceedings of RAGtime, 22, 19-23 Oct, (2020).
  * [26] Per-Olov Löwdin.  The normal constants of motion in quantum mechanics treated by projection technique.  Rev. Mod. Phys., 34:520–530, Jul 1962.
  * [27] Per-Olov Löwdin.  Advances in quantum chemistry, volume 2, academic press, 1st edition.  2, (1966).
  * [28] Erwin Schrödinger.  What is Life? The Physical Aspect of the Living Cell.  Cambridge University Press, 1944.