解説
問題のとおり、量子フーリエ変換は次式の遷移を満たすオラクルとして定義されます。
∣ 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 πijk ) ∣ k ⟩ 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 0 = 0 1 e 2 π i j 2 1 − n k 1 ∣ k 1 ⟩ ) ⊗ ⋯ ⊗ ( ∑ k 0 = 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_0=0}^{1} e^{2\pi i j 2^{1-n} k_1}\ket{k_1}\right)\otimes \cdots \otimes \left(\sum_{k_0=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 πijk ) ∣ 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 0 = 0 ∑ 1 e 2 πij 2 1 − n k 1 ∣ k 1 ⟩ ) ⊗ ⋯ ⊗ ( k 0 = 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 − 1 2 − ( k + 1 ) x k 0.x_0x_1 \cdots x_m = \sum_{k=0}^{m-1} 2^{-(k+1)} x_k 0. x 0 x 1 ⋯ x m = ∑ k = 0 m − 1 2 − ( k + 1 ) x k
(2) 式の操作は、次の量子回路（n = 3 n=3 n = 3
QCoder・Qiskit ではリトルエンディアンを採用しているため、一般的な回路図 とはビットの並びが逆になっていることに注意して下さい。
例えば、この図で 3 つ目の量子ビットの状態は次のように遷移します。
∣ j 2 ⟩ → H ( ∣ 0 ⟩ + e 2 π i 0. j 2 ∣ 1 ⟩ ) / 2 → C P ( π / 2 , 1 , 0 ) ( ∣ 0 ⟩ + e 2 π i 0. j 2 j 1 ∣ 1 ⟩ ) / 2 → C P ( π / 4 , 2 , 0 ) ( ∣ 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, 0)} (\ket{0} + e^{2\pi i 0.j_2j_1}\ket{1})/\sqrt{2}\nonumber\\
&\xrightarrow{CP(\pi/4, 2, 0)} (\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 CP ( π /2 , 1 , 0 ) ( ∣ 0 ⟩ + e 2 πi 0. j 2 j 1 ∣ 1 ⟩ ) / 2 CP ( π /4 , 2 , 0 ) ( ∣ 0 ⟩ + e 2 πi 0. j 2 j 1 j 0 ∣ 1 ⟩ ) / 2 最後にスワップゲートによってこの状態は 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 
