Review: Quantum arithmetic with the Quantum Fourier Transform¶

Original Paper¶

https://arxiv.org/pdf/1411.5949.pdf

Prerequisition¶

Quantum Fourier Transform
(Optional) Phase estimation

Short Summary¶

Quantum Fourier Transform Based
- $+, \times$
  - signed integer, non-modular integer
- $\sum a_{x} x$
  - controlled version gives the inner product of two data vectors
$| x ⟩ | y ⟩ \overset{Q F T}{\to} | x ⟩ | ϕ (y) ⟩ \overset{C Z}{\to} | x ⟩ | ϕ (x + y) ⟩ \overset{{Q F T}^{- 1}}{\to} | x ⟩ | x + y ⟩$

List of Techniques¶

QFT

Conclusion¶

Arithmetic that can be implemented and its complexity.

here $n$ is the $\log M$ where $M$ is the maximum number, and $N$ is the number of numbers

Name	Exact Formula	Circuit Complexity
Qudit Addition Mod D	${\| x + y (\mod d) ⟩}_{d}$	$O (n^{2})$
Qudit Addition	${\| x + y ⟩}_{d}$	$O (n^{2})$
Addition	$\| x + y ⟩$	$O (n^{2})$
(Constant) Weighted Sum	$\| \sum_{m = 1}^{N} a_{m} x_{m} ⟩$	$O (N n^{2})$
Multiplication	$\| a b ⟩$	$O (n^{3})$
Controlled Weighted Sum (Inner Product)	$\| \sum_{m = 1}^{N} a_{m} x_{m} ⟩$	$O (N n^{3})$

Detailed Notes¶

The Quantum Fourier Transform and distributed phase encoding¶

$Q F T | x ⟩ = \frac{1}{\sqrt{d}} \sum_{k = 0}^{d - 1} e^{i \frac{2 π x k}{d}} | k ⟩$
$I Q F T | k ⟩ = \frac{1}{\sqrt{d}} \sum_{x = 0}^{d - 1} e^{- i \frac{2 π x k}{d}} | x ⟩$

Adder (Qudits)¶

Generalized CZ Gate¶

${C Z}^{F} | x ⟩ | y ⟩ = e^{\frac{i 2 π}{F d} x y}$
- $d$ is the dimension of the quantum system (qudit)

Modular Addition $| x + y (\mod d) ⟩$ ¶

{Q F T}_{2}^{†} {C Z}_{12} {Q F T}_{2} | x ⟩ | y ⟩ = | x ⟩ | x + y (\mod d) ⟩

encodes number $y$ into the phase basis \begin{equation} \ket{x}\ket{y} \stackrel{{\scriptsize{QFT}}2}{\longrightarrow} \frac{1}{\sqrt{d}} \sum^{d-1} e^{i\frac{ 2 \pi y k }{d}}\ket{x}\ket{k} \end{equation}

The phase gate introduces a phase shift that is equivalent to a modulo $d$ addition in that basis $\frac{1}{\sqrt{d}} \sum_{k = 0}^{d - 1} e^{i \frac{2 π y k}{d}} | x ⟩ | k ⟩ \overset{C Z}{⟶} \frac{1}{\sqrt{d}} \sum_{k = 0}^{d - 1} e^{i \frac{2 π y k}{d}} e^{i \frac{2 π x k}{d}} | x ⟩ | k ⟩ .$

Finally, the inverse QFT takes the result back into the computational basis with \begin{equation} \begin{split} \frac{1}{\sqrt{d}} \sum_{k=0}^{d-1} e^{i\frac{2\pi (x+y) k }{d}} \ket{x}\ket{k} \stackrel{{\scriptsize{IQFT}}2}{\longrightarrow} \frac{1}{d}\sum^{d-1} e^{i\frac{ 2 \pi (x+y) k }{d}} e^{-i\frac{ 2 \pi k l }{d}} \ket{x}\ket{l} \ = \ket{x}\ket{x+y\pmod d}.
\end{split} \end{equation}

Adding More Integers Together (With More Quidits)¶

{I Q F T}_{N} \cdot C Z_{1, N} \dots C Z_{N - 2, N} \cdot C Z_{N - 1, N} \cdot {Q F T}_{N} | x_{1} ⟩ | x_{2} ⟩ \dots | x_{N - 1} ⟩ | x_{N} ⟩ = | x_{1} ⟩ | x_{2} ⟩ \dots | x_{N - 1} ⟩ | x_{1} + x_{2} + \dots + x_{N} (\mod d) ⟩ .

Non-Modular Addition¶

