3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – sam Jun 13 '16 at 9:07
  • 1
    $\begingroup$ Any idea why $p$ takes only odd values instead of the usual $0,1,\ldots,n-1$? $\endgroup$ – leongz Jun 13 '16 at 10:15
  • 1
    $\begingroup$ @Omar Shehab, Your updated approach is correct and its working (i checked it.) $\endgroup$ – sam Jun 13 '16 at 19:43
  • 1
    $\begingroup$ @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. $\endgroup$ – sam Jun 13 '16 at 20:39
  • 1
    $\begingroup$ $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. $\endgroup$ – sam Jun 13 '16 at 20:49
1
$\begingroup$

\begin{equation} 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} \end{equation} Then \begin{equation} 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} \end{equation} 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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @Omar, Do you find this calculation is correct? $\endgroup$ – sam Jun 18 '16 at 16:21
  • $\begingroup$ why is $b_{-p}b_{p}=-b_{p}b_{-p}$? $\endgroup$ – Omar Shehab Jun 18 '16 at 16:31
  • 1
    $\begingroup$ Fermionic generators anti-commute. Check equation 4.15, of the paper. $\endgroup$ – sam Jun 18 '16 at 16:34
  • 1
    $\begingroup$ Go ahead. You from BD i guess. $\endgroup$ – sam Jun 18 '16 at 16:38
  • 1
    $\begingroup$ If you have any problem, please post here. I will be happy to deal with that. $\endgroup$ – sam Jun 18 '16 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.