To be continued
Baisc Algorithms
building block
[TOC]
Reference
Mikio Nakahara, Tetsuo Ohmi.《Quantum Computing. From Linear Algebra to Physical Realizations 》
David McMahon. 《Quantum Computing Explained 》
Michael A Nielsen and Isaac Chuang.《Quantum computation and quantum information》, 2002
Ivan B. Djordjevic《Quantum Information Processing, Quantum Computing, and Quantum Error Correction: An Engineering Approach》
Given a state
∣ ψ ⟩ = ∑ j = 0 N − 1 a j ∣ j ⟩ = ( a 0 ⋮ a N − 1 )
|\psi\rangle=\sum_{j=0}^{N-1} a_j|j\rangle=\left(\begin{array}{c}
a_0 \\
\vdots \\
a_{N-1}
\end{array}\right)
∣ ψ ⟩ = j = 0 ∑ N − 1 a j ∣ j ⟩ = ⎝ ⎛ a 0 ⋮ a N − 1 ⎠ ⎞ U Q F T U_{Q F T} U Q F T ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ ∣ ψ ~ ⟩ |\tilde{\psi}\rangle ∣ ψ ~ ⟩ ∣ ψ ~ ⟩ = U Q F T ∣ ψ ⟩
\begin{aligned}
|\tilde{\psi}\rangle=U_{Q F T}|\psi\rangle
\end{aligned}
∣ ψ ~ ⟩ = U Q F T ∣ ψ ⟩ U N Q F T = 1 N ( 1 1 1 1 ⋯ 1 1 ω ω 2 ω 3 ⋯ ω N − 1 1 ω 2 ω 4 ω 6 ⋯ ω 2 ( N − 1 ) 1 ω 3 ω 6 ω 9 ⋯ ω 3 ( N − 1 ) ⋮ ⋮ ⋮ ⋮ ⋮ 1 ω N − 1 ω 2 ( N − 1 ) ω 3 ( N − 1 ) ⋯ ω ( N − 1 ) ( N − 1 ) )
U_{N}^{Q F T}=\frac{1}{\sqrt{N}}\left(\begin{array}{cccccc}
1 & 1 & 1 & 1 & \cdots & 1 \\
1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{N-1} \\
1 & \omega^2 & \omega^4 & \omega^6 & \cdots & \omega^{2(N-1)} \\
1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{3(N-1)} \\
\vdots & \vdots & \vdots & \vdots & & \vdots \\
1 & \omega^{N-1} & \omega^{2(N-1)} & \omega^{3(N-1)} & \cdots & \omega^{(N-1)(N-1)}
\end{array}\right)
U N Q F T = N 1 ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 1 1 1 1 ⋮ 1 1 ω ω 2 ω 3 ⋮ ω N − 1 1 ω 2 ω 4 ω 6 ⋮ ω 2 ( N − 1 ) 1 ω 3 ω 6 ω 9 ⋮ ω 3 ( N − 1 ) ⋯ ⋯ ⋯ ⋯ ⋯ 1 ω N − 1 ω 2 ( N − 1 ) ω 3 ( N − 1 ) ⋮ ω ( N − 1 ) ( N − 1 ) ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞
the orthonormal basis { ∣ j ⟩ } = { ∣ 0 ⟩ , ∣ 1 ⟩ } \{|j\rangle\}=\{|0\rangle ,| 1\rangle \} { ∣ j ⟩ } = { ∣ 0 ⟩ , ∣ 1 ⟩ } ∣ 0 ⟩ → 1 2 ∑ k = 0 1 e i 2 π ⋅ 0 ⋅ k / 2 ∣ k ⟩ = 1 2 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) ∣ 1 ⟩ → 1 2 ∑ k = 0 1 e i 2 π ⋅ 1 ⋅ k / 2 ∣ k ⟩ = 1 2 ( ∣ 0 ⟩ − ∣ 1 ⟩ )
\begin{aligned}
|0\rangle & \rightarrow \frac{1}{\sqrt{2}} \sum_{k=0}^1 e^{i 2 \pi \cdot 0 \cdot k / 2}|k\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\\
|1\rangle & \rightarrow \frac{1}{\sqrt{2}} \sum_{k=0}^1 e^{i 2 \pi \cdot 1 \cdot k / 2}|k\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)
\end{aligned}
∣ 0 ⟩ ∣ 1 ⟩ → 2 1 k = 0 ∑ 1 e i 2 π ⋅ 0 ⋅ k / 2 ∣ k ⟩ = 2 1 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) → 2 1 k = 0 ∑ 1 e i 2 π ⋅ 1 ⋅ k / 2 ∣ k ⟩ = 2 1 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) ∣ ψ ⟩ = α ∣ 0 ⟩ + β ∣ 1 ⟩ |\psi\rangle=\alpha|0\rangle+\beta|1\rangle ∣ ψ ⟩ = α ∣ 0 ⟩ + β ∣ 1 ⟩ U Q F T ∣ ψ ⟩ = U Q F T ( α ∣ 0 ⟩ + β ∣ 1 ⟩ ) = 1 2 ( α + β ) ∣ 0 ⟩ + 1 2 ( α − β ) ∣ 1 ⟩
\begin{aligned}
U_{Q F T}|\psi\rangle=& U_{Q F T} (\alpha|0\rangle+\beta|1\rangle)
\\=&\frac{1}{\sqrt{2}}(\alpha+\beta)|0\rangle+\frac{1}{\sqrt{2}}(\alpha-\beta)|1\rangle
\end{aligned}
U Q F T ∣ ψ ⟩ = = U Q F T ( α ∣ 0 ⟩ + β ∣ 1 ⟩ ) 2 1 ( α + β ) ∣ 0 ⟩ + 2 1 ( α − β ) ∣ 1 ⟩
U Q F T ∣ ψ ⟩ = U Q F T ( α ∣ 0 ⟩ + β ∣ 1 ⟩ ) = α 1 2 [ 1 1 1 − 1 ] ( 1 0 ) + β 1 2 [ 1 1 1 − 1 ] ( 0 1 ) = 1 2 ( α + β ) ( 1 0 ) + 1 2 ( α − β ) ( 0 1 ) = 1 2 ( α + β ) ∣ 0 ⟩ + 1 2 ( α − β ) ∣ 1 ⟩
\begin{aligned}
U_{Q F T}|\psi\rangle=& U_{Q F T} (\alpha|0\rangle+\beta|1\rangle)
\\=&\alpha\frac{1}{\sqrt{2}}\left[\begin{array}{cc}
1 & 1 \\
1 & -1
\end{array}\right]
\left(\begin{array}{c}
1 \\
0
\end{array}\right)+\beta\frac{1}{\sqrt{2}}\left[\begin{array}{cc}
1 & 1 \\
1 & -1
\end{array}\right]
\left(\begin{array}{c}
0 \\
1
\end{array}\right)
\\=&\frac{1}{\sqrt{2}}(\alpha+\beta)\left(\begin{array}{l}
1 \\
0
\end{array}\right)+\frac{1}{\sqrt{2}}(\alpha-\beta)\left(\begin{array}{l}
0 \\
1
\end{array}\right)
\\=&\frac{1}{\sqrt{2}}(\alpha+\beta)|0\rangle+\frac{1}{\sqrt{2}}(\alpha-\beta)|1\rangle
\end{aligned}
U Q F T ∣ ψ ⟩ = = = = U Q F T ( α ∣ 0 ⟩ + β ∣ 1 ⟩ ) α 2 1 [ 1 1 1 − 1 ] ( 1 0 ) + β 2 1 [ 1 1 1 − 1 ] ( 0 1 ) 2 1 ( α + β ) ( 1 0 ) + 2 1 ( α − β ) ( 0 1 ) 2 1 ( α + β ) ∣ 0 ⟩ + 2 1 ( α − β ) ∣ 1 ⟩
the orthonormal basis of 2-qbit system
∣ 0 ⟩ = ∣ 0 1 ⟩ ∣ 0 0 ⟩ \left.|0\rangle=\left|0_1 \rangle \right| 0_0\right\rangle ∣ 0 ⟩ = ∣ 0 1 ⟩ ∣ 0 0 ⟩ ∣ 1 ⟩ = ∣ 0 1 ⟩ ∣ 1 0 ⟩ |1\rangle =| 0_1 \rangle | 1_0\rangle ∣ 1 ⟩ = ∣ 0 1 ⟩ ∣ 1 0 ⟩ ∣ 2 ⟩ = ∣ 1 1 ⟩ ∣ 0 0 ⟩ |2\rangle =| 1_1 \rangle | 0_0 \rangle ∣ 2 ⟩ = ∣ 1 1 ⟩ ∣ 0 0 ⟩ ∣ 3 ⟩ = ∣ 1 1 ⟩ ∣ 1 0 ⟩ |3\rangle=\left|1_1\rangle \right| 1_0 \rangle ∣ 3 ⟩ = ∣ 1 1 ⟩ ∣ 1 0 ⟩
the orthonormal basis transformed into
∣ 0 ⟩ → 1 4 ∑ k = 0 3 e i 2 π ⋅ 0 ⋅ k / 4 ∣ k ⟩ = 1 2 ( ∣ 0 ⟩ + ∣ 1 ⟩ + ∣ 2 ⟩ + ∣ 3 ⟩ ) ∣ 1 ⟩ → 1 4 ∑ k = 0 3 e i 2 π ⋅ 1 ⋅ k / 4 ∣ k ⟩ = 1 2 ( ∣ 0 ⟩ + i ∣ 1 ⟩ − ∣ 2 ⟩ − i ∣ 3 ⟩ ) ∣ 2 ⟩ → 1 4 ∑ k = 0 3 e i 2 π ⋅ 2 k ⋅ / 4 ∣ k ⟩ = 1 2 ( ∣ 0 ⟩ − ∣ 1 ⟩ + ∣ 2 ⟩ − ∣ 3 ⟩ ) ∣ 3 ⟩ → 1 4 ∑ k = 0 3 e i 2 π ⋅ 3 ⋅ k / 4 ∣ k ⟩ = 1 2 ( ∣ 0 ⟩ − i ∣ 1 ⟩ − ∣ 2 ⟩ + i ∣ 3 ⟩ )
\begin{aligned}
|0\rangle & \rightarrow \frac{1}{\sqrt{4}} \sum_{k=0}^3 e^{i 2 \pi \cdot 0 \cdot k / 4}|k\rangle=\frac{1}{2}(|0\rangle+|1\rangle+|2\rangle+|3\rangle)
\\
|1\rangle & \rightarrow \frac{1}{\sqrt{4}} \sum_{k=0}^3 e^{i 2 \pi \cdot 1 \cdot k / 4}|k\rangle=\frac{1}{2}(|0\rangle+i|1\rangle-|2\rangle-i|3\rangle)
\\
|2\rangle & \rightarrow \frac{1}{\sqrt{4}} \sum_{k=0}^3 e^{i 2 \pi \cdot 2 k \cdot / 4}|k\rangle=\frac{1}{2}(|0\rangle-|1\rangle+|2\rangle-|3\rangle)
\\
|3\rangle & \rightarrow \frac{1}{\sqrt{4}} \sum_{k=0}^3 e^{i 2 \pi \cdot 3 \cdot k / 4}|k\rangle=\frac{1}{2}(|0\rangle-i|1\rangle-|2\rangle+i|3\rangle)
\end{aligned}
∣ 0 ⟩ ∣ 1 ⟩ ∣ 2 ⟩ ∣ 3 ⟩ → 4 1 k = 0 ∑ 3 e i 2 π ⋅ 0 ⋅ k / 4 ∣ k ⟩ = 2 1 ( ∣ 0 ⟩ + ∣ 1 ⟩ + ∣ 2 ⟩ + ∣ 3 ⟩ ) → 4 1 k = 0 ∑ 3 e i 2 π ⋅ 1 ⋅ k / 4 ∣ k ⟩ = 2 1 ( ∣ 0 ⟩ + i ∣ 1 ⟩ − ∣ 2 ⟩ − i ∣ 3 ⟩ ) → 4 1 k = 0 ∑ 3 e i 2 π ⋅ 2 k ⋅ / 4 ∣ k ⟩ = 2 1 ( ∣ 0 ⟩ − ∣ 1 ⟩ + ∣ 2 ⟩ − ∣ 3 ⟩ ) → 4 1 k = 0 ∑ 3 e i 2 π ⋅ 3 ⋅ k / 4 ∣ k ⟩ = 2 1 ( ∣ 0 ⟩ − i ∣ 1 ⟩ − ∣ 2 ⟩ + i ∣ 3 ⟩ ) F = 1 2 ( 1 1 1 1 1 ω ω 2 ω 3 1 ω 2 1 ω 2 1 ω 3 ω 2 ω ) = 1 2 ( 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i )
\begin{aligned}
F=&\frac{1}{2}\left(\begin{array}{cccc}
1 & 1 & 1 & 1 \\
1 & \omega & \omega^2 & \omega^3 \\
1 & \omega^2 & 1 & \omega^2 \\
1 & \omega^3 & \omega^2 & \omega
\end{array}\right)
\\=& \frac{1}{2}\left(\begin{array}{cccc}
1 & 1 & 1 & 1 \\
1 & \mathrm{i} & -1 & -\mathrm{i} \\
1 & -1 & 1 & -1 \\
1 & -\mathrm{i} & -1 & \mathrm{i}
\end{array}\right)
\end{aligned}
F = = 2 1 ⎝ ⎜ ⎜ ⎛ 1 1 1 1 1 ω ω 2 ω 3 1 ω 2 1 ω 2 1 ω 3 ω 2 ω ⎠ ⎟ ⎟ ⎞ 2 1 ⎝ ⎜ ⎜ ⎛ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ⎠ ⎟ ⎟ ⎞
ω = e π i / 2 \omega=\mathrm{e}^{\pi \mathrm{i} / 2} ω = e π i / 2
To be continued