\begin{equation} C!Z \ket{x}d\ket{y}=e^{i\frac{ 2 \pi x y}{2d-1}}\ket{x}d\ket{y}. \end{equation} - To sum $N$ numbers, $d^{'} = N d - N + 1$ is required - Signed addition for numbers up to $d / 2$ - positive $x < d / 2$ into states $| x ⟩$ - negative numbers $- x$ into states $| d - x ⟩$ - negative numbers are associated to negative phases

Adder (Qubit) (Draper's circuit)¶

Consider the addition of numbers encoded in $n$ qubits. $a = a_{1} 2^{n - 1} + a_{2} 2^{n - 2} + \dots + a_{n} 2^{0}$ $| a ⟩ | a_{1} ⟩ \otimes | a_{2} ⟩ \otimes \dots \otimes | a_{n} ⟩$

Draper's circuit¶

Evolving $| a ⟩$ into $| ϕ (a) ⟩$ $| ϕ (a) ⟩ = Q! F! T | a ⟩ = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} e^{i \frac{2 π a k}{N}} | k ⟩,$
To take $| ϕ (a) ⟩$ into $| ϕ (a + b) ⟩$ . To perform the addition, the circuit decomposes the $C Z$ gates to the following. These gates are controlled by the $n$ qubits that represent the number $b$ . The combined effect of all the gates is to introduce a total phase $e^{\frac{2 π i b k}{N}}$ for each state $| k ⟩$ , $R_{l} = [\begin{array}{cc} 1 & 0 0 & e^{\frac{2 π i}{2^{l}}} \end{array}] .$

Non-modular adder¶

$| a ⟩ = | 0 ⟩ | a_{1} ⟩ | a_{2} ⟩ \dots | a_{n} ⟩$ .

Remaining Q¶

exact circuit
- add in fourier basis?

Mean¶

\begin{equation} \begin{split} {I!Q!F!T}{N+1} \left(\prod^{N} C!Z_{m,N+1}^N \right) {Q!F!T}{N+1}\ket{x_1}\ket{x_2}\ldots\ket{x_N}\ket{0}=\ \ket{x_1}\ket{x_2}\ldots\ket{x_N}\left|\frac{1}{N}\sum^{N} x_m\pmod d\right \rangle, \end{split} \end{equation} - In general, the result is not an integer. - Sol1: fixed point representation, $\log_{2} (N d)$ qubits we recover the correct mean value - Sol2: phase estimation quantum algorithms - for $d = 2^{m}$ , give the best possible $m$ -bit approximation to any arbitray phase $ϕ$ between 0 and 1 in a term $e^{i 2 π ϕ}$ with a probability of, at least, $4 / π^{2}$ , which can be improved at the cost of a larger circuit \cite{CEM98}.

(Constant) Weighted Sum¶

\begin{equation} \begin{split} {I!Q!F!T}{N+1} \left(\prod^{N} C!Z_{m,N+1}^{\frac{1}{a_m}} \right) {Q!F!T}{N+1}\ket{x_1}\ket{x_2}\ldots\ket{x_N}\ket{0}=\ \ket{x_1}\ket{x_2}\ldots\ket{x_N}\left|\sum^{N} a_mx_m\pmod d\right \rangle, \end{split} \end{equation} - In general, the result is not an integer. - Sol1: fixed point representation, $\log_{2} (N d)$ qubits we recover the correct mean value - Sol2: phase estimation quantum algorithms - for $d = 2^{m}$ , give the best possible $m$ -bit approximation to any arbitray phase $ϕ$ between 0 and 1 in a term $e^{i 2 π ϕ}$ with a probability of, at least, $4 / π^{2}$ , which can be improved at the cost of a larger circuit \cite{CEM98}. - Also, the values in range may be bigger - Sol: Ancillary bit

Multiplication by a constant¶

(b_{1} 2^{n - 1} \cdot b_{2} 2^{n - 2} \dots b_{n - 1} 2^{1} \cdot b_{n} 2^{0}) x = \sum_{m = 1}^{n} b_{m} 2^{n - m} x,

QFT Multiplier¶

$2^{m} Σ$ takes $| a ⟩ | ϕ (0) ⟩$ to $| a ⟩ | ϕ (0 + a) ⟩$ Apply for all $m$ $| ϕ (0 + b_{n} 2^{0} a + b_{n - 1} 2^{1} a + \dots + b_{2} 2^{n - 2} a + b_{1} 2^{n - 1} a) ⟩ = | ϕ (0 + a b) ⟩ = | ϕ (a b) ⟩ .$

The key to compute the product $a \cdot b$ is to select the proper conditional phase rotation gates to implement each QFT adder block.

After computing the QFT of $0$ , we obtain the output state $Q! F! T | 0 ⟩ = \frac{1}{\sqrt{2^{2 n}}} \sum_{k = 0}^{2^{2 n} - 1} e^{i \frac{2 π 0 k}{2^{2 n}}} | k ⟩ = | ϕ (0) ⟩,$ where $k = k_{1} 2^{2 n - 1} + k_{2} 2^{2 n - 2} + \dots + k_{2 n} 2^{0} = \sum_{s = 1}^{2 n} k_{s} 2^{2 n - s}$ . In order to take $| ϕ (0) ⟩$ to $| ϕ (0 + b_{j} 2^{n - j} a) ⟩$ , we need to use phase rotation gates controlled by $b_{j}$ and by each $a_{i}$ , chosen so that they apply a phase rotation $e^{i \frac{2 π (a_{i} 2^{n - i} b_{j} 2^{n - j}) k_{s} 2^{2 n - s}}{2^{2 n}}} = e^{i \frac{2 π a_{i} b_{j} k_{s}}{2^{i + j + s - 2 n}}} .$ Therefore, we select conditional rotation gates of the form $R_{l} = R_{i + j + s - 2 n}$ , where $i + j + s - 2 n > 0$ , to implement the QFT adder block controlled by $b_{j}$ .

The size of ancillary 0 can be chosen freely to avoid modular.

Controlled Weighted Sum¶

$\sum_{m = 1}^{N} a_{m} x_{m}$ - $a_{m}$ can be in superposition - implementation $| a_{1} ⟩ | x_{1} ⟩ | a_{2} ⟩ | x_{2} ⟩ \otimes \dots \otimes | a_{N} ⟩ | x_{N} ⟩ | ϕ (0 + a_{1} x_{1} + a_{2} x_{2} + \dots + a_{N} x_{N}) ⟩ .$ - this gives inner product!

Last update: 2023-09-15