summaryrefslogtreecommitdiff
path: root/source/know/concept/quantum-fourier-transform
diff options
context:
space:
mode:
authorPrefetch2022-10-20 18:25:31 +0200
committerPrefetch2022-10-20 18:25:31 +0200
commit16555851b6514a736c5c9d8e73de7da7fc9b6288 (patch)
tree76b8bfd30f8941d0d85365990bcdbc5d0643cabc /source/know/concept/quantum-fourier-transform
parente5b9bce79b68a68ddd2e51daa16d2fea73b84fdb (diff)
Migrate from 'jekyll-katex' to 'kramdown-math-sskatex'
Diffstat (limited to 'source/know/concept/quantum-fourier-transform')
-rw-r--r--source/know/concept/quantum-fourier-transform/index.md86
1 files changed, 43 insertions, 43 deletions
diff --git a/source/know/concept/quantum-fourier-transform/index.md b/source/know/concept/quantum-fourier-transform/index.md
index 5595fa2..113367c 100644
--- a/source/know/concept/quantum-fourier-transform/index.md
+++ b/source/know/concept/quantum-fourier-transform/index.md
@@ -10,9 +10,9 @@ 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$:
+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{
@@ -22,9 +22,9 @@ $$\begin{aligned}
}
\end{aligned}$$
-Note that $\Ket{x}$ and $\Ket{k}$ refer to the same basis set;
+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$,
+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.
@@ -39,7 +39,7 @@ $$\begin{aligned}
\end{aligned}$$
The above definitions of the QFT and iQFT describe
-the effect on a single basis vector $\Ket{x}$,
+the effect on a single basis vector $$\Ket{x}$$,
so the effect on an abitrary superposition follows from linearity,
e.g. for the QFT:
@@ -50,14 +50,14 @@ $$\begin{aligned}
\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)$
+$$\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.
+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}}$:
+which maps a basis state $$\Ket{x}$$ to another state $$\Ket{\tilde{x}}$$:
$$\begin{aligned}
\Ket{x}
@@ -67,8 +67,8 @@ $$\begin{aligned}
= \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}$:
+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}}
@@ -84,7 +84,7 @@ $$\begin{aligned}
&= \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.
+If $$k_j = 0$$, the exponential is zero.
We can thus separate this state into its individual qubits:
$$\begin{aligned}
@@ -93,14 +93,14 @@ $$\begin{aligned}
\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}$:
+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$,
+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:
@@ -110,7 +110,7 @@ $$\begin{aligned}
= \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$,
+In the above QFT state, the position of the decimal point is $$d = n - j$$,
so we write it as:
$$\begin{aligned}
@@ -119,7 +119,7 @@ $$\begin{aligned}
+ \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$,
+Because $$\exp(i 2 \pi m) = 1$$ for all integers $$m$$,
we can discard bits before the decimal point:
$$\begin{aligned}
@@ -132,7 +132,7 @@ $$\begin{aligned}
\end{aligned}$$
Furthermore, each exponential can be factorized,
-with every factor containing one bit of $x$:
+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)
@@ -141,42 +141,42 @@ $$\begin{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 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}$.
++ 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,
+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$:
+Here, $$R_m$$ means $$R_\phi$$ with $$\phi = 2 \pi / 2^m$$:
<a href="qft-circuit-noswap.png">
<img src="qft-circuit-noswap.png" style="width:100%">
</a>
-Again, note how the inputs $\Ket{x_j}$ and outputs $\Ket{k_j}$ are in the opposite order.
+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:
@@ -184,8 +184,8 @@ therefore looks like this:
<img src="qft-circuit-swap.png" style="width:85%">
</a>
-For each of the $n$ qubits, $\mathcal{O}(n)$ gates are applied,
-so overall the QFT algorithm is $\mathcal{O}(n^2)$.
+For each of the $$n$$ qubits, $$\mathcal{O}(n)$$ gates are applied,
+so overall the QFT algorithm is $$\mathcal{O}(n^2)$$.