Addition by Fourier transform

Carsten Urbach

This corresponds to problem 5.6 in Nielsen & Chuang. The original paper is (Draper 2000). Which quantum circuit can be used to perform the computation $$|x\rangle\quad\to\quad |x + y \mod 2^n\rangle$$ with $0\leq x < 2^n$ and a constant integer $y$.

We exploit the general idea $$x+y = \log\left(\mathrm{e}^x\mathrm{e}^y\right)$$ where the exponentiation is de facto performed by a Fourier trafo and the logarithm by the inverse trafo.

Fourier transforming the state $|x\rangle$ with $n$ bits, leads to the following product representation $$|x\rangle\ = |x_n x_{n-1} \ldots x_1\rangle\ \to\ \frac{1}{2^n}(|0\rangle + e^{2\pi i 0.x_1}|1\rangle)(|0\rangle + e^{2\pi i 0.x_2x_1}|1\rangle)\cdots (|0\rangle + e^{2\pi i 0.x_n\ldots x_1}|1\rangle)$$ where we use the notation $$x = x_1 2^0 + x_2 2^1 + \ldots + x_n 2^{n-1}$$ and $$0.x_l \ldots x_1\ \equiv\ \frac{x_l}{2} + \frac{x_{l-1}}{2^{2}} + \ldots + \frac{x_1}{2^{l}}\,.$$ Now, we apply a phase shift $R_\theta(\theta)$ to each qubit $$R_z\ \equiv\ \begin{pmatrix} 1 & 0\\ 0 & \exp(i\theta)\\ \end{pmatrix}\,.$$ We apply $R_\theta$ with $\theta_j = 2\pi y/2^{n-(j-1)}$ to qubit $j$ where $1\leq j\leq n$. For $y$ we can also write $$y\ =\ y_1 2^0 + y_2 2^1 + \ldots + y_n 2^{n-1}\,.$$ Thus, $$\exp(2\pi i y/2^{n-j+1}) = \prod_{k=0}^{n-1} \exp(2\pi i y_{k+1} 2^{j-1-n+k})\,.$$ Since $\exp(2\pi i y_k l) = 1$ for positive integer $l$, this reduces to (recall $y_k\in\{0,1\}$) $$\exp(2\pi i y/2^{n-j+1}) = \prod_{k=0}^{n-j} \exp(2\pi i y_{k+1} 2^{j-1-n+k})\,.$$ The $n$th qubit gets multiplied with $\exp(i\theta_n)$ with $\theta_n = 2\pi y /2^{1}$. Thus, we need to compute $$\exp(2\pi i x_1/2)\cdot \exp(2\pi i y_1/2) = \exp(2\pi i (x_1 + y_1) /2)\,.$$ Similarly, for the $j$th qubit one gets $$\exp(2\pi i (x_1/2^{n-j+1} + x_2/2^{n-j} + ...))\cdot \exp(2\pi i (y_1/2^{n-j+1} + y_2/2^{n-j} + ...)) = \exp(2\pi i ((x_1 + y_1) /2^{n-j+1} + (x_2 + y_2)/2^{n-j} + ...))$$ which implements the addition $\mod n$ operation in this binary fraction.

Now apply the inverse Fourier trafo and it is easy to see that this transforms back to the state $|x+y\mod n\rangle$.

For the practical implementation we first need the phase shift operators, which is up to a phase identical to $R_z$:

Rtheta <- function(bit, theta=0.) {
  return(methods::new("sqgate", bit=as.integer(bit),
                      M=array(as.complex(c(1, 0, 0, exp(1i*theta))),
                              dim=c(2,2)), type="Rt"))
}

With this one can write the desired function on state $x$.

addbyqft <- function(x, y) {
  n <- x@nbits
  z <- qsimulatR::qft(x)
  for(j in c(1:n)) {
    z  <- Rtheta(bit=j, theta = 2*pi*y/2^(n-j+1)) * z
  }
  z <- qft(z, inverse=TRUE)
  return(invisible(z))
}

Examples

x <- qstate(5, basis=as.character(seq(0, 2^5-1)))
x

   ( 1 )    * 0 

z <- addbyqft(x, 3)
z

   ( 1 )    * 3 

z <- addbyqft(z, 5)
z

   ( 1 )    * 8 

z <- addbyqft(z, 30)
z

   ( 1 )    * 6