解説
問題のとおり、量子フーリエ変換は次式の遷移を満たすオラクルとして定義されます。
∣ j ⟩ n → Q F T 1 2 n ∑ k = 0 2 n − 1 exp ( 2 π i j k 2 n ) ∣ k ⟩ n \begin{equation}
\ket{j}_n \xrightarrow{\mathrm{QFT}} \sqrt{\frac{1}{2^n}} \sum_{k=0}^{2^n-1} \exp{\left(\frac{2\pi i j k}{2^n}\right)} \ket{k}_n
\end{equation} ∣ j ⟩ n QFT 2 n 1 k = 0 ∑ 2 n − 1 exp ( 2 n 2 π ij k ) ∣ k ⟩ n このとき、右辺は、正規化係数 1 / 2 n 1/\sqrt{2^n} 1/ 2 n
∑ k = 0 2 n − 1 exp ( 2 π i j k 2 n ) ∣ k ⟩ n = ∑ k 0 = 0 1 ⋯ ∑ k n − 1 = 0 1 exp ( 2 π i j ∑ l = 0 n − 1 ( 2 l k l ) 2 n ) ∣ k 0 ⋯ k n − 1 ⟩ = ∑ k 0 = 0 1 ⋯ ∑ k n − 1 = 0 1 exp ( 2 π i j ∑ l = 0 n − 1 ( 2 l − n k l ) ) ∣ k 0 ⋯ k n − 1 ⟩ = ( ∑ k 0 = 0 1 e 2 π i j 2 − n k 0 ∣ k 0 ⟩ ) ⊗ ( ∑ k 1 = 0 1 e 2 π i j 2 1 − n k 1 ∣ k 1 ⟩ ) ⊗ ⋯ ⊗ ( ∑ k n − 1 = 0 1 e 2 π i j 2 − 1 k n − 1 ∣ k n − 1 ⟩ ) = ( ∣ 0 ⟩ + e 2 π i 0. j n − 1 ⋯ j 0 ∣ 1 ⟩ ) ⊗ ( ∣ 0 ⟩ + e 2 π i 0. j n − 2 ⋯ j 0 ∣ 1 ⟩ ) ⊗ ⋯ ⊗ ( ∣ 0 ⟩ + e 2 π i 0. j 0 ∣ 1 ⟩ ) \begin{align}
\sum_{k=0}^{2^n-1} \exp{\left(\frac{2\pi i j k}{2^n}\right)} \ket{k}_n
&= \sum_{k_0=0}^{1} \cdots \sum_{k_{n-1}=0}^{1} \exp{\left(\frac{2\pi i j \sum_{l=0}^{n-1} (2^l k_l)}{2^n}\right)} \ket{k_0 \cdots k_{n-1}} \nonumber\\
&= \sum_{k_0=0}^{1} \cdots \sum_{k_{n-1}=0}^{1} \exp{\left(2\pi i j \sum_{l=0}^{n-1} (2^{l-n} k_l)\right)} \ket{k_0 \cdots k_{n-1}} \nonumber\\
&= \left(\sum_{k_0=0}^{1} e^{2\pi i j 2^{-n} k_0}\ket{k_0}\right) \otimes \left(\sum_{k_1=0}^{1} e^{2\pi i j 2^{1-n} k_1}\ket{k_1}\right)\otimes \cdots \otimes \left(\sum_{k_{n-1}=0}^{1} e^{2\pi i j 2^{-1} k_{n-1}}\ket{k_{n-1}}\right) \nonumber\\
&= (\ket{0} + e^{2\pi i 0.j_{n-1} \cdots j_0}\ket{1}) \otimes (\ket{0} + e^{2\pi i 0.j_{n-2} \cdots j_0}\ket{1}) \otimes \cdots \otimes (\ket{0} + e^{2\pi i 0.j_{0}}\ket{1})
\end{align} k = 0 ∑ 2 n − 1 exp ( 2 n 2 π ij k ) ∣ k ⟩ n = k 0 = 0 ∑ 1 ⋯ k n − 1 = 0 ∑ 1 exp ( 2 n 2 π ij ∑ l = 0 n − 1 ( 2 l k l ) ) ∣ k 0 ⋯ k n − 1 ⟩ = k 0 = 0 ∑ 1 ⋯ k n − 1 = 0 ∑ 1 exp ( 2 π ij l = 0 ∑ n − 1 ( 2 l − n k l ) ) ∣ k 0 ⋯ k n − 1 ⟩ = ( k 0 = 0 ∑ 1 e 2 π ij 2 − n k 0 ∣ k 0 ⟩ ) ⊗ ( k 1 = 0 ∑ 1 e 2 π ij 2 1 − n k 1 ∣ k 1 ⟩ ) ⊗ ⋯ ⊗ k n − 1 = 0 ∑ 1 e 2 π ij 2 − 1 k n − 1 ∣ k n − 1 ⟩ = ( ∣ 0 ⟩ + e 2 π i 0. j n − 1 ⋯ j 0 ∣ 1 ⟩ ) ⊗ ( ∣ 0 ⟩ + e 2 π i 0. j n − 2 ⋯ j 0 ∣ 1 ⟩ ) ⊗ ⋯ ⊗ ( ∣ 0 ⟩ + e 2 π i 0. j 0 ∣ 1 ⟩ ) ただし、0. x 0 x 1 ⋯ x m = ∑ k = 0 m 2 − ( k + 1 ) x k 0.x_0x_1 \cdots x_m = \sum_{k=0}^{m} 2^{-(k+1)} x_k 0. x 0 x 1 ⋯ x m = ∑ k = 0 m 2 − ( k + 1 ) x k
(2) 式の操作は、次の量子回路（n = 3 n=3 n = 3
QCoder・Qiskit ではリトルエンディアンを採用しているため、一般的な量子回路図 とはビットの並びが逆になっていることに注意して下さい。
例えば、この図で 3 3 3
∣ j 2 ⟩ → H ( ∣ 0 ⟩ + e 2 π i 0. j 2 ∣ 1 ⟩ ) / 2 → C P ( π / 2 , 1 , 2 ) ( ∣ 0 ⟩ + e 2 π i 0. j 2 j 1 ∣ 1 ⟩ ) / 2 → C P ( π / 4 , 0 , 2 ) ( ∣ 0 ⟩ + e 2 π i 0. j 2 j 1 j 0 ∣ 1 ⟩ ) / 2 \begin{align}
\ket{j_2}
&\xrightarrow{H} (\ket{0} + e^{2\pi i 0.j_2}\ket{1})/\sqrt{2}\nonumber\\
&\xrightarrow{CP(\pi/2, 1, 2)} (\ket{0} + e^{2\pi i 0.j_2j_1}\ket{1})/\sqrt{2}\nonumber\\
&\xrightarrow{CP(\pi/4, 0, 2)} (\ket{0} + e^{2\pi i 0.j_2j_1j_0}\ket{1})/\sqrt{2}
\end{align} ∣ j 2 ⟩ H ( ∣ 0 ⟩ + e 2 π i 0. j 2 ∣ 1 ⟩ ) / 2 C P ( π /2 , 1 , 2 ) ( ∣ 0 ⟩ + e 2 π i 0. j 2 j 1 ∣ 1 ⟩ ) / 2 C P ( π /4 , 0 , 2 ) ( ∣ 0 ⟩ + e 2 π i 0. j 2 j 1 j 0 ∣ 1 ⟩ ) / 2 最後にスワップゲートによってこの状態は 1 1 1 1 1 1 ( ∣ 0 ⟩ + e 2 π i 0. j 2 j 1 j 0 ∣ 1 ⟩ ) / 2 (\ket{0} + e^{2\pi i 0.j_2j_1j_0}\ket{1})/\sqrt{2} ( ∣ 0 ⟩ + e 2 π i 0. j 2 j 1 j 0 ∣ 1 ⟩ ) / 2
ゲートを左に詰めていくことでこの量子回路の深さは 2 n 2n 2 n
量子フーリエ変換はショアのアルゴリズムや量子位相推定などの量子アルゴリズムに用いられる重要なサブルーチンとして知られています。
writer 解説
解答例
解答例は以下の通りです。
import math
from qiskit import QuantumCircuit
def solve ( n : int ) -> QuantumCircuit: qc = QuantumCircuit(n)
for i in reversed ( range (n)): qc.h(i) for j in reversed ( range (i)): qc.cp(math.pi / 2 ** (i - j), j, i)
for i in range (n // 2 ): qc.swap(i, n - i - 1 )
return qc 
