Following are the 3 classes of Quantum Algorithms:

1. Based on Quantum versions of Fourier Transform:
   • DJ Algos’s Hadamard Transform
   • Shor’s algorithm form Factoring & Discrete Logarithms
2. Quantum Search Algorithm
3. Quantum simulations

Introduction

• Has rich applications in areas of Signal/Information processing from spectroscopy to telecommunication.

• A mathematical/integral transform maps a function from its function space into another functions space. We can also map back to the orignal function space via inverse transform.

• Fourier Transform: A mathematical transform that decomposes a waveform (function/signal) into an alternate representation characterized by sine & cosine functions of varying frequencies.

  Ex: Decomposing the waveform of a musical chord into terms of intensity of contituent pitches.

• It is noted that a Fourier Transformed version of a problem is easier to solve than the Orignal version.

Implementation Efficiency

• Fourier transform is being actively used due to its discrete version known as Discrete Fourier Transform (DFT) which is being implemented in a computationally efficient manner in the form of Fast Fourier Transform (FFT).
• Quantum Version of the Fourier Transform is Quantum Fourier Trasnform.
• It is similar to the classical FFT, but adds the advantage of Quantum Parallelism leading to a exponentially faster implementation.
• Given an input data of size $N = 2^n$ numbers,
  • FFT executes it in $N.log_2N = n.2^n$ steps
  • QFT executes it in $O(log_2^2(N)) = O(n^2)$ steps.

An Informal Introduction

• The Discrete Fourier Transform acts on a vector $(x_0, \dots, x_{N-1})$ and maps it to the vector $(y_0, \dots, y_{N-1})$ according to the formula:

  $\boxed{y_k = \frac{1}{\sqrt{N}}\normalsize\sum_{j=0}^{N-1}x_j\large e^{2\pi i\frac{jk}{N}}}$

• Similarly, the quantum Fourier transform acts on a quantum state:

  $\ket{X} = \sum_{j=0}^{N-1}x_j\ket{j}$

  and maps it to the quantum state:

  $\ket{Y} = \sum_{k=0}^{N-1}y_k\ket{k}$

  according to the formula:

  $\boxed{y_k = \frac{1}{\sqrt{N}}\normalsize\sum_{j=0}^{N-1}x_j\large e^{2\pi i\frac{jk}{N}}}$

  or, simply for a basis state $\ket{X}$, the QFT can also be expressed as a map:

  $\boxed{QFT : \ket{j} \rarr \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\large e^{2\pi i\frac{jk}{N}}\normalsize\ket{k}}$

  As, notice from the above expression for $y_k$ each basis state $x_j$ contributes a factor of $\large e^{2\pi i\frac{jk}{N}}$to the state $y_k$.

  which, for an $n$ qubit system can be written as:

  $\boxed{QFT : \ket{j} \rarr \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\large e^{2\pi i\frac{jk}{2^n}}\normalsize\ket{k}}$

• Example:

  Suppose there are 2 states in $H^{\otimes n}$ : $\ket{\psi}$ & $\ket{\psi’}$, such that:

  $\ket{\psi’} = QFT\ket{\psi}$

  Then, if (for$N = 2^{n}$):

  $\ket{\psi} = x_1\ket{0} + x_2\ket{1} + \dots + x_{N-1}\ket{N-1}$

  and,

  $\ket{\psi'} = y_1\ket{0} + y_2\ket{1} + \dots + y_{N-1}\ket{N-1}$

  $\boxed{QFT: \sum_{j=0}^{n-1}x_j\ket{j} \rarr \sum_{k=0}^{n-1}x_k\ket{k}}$

  or, simply

  $\boxed{QFT: \ket{\psi} \rarr \ket{\psi'}}$

Formal Definition

• The Quantum Fourier Transform $F$ on the Hilbert Space $H^{\otimes N}$ wrt to an n-Qubit quantum system is:

  $\boxed{F = \frac{1}{\sqrt{2^n}}\sum_{x,y = 0}^{2^n - 1}\large e^{\frac{2\pi i}{2^n}x.y}\ket{x}\bra{y}}$

  Here, as one might notice $\ket{x}$ & $\ket{y}$ represent the computation basis of $H^{\otimes n}$.

• Recall from the chapter matrices & operators that, the above equation represents an operator of order $2^n$ (or simply a $2^n \times 2^n$ matrix).

• Taking $w_n = \large e^{\frac{2\pi i}{2^n}}$, we can write the above operator $F$ as:

  $F = \Large \frac{1}{\sqrt{2^n}}\normalsize \left[\begin{matrix}1 & 1 & 1 & \dots & 1 \\ 1 & w_n & w_n^2 & \dots & w_n^{2^{n}-1} \\ 1 & w_n^2 & w_n^4 & \dots & w_n^{2(2^{n}-1)} \\ \vdots & \vdots & \vdots & \dots & \vdots \\ 1 & w_n^{2^{n}-1} & w_n^{2(2^{n}-1)} & \dots & w_n^{(2^{n}-1)^{2}} \end{matrix}\right]$

  The above matrix is noted to be Unitary.

Simplifying the QFT Equation