What is QFT?
computational basis set {∣ 0 ⟩ |0\rangle ∣ 0 ⟩ ∣ 1 ⟩ |1\rangle ∣ 1 ⟩ ∣ N − 1 ⟩ |N-1\rangle ∣ N − 1 ⟩ ∣ 0 ~ ⟩ |\tilde{0}\rangle ∣ 0 ~ ⟩ ∣ 1 ~ ⟩ |\tilde{1}\rangle ∣ 1 ~ ⟩ ∣ N − 1 ~ ⟩ |\widetilde{N-1}\rangle ∣ N − 1 ⟩ U Q F T U_{QFT} U Q F T
기존 베이시스와 푸리에 변환 이후 basis 의 차이. 아랫쪽 fourier basis 의 경우, 위상을 가진 것처럼 평면을 회전하는 것을 확인할 수 있다.
computational basis 의 coefficient 를 x j x_{j} x j y k y_{k} y k
y k = 1 N ∑ j = 0 N − 1 e x p ( i 2 π j k N ) x j y_{k}=\frac{1}{\sqrt{N}}\sum \limits_{j=0}^{N-1}exp(i\frac{2\pi jk}{N})x_{j} y k = N 1 j = 0 ∑ N − 1 e x p ( i N 2 π j k ) x j Discrete Fourier Transform 과 식의 모양은 같다.
basis 로 표현한 수식은 아래와 같다.
∣ b ~ ⟩ = 1 N ∑ a = 0 N − 1 e x p ( i 2 π a b N ) ∣ a ⟩ |\tilde{b}\rangle = \frac{1}{\sqrt{N}}\sum \limits_{a=0}^{N-1} exp(i\frac{2\pi ab}{N})|a\rangle ∣ b ~ ⟩ = N 1 a = 0 ∑ N − 1 e x p ( i N 2 π a b ) ∣ a ⟩ 이때 ∣ a ⟩ = ∣ a 1 a 2 . . . a n ⟩ = 2 n − 1 y 1 + 2 n − 2 y 2 + . . . + 2 0 y n |a\rangle = |a_{1}a_{2}...a_{n}\rangle = 2^{n-1}y_{1}+2^{n-2}y_{2}+...+2^{0}y_{n} ∣ a ⟩ = ∣ a 1 a 2 . . . a n ⟩ = 2 n − 1 y 1 + 2 n − 2 y 2 + . . . + 2 0 y n y = ∑ k = 1 n y k 2 n − k y=\sum\limits_{k=1}^{n}y_{k} 2^{n-k} y = k = 1 ∑ n y k 2 n − k
∣ b ~ ⟩ = 1 N ∑ a = 0 N − 1 e ( i 2 π a b N ) ∣ a ⟩ |\tilde{b}\rangle = \frac{1}{\sqrt{N}}\sum \limits_{a=0}^{N-1} e^{(i\frac{2\pi ab}{N})}|a\rangle ∣ b ~ ⟩ = N 1 a = 0 ∑ N − 1 e ( i N 2 π a b ) ∣ a ⟩ = 1 N ∑ a = 0 N − 1 ∏ k = 1 n e ( i 2 π b a k a k ) ∣ a ⟩ =\frac{1}{\sqrt{N}}\sum \limits_{a=0}^{N-1}\prod\limits_{k=1}^{n} e^{(i\frac{2\pi ba_{k}}{a^{k}})}|a\rangle = N 1 a = 0 ∑ N − 1 k = 1 ∏ n e ( i a k 2 π b a k ) ∣ a ⟩ = 1 N ( ∣ 0 ⟩ + e 2 π i b / 2 1 ∣ 1 ⟩ ) ⊗ ( ∣ 0 ⟩ + e 2 π i b / 2 2 ∣ 1 ⟩ ) ⊗ . . . ⊗ ( ∣ 0 ⟩ + e 2 π i b / 2 n ∣ 1 ⟩ ) =\frac{1}{\sqrt{N}}(|0\rangle+e^{2\pi i b/2^{1}}|1\rangle)\otimes(|0\rangle+e^{2\pi i b/2^{2}}|1\rangle)\otimes...\otimes(|0\rangle+e^{2\pi i b/2^{n}}|1\rangle) = N 1 ( ∣ 0 ⟩ + e 2 π i b / 2 1 ∣ 1 ⟩ ) ⊗ ( ∣ 0 ⟩ + e 2 π i b / 2 2 ∣ 1 ⟩ ) ⊗ . . . ⊗ ( ∣ 0 ⟩ + e 2 π i b / 2 n ∣ 1 ⟩ ) QFT를 적용하기 전인 ∣ a ⟩ = ∣ a 1 ⟩ ∣ a 2 ⟩ . . . ∣ a n ⟩ |a\rangle=|a_{1}\rangle |a_{2}\rangle ... |a_{n}\rangle ∣ a ⟩ = ∣ a 1 ⟩ ∣ a 2 ⟩ . . . ∣ a n ⟩
이때 ∣ b ~ ⟩ |\tilde{b}\rangle ∣ b ~ ⟩
∣ 00...0 ⟩ |00...0\rangle ∣ 0 0 . . . 0 ⟩ e 2 π i b / 2 n ∣ 00...01 ⟩ e^{2\pi i b/2^{n}}|00...01\rangle e 2 π i b / 2 n ∣ 0 0 . . . 0 1 ⟩ e 2 π i b / 2 n − 1 ∣ 00...10 ⟩ e^{2\pi i b/2^{n-1}}|00...10\rangle e 2 π i b / 2 n − 1 ∣ 0 0 . . . 1 0 ⟩ e 2 π i b ( 1 2 + 1 2 2 + . . . + 1 2 n ) ∣ 11...11 ⟩ e^{2\pi i b(\frac{1}{2}+\frac{1}{2^2}+...+\frac{1}{2^n})}|11...11\rangle e 2 π i b ( 2 1 + 2 2 1 + . . . + 2 n 1 ) ∣ 1 1 . . . 1 1 ⟩
Example
For N=2, {∣ 0 ⟩ , ∣ 1 ⟩ |0\rangle,|1\rangle ∣ 0 ⟩ , ∣ 1 ⟩ → \rightarrow → ∣ 0 ~ ⟩ , ∣ 1 ~ ⟩ |\tilde{0}\rangle,|\tilde{1}\rangle ∣ 0 ~ ⟩ , ∣ 1 ~ ⟩
∣ 0 ~ ⟩ |\tilde{0}\rangle ∣ 0 ~ ⟩ 1 2 ( 1 ∗ ∣ 0 ⟩ + 1 ∗ ∣ 1 ⟩ ) = ∣ + ⟩ \frac{1}{\sqrt{2}}(1*|0\rangle+1*|1\rangle)=|+\rangle 2 1 ( 1 ∗ ∣ 0 ⟩ + 1 ∗ ∣ 1 ⟩ ) = ∣ + ⟩
∣ 1 ~ ⟩ |\tilde{1}\rangle ∣ 1 ~ ⟩ 1 2 ( 1 ∗ ∣ 0 ⟩ − 1 ∗ ∣ 1 ⟩ ) = ∣ − ⟩ \frac{1}{\sqrt{2}}(1*|0\rangle-1*|1\rangle)=|-\rangle 2 1 ( 1 ∗ ∣ 0 ⟩ − 1 ∗ ∣ 1 ⟩ ) = ∣ − ⟩
QFT performes a transform on the basis state.
In general, for N = 2 n N=2^{n} N = 2 n
∣ b ~ ⟩ = 1 2 n ( ∣ 0 ⟩ + e x p ( i π b ) ∣ 1 ⟩ ) ⊗ ( ∣ 0 ⟩ + e x p ( i π 2 b ) ∣ 1 ⟩ ) ⊗ . . . |\tilde{b}\rangle = \frac{1}{\sqrt{2^{n}}}(|0\rangle+exp(i\pi b)|1\rangle)\otimes(|0\rangle+exp(i\frac{\pi}{2} b)|1\rangle)\otimes... ∣ b ~ ⟩ = 2 n 1 ( ∣ 0 ⟩ + e x p ( i π b ) ∣ 1 ⟩ ) ⊗ ( ∣ 0 ⟩ + e x p ( i 2 π b ) ∣ 1 ⟩ ) ⊗ . . . ⊗ ( ∣ 0 ⟩ + e x p ( i π 2 n − 1 b ) ∣ 1 ⟩ ) \otimes(|0\rangle+exp(i\frac{\pi}{2^{n-1}} b)|1\rangle) ⊗ ( ∣ 0 ⟩ + e x p ( i 2 n − 1 π b ) ∣ 1 ⟩ ) 오퍼레이터 U Q F T U_{QFT} U Q F T
U Q F T = 1 N ∑ a = 0 N − 1 ∑ b = 0 N − 1 exp ( i 2 π a b N ) ∣ a ⟩ ⟨ b ∣ U_{QFT} = \frac{1}{\sqrt{N}}\sum\limits_{a=0}^{N-1}\sum\limits_{b=0}^{N-1} \exp{(i\frac{2\pi ab}{N})}|a\rangle \langle b| U Q F T = N 1 a = 0 ∑ N − 1 b = 0 ∑ N − 1 exp ( i N 2 π a b ) ∣ a ⟩ ⟨ b ∣ ∣ b ~ ⟩ = U Q F T ∣ b ⟩ |\tilde{b}\rangle = U_{QFT}|b\rangle ∣ b ~ ⟩ = U Q F T ∣ b ⟩ Application : Period Finding
f ( x ) f(x) f ( x ) a x a^{x} a x f ( x ) f(x) f ( x ) f ( x ) = 1 f(x)=1 f ( x ) = 1 x = r x=r x = r a r − 1 a^{r}-1 a r − 1 a r − 1 a^{r}-1 a r − 1 ( a r / 2 + 1 ) ( a r / 2 − 1 ) (a^{r/2}+1)(a^{r/2}-1) ( a r / 2 + 1 ) ( a r / 2 − 1 )
그럼 r을 어떻게 찾느냐? 고전적인 컴퓨터로는 N = 2 n N=2^{n} N = 2 n f ( x ) f(x) f ( x )
소인수 분해를 하려면 greate common divisor 를 찾는 과정도 필요한데, 오일러 알고리즘에 따르면 gcd 를 찾는것은 O ( n ) O(n) O ( n )
referenceqiskit QFT documentation qiskit 유튜브 강의
