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