Addition by Fourier transform

In qsimulatR: A Quantum Computer Simulator

library(knitr)
library(qsimulatR)
knitr::opts_chunk$set(fig.align='center',
                      comment='')

This corresponds to problem 5.6 in Nielsen & Chuang. The original paper is [@draper2000addition]. 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
z <- addbyqft(x, 3)
z
z <- addbyqft(z, 5)
z
z <- addbyqft(z, 30)
z

qsimulatR documentation built on Oct. 16, 2023, 5:06 p.m.