summaryrefslogtreecommitdiff
path: root/source/know/concept/quantum-fourier-transform/index.md
blob: 217596bd510270dfdddc25c1fd337ada3fb9dab9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
---
title: "Quantum Fourier transform"
sort_title: "Quantum Fourier transform"
date: 2021-05-01
categories:
- Algorithms
- Quantum information
layout: "concept"
---

The **quantum Fourier transform (QFT)** is a quantum counterpart
of the classical discrete Fourier transform.
It is defined like so, where $$\Ket{x}$$
is an $$n$$-qubit computational basis state $$\Ket{x_1} \cdots \Ket{x_n}$$,
and $$\omega_N$$ is an $$N$$th complex root of unity $$\omega_N^N = 1$$ with $$N = 2^n$$:

$$\begin{aligned}
    \boxed{
        \Ket{x}
        \:\to\:
        \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \Ket{k}
    }
\end{aligned}$$

Note that $$\Ket{x}$$ and $$\Ket{k}$$ refer to the same basis set;
we use these names to clarify which "space" we are considering.
Furthermore, note the sign of the exponent of $$\omega_N$$,
which is the opposite of the classical DFT convention.
In other words, the *forward* QFT corresponds to the *inverse* DFT.

The **inverse quantum Fourier transform (iQFT)** has a different sign in the exponent:

$$\begin{aligned}
    \boxed{
        \Ket{k}
        \:\to\:
        \frac{1}{\sqrt{N}} \sum_{x = 0}^{N - 1} \omega_N^{-xk} \Ket{x}
    }
\end{aligned}$$

The above definitions of the QFT and iQFT describe
the effect on a single basis vector $$\Ket{x}$$,
so the effect on an abitrary superposition follows from linearity,
e.g. for the QFT:

$$\begin{aligned}
    \sum_{x = 0}^{N - 1} c_x \Ket{x}
    \:\to\:
    \sum_{x = 0}^{N - 1} c_x \bigg( \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \Ket{k} \bigg)
\end{aligned}$$

Classically, such a double sum takes
$$\mathcal{O}(N^2) = \mathcal{O}(2^{2n})$$ time to evaluate naively,
with a potential improvement to $$\mathcal{O}(N \log{N}) = \mathcal{O}(n 2^n)$$
for smarter algorithms.
Quantum computers can do a QFT in $$\mathcal{O}(\log^2(N)) = \mathcal{O}(n^2)$$ time,
and approximate it in $$\mathcal{O}(n \log{n})$$ time.

To find out how, we look at the forward QFT,
which maps a basis state $$\Ket{x}$$ to another state $$\Ket{\tilde{x}}$$:

$$\begin{aligned}
    \Ket{x}
    \:\to\:
    \Ket{\tilde{x}}
    = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \Ket{k}
    = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \exp\!\bigg( \frac{i 2 \pi x k}{N} \bigg) \Ket{k}
\end{aligned}$$

We can decompose $$k$$ into its binary representation
$$k_1 2^{n-1} + k_2 2^{n-2} + ... + k_n 2^{0}$$:

$$\begin{aligned}
    \Ket{\tilde{x}}
    &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \exp\!\bigg( \frac{i 2 \pi x}{2^n} \sum_{j = 1}^{n} k_j 2^{n-j} \bigg) \Ket{k}
    \\
    &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \exp\!\bigg( i 2 \pi x \sum_{j = 1}^{n} \frac{k_j}{2^j} \bigg) \Ket{k}
\end{aligned}$$

Expanding the exponential-of-a-sum into a product-of-exponentials then yields:

$$\begin{aligned}
    \Ket{\tilde{x}}
    &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \prod_{j = 1}^{n} \exp\!\bigg( i 2 \pi x \frac{k_j}{2^j} \bigg) \Ket{k}
\end{aligned}$$

If $$k_j = 0$$, the exponential is zero.
We can thus separate this state into its individual qubits:

$$\begin{aligned}
    \Ket{\tilde{x}}
    &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \Ket{0} + \exp\!\Big( \frac{i 2 \pi x}{2^j} \Big) \Ket{1} \bigg)
\end{aligned}$$

Next, we use the trick from before:
decompose $$x$$ as $$x_1 2^{n-1} + x_2 2^{n-2} + ... + x_n 2^{0}$$:

$$\begin{aligned}
    \Ket{\tilde{x}}
    &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \sum_{r = 1}^{n} x_r 2^{n-r-j} \Big) \Ket{1} \bigg)
\end{aligned}$$

The factor $$2^{n-r-j}$$ may be smaller or bigger than $$1$$,
so it is convenient for us to use the following notation
for non-integer binary numbers.
Note the decimal point in the middle:

