# Replacing fermionic operators with their Fourier transform and boundary conditions

In the section 4.1 of Quantum Computation by Adiabatic Evolution, Farhi et al proposes a quantum adiabatic algorithm to solve the $2$-SAT problem on a ring. To compute the complexity of the algorithm the authors computed the energy gap between the ground and first excited states of the adiabatic Hamiltonian.

The adiabatic Hamiltonian is defined as $$\tilde{H} (s) = (1-s) \sum^n_{j=1}(1-\sigma^{(j)}_x) + s \sum^n_{j=1}\frac{1}{2} (1-\sigma^{(j)}_z \sigma^{(j+1)}_z )$$

Then the adiabatic Hamiltonian is reexpressed using fermionic operators as follows.

$$\tilde{H}(s) = \sum^n_{j=1} \left\{2 (1-s)b^\dagger_j b_j + \frac{s}{2}(1-(b^\dagger_j - b_j)(b^\dagger_{j+1} + b_{j+1}))\right\}$$

Then the authors takes the Fourier transform of the fermionic operators,

$$\beta_p = \frac{1}{\sqrt{n}} \sum^n_{j=1} e^{i\pi p j/n} b_j$$ where $p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)$,

and rewrite the adiabatic Hamiltonian as

$$\tilde{H}(s) = \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} A_p (s)$$ where $$A_p (s) = 2 (1-s)[\beta^\dagger_p \beta_p + \beta^\dagger_{-p} \beta_{-p}] + s \left\{1 - \cos\frac{\pi p}{n} [\beta^\dagger_p \beta_p - \beta_{-p} \beta^\dagger_{-p}] + i \sin \frac{\pi p}{n}[\beta^\dagger_{-p} \beta^\dagger_{p} - \beta_{p} \beta_{-p}]\right\}.$$

My question:

How can I derive the second part i.e. $s \left\{1 - \cos\frac{\pi p}{n} [\beta^\dagger_p \beta_p - \beta_{-p} \beta^\dagger_{-p}] + i \sin \frac{\pi p}{n}[\beta^\dagger_{-p} \beta^\dagger_{p} - \beta_{p} \beta_{-p}]\right\}$?

My attempt:

We compute few quantities.

$$\beta^\dagger_p \beta_p = \left(\frac{1}{\sqrt{n}}\sum^n_{k=1}e^{-i\pi p k/n}b^\dagger_k\right)\left(\frac{1}{\sqrt{n}}\sum^n_{j=1}e^{i\pi p j/n}b_j\right) \\ =\frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_k b_j$$,

$$\beta^\dagger_{-p} \beta_{-p} = \left(\frac{1}{\sqrt{n}} \sum^n_{k=1} e^{i\pi p k/n} b^\dagger_k\right)\left(\frac{1}{\sqrt{n}} \sum^n_{j=1} e^{-i\pi p j/n} b_j\right) \\ =\frac{1}{n} \sum^n_{k,j=1}e^{i\pi p (k-j)/n} b^\dagger_k b_j$$,

$$\beta_{-p} \beta^\dagger_{-p} = \left( \frac{1}{\sqrt{n}} \sum^n_{j=1} e^{-i\pi p j/n} b_j\right)\left( \frac{1}{\sqrt{n}} \sum^n_{k=1} e^{i\pi p k/n} b^\dagger_k\right) \\ =\frac{1}{n} \sum^n_{k,j=1}e^{i\pi p (k-j)/n} b_j b^\dagger_k$$,

$$\beta^\dagger_{-p} \beta^\dagger_{p} = \left(\frac{1}{\sqrt{n}} \sum^n_{j=1} e^{i\pi p j/n} b^\dagger_j\right)\left(\frac{1}{\sqrt{n}} \sum^n_{k=1} e^{-i\pi p k/n} b^\dagger_k\right) \\ =\frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_j b^\dagger_k$$,

and

$$\beta_{p} \beta_{-p} = \left(\frac{1}{\sqrt{n}} \sum^n_{j=1} e^{i\pi p j/n} b_j\right)\left(\frac{1}{\sqrt{n}} \sum^n_{k=1} e^{-i\pi p k/n} b_k\right) \\ =\frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b_j b_k$$.

We also compute two linear combinations of these quantities.

\begin{align} \beta^\dagger_{p} \beta_{p} - \beta_{-p} \beta^\dagger_{-p} &= \frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_k b_j - \frac{1}{n} \sum^n_{k,j=1}e^{i\pi p (k-j)/n} b_j b^\dagger_k \nonumber\\ &= \frac{1}{n} \left( \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_k b_j - \sum^n_{k,j=1}e^{i\pi p (k-j)/n} b_j b^\dagger_k\right) \nonumber\\ &= \frac{1}{n} \left( \sum^n_{k,j=1}\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right. \nonumber\\ & \left. - \sum^n_{k,j=1} \left(\cos \left(\pi p (k-j)/n\right) + i \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right) \nonumber\\ &= \frac{1}{n} \sum^n_{k,j=1} \left(\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right. \nonumber\\ & \left. - \left(\cos \left(\pi p (k-j)/n\right) + i \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right) \end{align}

and

\begin{align} \beta^\dagger_{-p} \beta^\dagger_{p} - \beta_{p} \beta_{-p} &= \frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_j b^\dagger_k - \frac{1}{n} \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b_j b_k \nonumber\\ &= \frac{1}{n} \left( \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b^\dagger_j b^\dagger_k - \sum^n_{k,j=1}e^{-i\pi p (k-j)/n} b_j b_k\right) \nonumber\\ &= \frac{1}{n} \left( \sum^n_{k,j=1}\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right. \nonumber\\ & \left.- \sum^n_{k,j=1}\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right) \nonumber\\ &= \frac{1}{n} \sum^n_{k,j=1} \left( \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right. \nonumber\\ & \left.- \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right) \end{align}.

So, \begin{align} 1 - \cos \frac{\pi p}{n}\left[\beta^\dagger_p \beta_p - \beta_{-p} \beta^\dagger_{-p}\right] + i \sin \frac{\pi p}{n} \left[\beta^\dagger_{-p} \beta^\dagger_p - \beta_p \beta_{-p}\right] = \nonumber\\ 1 - \cos \frac{\pi p}{n}\left[\frac{1}{n} \sum^n_{k,j=1} \left(\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right. \right. \nonumber\\ - \left. \left. \left(\cos \left(\pi p (k-j)/n\right) + i \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right)\right] \nonumber\\ + i \sin \frac{\pi p}{n} \left[\frac{1}{n} \sum^n_{k,j=1} \left( \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right. \right. \nonumber\\ - \left. \left. \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right)\right] \nonumber\\ = 1 - \frac{1}{n} \cos \frac{\pi p}{n}\left[ \sum^n_{k,j=1} \left(\left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right. \right. \nonumber\\ - \left. \left. \left(\cos \left(\pi p (k-j)/n\right) + i \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right)\right] \nonumber\\ + \frac{1}{n}i \sin \frac{\pi p}{n} \left[ \sum^n_{k,j=1} \left( \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right. \right. \nonumber\\ - \left. \left. \left(\cos \left(\pi p (k-j)/n\right) - i \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right)\right] \nonumber\\ = 1 - \frac{1}{n} \left[ \sum^n_{k,j=1} \left(\left(\cos \frac{\pi p}{n} \cos \left(\pi p (k-j)/n\right) - i\cos \frac{\pi p}{n} \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_k b_j \right. \right. \nonumber\\ - \left. \left. \left(\cos \frac{\pi p}{n} \cos \left(\pi p (k-j)/n\right) + i \cos \frac{\pi p}{n} \sin \left(\pi p (k-j)/n\right) \right) b_j b^\dagger_k\right)\right] \nonumber\\ + \frac{1}{n}i \left[ \sum^n_{k,j=1} \left( \left(\sin \frac{\pi p}{n} \cos \left(\pi p (k-j)/n\right) - i \sin \frac{\pi p}{n} \sin \left(\pi p (k-j)/n\right)\right) b^\dagger_j b^\dagger_k \right. \right. \nonumber\\ - \left. \left. \left(\sin \frac{\pi p}{n} \cos \left(\pi p (k-j)/n\right) - i \sin \frac{\pi p}{n} \sin \left(\pi p (k-j)/n\right)\right) b_j b_k\right)\right] \end{align}

I am not sure how to get to $1-(b^\dagger_j - b_j)(b^\dagger_{j+1} + b_{j+1})$ from here.

Update 1:

Following the comment by @mas, I am starting with Eq. 4.14 i.e. the inverse Fourier transform.

\begin{align} b_j &= \frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p \end{align}

So,

$$\sum^n_{j=1} (b^\dagger_j - b_j)(b^\dagger_{j+1} + b_{j+1}) = \\ \sum^n_{j=1} (\frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} \beta^\dagger_p - \frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p)(\frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p (j+1)/n} \beta^\dagger_p + \frac{1}{\sqrt{n}} \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p (j+1)/n} \beta_p) \\ =\sum^n_{j=1} \frac{1}{n} ( \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} \beta^\dagger_p - \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p)( \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p (j+1)/n} \beta^\dagger_p + \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p (j+1)/n} \beta_p) \\ =\sum^n_{j=1} \frac{1}{n} ( \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} \beta^\dagger_p \sum_{q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi q (j+1)/n} \beta^\dagger_q - \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p \sum_{q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi q (j+1)/n} \beta^\dagger_q + \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} \beta^\dagger_p \sum_{q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi q (j+1)/n} \beta_q - \sum_{p = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} \beta_p \sum_{q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi q (j+1)/n} \beta_q) \\ =\sum^n_{j=1} \frac{1}{n} ( \sum_{p,q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} e^{i\pi q (j+1)/n} \beta^\dagger_p \beta^\dagger_q - \sum_{p,q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} e^{i\pi q (j+1)/n} \beta_p \beta^\dagger_q + \sum_{p,q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{i\pi p j/n} e^{-i\pi q (j+1)/n} \beta^\dagger_p \beta_q - \sum_{p,q = \pm 1, \pm 3, \ldots, \pm \left(n-1\right)} e^{-i\pi p j/n} e^{-i\pi q (j+1)/n} \beta_p \beta_q)$$

I am still stuck.

• Instead of starting with (4.13), If you start with the inverse transformation given by equation (4.14) can carry out the calculation you have done. that will lead the desired expression. – sam Jun 13 '16 at 9:07
• Any idea why $p$ takes only odd values instead of the usual $0,1,\ldots,n-1$? – leongz Jun 13 '16 at 10:15
• @Omar Shehab, Your updated approach is correct and its working (i checked it.) – sam Jun 13 '16 at 19:43
• @Omar Shehab, when $p=q$, that gives a contribution like $e^{2\pi\theta} e^{\frac{ip\pi }{n}}$. Then we have to use $e^{2\pi\theta}=1$. There is a sum over $p$ in $\beta_{p}^{\dagger}\beta_{p}^{\dagger}$. As $\beta's$ are Fermioni c that is why $\beta^{2}=0$. Therefore only the terms survive in the sum over $p$ must comes with opposite sign of $p$. Which is in fact leads the term $\beta^{\dagger}_{-p}\beta^{\dagger}_{p}+\text{hermition conjugate}$ with a $i\sin\theta$-multiplied with it. – sam Jun 13 '16 at 20:39
• $b^{\dagger}_{j}b_{j}=\frac{1}{n}\sum_{p,q}e^{\frac{ij\pi (q-p)}{n}}\beta_{q}^{\dagger}\beta_{q}=\frac{1}{n}\sum_{p,q}n\delta_{pq}\beta_{q}^{\dagger}\beta_{p}=\sum_{p}\beta_{p}^{\dagger}\beta_{p}=\beta_{p}^{\dagger}\beta_{p}+\beta_{-p}^{\dagger}\beta_{-p}$. This is the first term. – sam Jun 13 '16 at 20:49

$$b_{j} = \frac{1}{\sqrt{n}}\sum_{p}e^{-i\pi pj/n}\beta_{p}\qquad b_{j+1} = \frac{1}{\sqrt{n}}\sum_{p}e^{-i\pi q(j+1)/n}\beta_{q}$$ Then $$b_{j}^{\dagger}b_{j+1}^{\dagger} = \frac{1}{n}\sum_{p,q}e^{\pi i(p+q)j/n}e^{\pi iq/n}\beta_{q}^{\dagger}\beta_{p}^{\dagger} = \sum_{p} e^{-\pi ip/n}\beta_{-p}^{\dagger}\beta_{p}^{\dagger}$$ Likewise $b_{j}b_{j+1}= \sum_{p} e^{\pi ip/n}\beta_{-p}\beta_{p}$. Then \begin{eqnarray} b_{j}^{\dagger}b_{j+1}^{\dagger}-b_{j}b_{j+1} & = & \sum_{p} [e^{-\pi ip/n}\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-e^{\pi ip/n}\beta_{-p}\beta_{p}] \\ & = & \sum_{p}e^{-\pi ip/n}[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-e^{2\pi ip/n}\beta_{-p}\beta_{p}]\\ & = & \sum_{p}e^{-\pi ip/n}[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}]\quad\boxed{\text{using}~e^{2\theta}=1}\\ & = & \sum_{p}(\cos\frac{\pi p}{n}-i\sin\frac{\pi p}{n})[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}]\\ & = & -2i\sum_{p}\sin\left(\frac{\pi p}{n}\right)[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}] \\ \Rightarrow -\frac{1}{2}[b_{j}^{\dagger}b_{j+1}^{\dagger}-b_{j}b_{j+1}] & = & i\sum_{p}\sin\left(\frac{\pi p}{n}\right)[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}] \\ \end{eqnarray} Which is the desired expression. Lets check the term $\sum_{p}(\cos\frac{\pi p}{n}-i\sin\frac{\pi p}{n})[\beta_{-p}^{\dagger}\beta_{p}^{\dagger}-\beta_{-p}\beta_{p}]$ for $p=\pm 1$ (setting $\frac{1}{n}=m$) \begin{eqnarray} (\cos\pi m-i\sin\pi m)[\beta_{-1}^{\dagger}\beta_{1}^{\dagger}-\beta_{-1}\beta_{1}]+[\cos(-\pi m)-i\sin(-\pi m)][\beta_{1}^{\dagger}\beta_{-1}^{\dagger}-\beta_{1}\beta_{-1}] & = & -2i\sin(\pi m)[\beta_{-1}^{\dagger}\beta_{1}^{\dagger}-\beta_{-1}\beta_{1}] \end{eqnarray} (There $b_{-p}b_{p}=-b_{p}b_{-p}$ has been used). Therefore no contribution comes from cosine terms. Likewise rest of the expression follows.
• why is $b_{-p}b_{p}=-b_{p}b_{-p}$? – Omar Shehab Jun 18 '16 at 16:31