$$\begin{aligned}
    \left[ a_1 \cdots a_{d} \:.\: a_{d+1} \cdots a_{n} \right]
    = \sum_{r = 1}^{n} a_r 2^{d - r}
\end{aligned}$$

In the above QFT state, the position of the decimal point is $$d = n - j$$,
so we write it as:

$$\begin{aligned}
    \Ket{\tilde{x}}
    &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \Ket{0}
    + \exp\!\Big( i 2 \pi \big[ x_1 \cdots x_{n-j} \:.\: x_{n-j+1} \cdots x_n \big] \Big) \Ket{1} \bigg)
\end{aligned}$$

Because $$\exp(i 2 \pi m) = 1$$ for all integers $$m$$,
we can discard bits before the decimal point:

$$\begin{aligned}
    \Ket{\tilde{x}}
    &= \frac{1}{\sqrt{2^n}} \bigotimes_{j = 1}^{n} \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \big[ 0\:.\: x_{n-j+1} \cdots x_n \big] \Big) \Ket{1} \bigg)
    \\
    &= \frac{1}{\sqrt{2^n}} \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \big[ 0. x_n \big] \Big) \Ket{1} \bigg)
    \otimes \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \big[ 0. x_{n-1} x_n \big] \Big) \Ket{1} \bigg)
    \otimes \cdots
\end{aligned}$$

Furthermore, each exponential can be factorized,
with every factor containing one bit of $$x$$:

$$\begin{aligned}
    \exp\!\Big( i 2 \pi \big[ 0\:.\: x_{n-j+1} \cdots x_n \big] \Big)
    = \exp\!\Big( i 2 \pi \frac{x_{n-j+1}}{2} \Big) \cdots \exp\!\Big( i 2 \pi \frac{x_{n}}{2^{j}} \Big)
\end{aligned}$$

This suggests a way to implement the QFT using
[quantum gates](/know/concept/quantum-gate/) in a circuit.
If the $$j$$th qubit is in $$\Ket{+} = (\Ket{0} + \Ket{1})/\sqrt{2}$$,
then for each bit $$x_{n-j+r}$$ where $$r \in \{1, ..., j\}$$:

+ If $$x_{n-j+r} = 0$$, do nothing.
+ If $$x_{n-j+r} = 1$$, add a relative phase $$2 \pi / 2^{r}$$.

The full QFT algorithm therefore proceeds as follows,
for the $$(n\!-\!j\!+\!1)$$'th input $$\Ket{x_{n-j+1}}$$:

1.  Apply the Hadamard gate $$H$$.
    If $$x_{n-j+1} = 0$$, this puts the qubit in $$\Ket{+}$$.
    If $$x_{n-j+1} = 1$$, this puts the qubit in $$\Ket{+}$$,
    and then adds a phase $$\pi$$, yielding $$\Ket{-}$$.
2.  Apply the phase shift gate $$R_{\phi}$$ controlled by $$x_{n-j+2}$$,
    with angle $$\phi = 2 \pi / 2^{2}$$.
3.  Apply $$R_{\phi}$$ controlled by $$x_{n-j+3}$$,
    with angle $$\phi = 2 \pi / 2^{3}$$...
4.  And so on, until the $$n$$th bit $$x_n$$ is reached,
    and used to control $$R_\phi$$ with $$\phi = 2 \pi / 2^{j}$$.

And so on, for each $$j \in \{1, ..., n\}$$,
and we reach the above expression for $$\Ket{\tilde{x}}$$.
We started from the $$(n\!-\!j\!+\!1)$$'th input qubit,
i.e. we read the input in reverse order.
Therefore all the qubits need to be swapped back to front,
either before or after the above algorithm is run.

The quantum circuit to execute the mentioned steps is illustrated below,
excluding the swapping part to get the right order.
Here, $$R_m$$ means $$R_\phi$$ with $$\phi = 2 \pi / 2^m$$:

{% include image.html file="qft-circuit-noswap.png" width="100%"
    alt="QFT circuit, without final swap" %}

Again, note how the inputs $$\Ket{x_j}$$ and outputs $$\Ket{k_j}$$ are in the opposite order.
The complete circuit, including the swapping at the end,
therefore looks like this:

{% include image.html file="qft-circuit-swap.png" width="85%"
    alt="QFT circuit, including final swap" %}

For each of the $$n$$ qubits, $$\mathcal{O}(n)$$ gates are applied,
so overall the QFT algorithm is $$\mathcal{O}(n^2)$$.



## References
1.  J.S. Neergaard-Nielsen,
    *Quantum information: lectures notes*,
    2021, unpublished.
2.  S. Aaronson,
    *Introduction to quantum information science: lecture notes*,
    2018, unpublished.