양자 컴퓨터로 푸리에 변환하면 고속 푸리에 변환보다 빠른
이산 푸리에 변환?
이산 푸리에 변환 은 푸리에 변환을 이산화한 것입니다. 오시마 (ぉぃ
음, 모두 좋아하는 주파수 분해를 하기 위한 것으로, 음성 처리라든지 화상 처리라든지 무선 통신이라든지 여러가지 곳에서 보는 위대한 녀석입니다. 식은 이런 느낌입니다.
y_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} n k}
이하, $N=8$ 의 경우를 쫓아 갑시다.
$w = e^{\frac{-\pi i}{4}}$ 라고 놓으면, 아래의 행렬 계산으로 나타낼 수 있는 것이 간입니다.
\begin{pmatrix}
y_{0} \\
y_{1} \\
y_{2} \\
y_{3} \\
y_{4} \\
y_{5} \\
y_{6} \\
y_{7} \\
\end{pmatrix} =
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{1} & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} \\
w^{0} & w^{2} & w^{4} & w^{6} & w^{8} & w^{10} & w^{12} & w^{14} \\
w^{0} & w^{3} & w^{6} & w^{9} & w^{12} & w^{15} & w^{18} & w^{21} \\
w^{0} & w^{4} & w^{8} & w^{12} & w^{16} & w^{20} & w^{24} & w^{28} \\
w^{0} & w^{5} & w^{10} & w^{15} & w^{20} & w^{25} & w^{30} & w^{35} \\
w^{0} & w^{6} & w^{12} & w^{18} & w^{24} & w^{30} & w^{36} & w^{42} \\
w^{0} & w^{7} & w^{14} & w^{21} & w^{28} & w^{35} & w^{42} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{pmatrix} \\
고속 푸리에 변환!
고속 푸리에 변환은 이산 푸리에 변환을 가속화합니다 (ぉ
분할통치법을 사용한 Cooley-Tukey형의 알고리즘이 유명하고, 왼쪽에서 오른쪽으로 수치를 흘리는 회로처럼 쓰면 이런 느낌이 듭니다. 사선이 교차하는 곳을 나비 연산이라고합니다.
입력열의 순서를 비트 반전을 하는 것이 미소로, 예를 들어 입력의 $x_3$ 의 첨자는 2진수라고 011이므로 반전시켜 110, 즉 0으로부터 세어 6번째에 둡니다.
이런 식으로 앞의 행렬 계산을 변형하면,
\begin{pmatrix}
y_{0} \\
y_{1} \\
y_{2} \\
y_{3} \\
y_{4} \\
y_{5} \\
y_{6} \\
y_{7} \\
\end{pmatrix} =
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{2} & w^{6} & w^{1} & w^{5} & w^{3} & w^{7} \\
w^{0} & w^{8} & w^{4} & w^{12} & w^{2} & w^{10} & w^{6} & w^{14} \\
w^{0} & w^{12} & w^{6} & w^{18} & w^{3} & w^{15} & w^{9} & w^{21} \\
w^{0} & w^{16} & w^{8} & w^{24} & w^{4} & w^{20} & w^{12} & w^{28} \\
w^{0} & w^{20} & w^{10} & w^{30} & w^{5} & w^{25} & w^{15} & w^{35} \\
w^{0} & w^{24} & w^{12} & w^{36} & w^{6} & w^{30} & w^{18} & w^{42} \\
w^{0} & w^{28} & w^{14} & w^{42} & w^{6} & w^{35} & w^{21} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{4} \\
x_{2} \\
x_{6} \\
x_{1} \\
x_{5} \\
x_{3} \\
x_{7} \\
\end{pmatrix}
이 8x8 행렬을 $F_8$ 로 두고 분해하면,
\begin{align}
F_8 = \ &
\begin{pmatrix}
1 &&&& w^{0} \\
& 1 &&&& w^{1} \\
&& 1 &&&& w^{2} \\
&&& 1 &&&& w^{3} \\
1 &&&& w^{4} \\
& 1 &&&& w^{5} \\
&& 1 &&&& w^{6} \\
&&& 1 &&&& w^{7} \\
\end{pmatrix}
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{2} & w^{6} \\
w^{0} & w^{8} & w^{4} & w^{12} \\
w^{0} & w^{12} & w^{6} & w^{18} \\
&&&& w^{0} & w^{0} & w^{0} & w^{0} \\
&&&& w^{0} & w^{4} & w^{2} & w^{6} \\
&&&& w^{0} & w^{8} & w^{4} & w^{12} \\
&&&& w^{0} & w^{12} & w^{6} & w^{18} \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
1 &&&& w^{0} \\
& 1 &&&& w^{1} \\
&& 1 &&&& w^{2} \\
&&& 1 &&&& w^{3} \\
1 &&&& w^{4} \\
& 1 &&&& w^{5} \\
&& 1 &&&& w^{6} \\
&&& 1 &&&& w^{7} \\
\end{pmatrix}
\begin{pmatrix}
F_4 & \\
& F_4 \\
\end{pmatrix}
\end{align}
로 회로대로, $N=4$ 의 고속 푸리에 변환을 재귀적으로 호출해 나비 연산을 실시하면, $N=8$ 의 고속 푸리에 변환을 할 수 있는 것을 알 수 있습니다.
양자 푸리에 변환♪
양자 푸리에 변환 은 양자 컴퓨터에서 이산 푸리에 변환을 수행합니다 (
양자 게이트의 회로로 쓰면 이런 느낌이 듭니다.
여기서 $ x, y $의 첨자를 2 진수로 표시하여 입력 양자 상태를
\newcommand{\ket}[1]{\left| #1 \right\rangle}
\begin{align}
& \sum_{i_0, i_1, i_2 \in \{0, 1\}} x_{i_0 i_1 i_2} \ket{i_0 \ i_1 \ i_2} \\
&= \ x_{000} \ket{000} + x_{001} \ket{001} + x_{010} \ket{010} + x_{011} \ket{011} + x_{100} \ket{100} + x_{101} \ket{101} + x_{110} \ket{110} + x_{111} \ket{111} \\
\end{align}
출력 양자 상태
\begin{align}
& \sum_{j_0, j_1, j_2 \in \{0, 1\}} y_{j_0 j_1 j_2} \ket{j_0 \ j_1 \ j_2} \\
&= \ y_{000} \ket{000} + y_{001} \ket{001} + y_{010} \ket{010} + y_{011} \ket{011} + y_{100} \ket{100} + y_{101} \ket{101} + y_{110} \ket{110} + y_{111} \ket{111} \\
\end{align}
하고 있습니다. 그리고 실은 이 회로, 고속 푸리에 변환과 동등한 행렬 분해를 이용하고 있습니다.
이번에는 출력을 비트 반전해 보면,
\begin{pmatrix}
y_{0} \\
y_{4} \\
y_{2} \\
y_{6} \\
y_{1} \\
y_{5} \\
y_{3} \\
y_{7} \\
\end{pmatrix} =
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{8} & w^{12} & w^{16} & w^{20} & w^{24} & w^{28} \\
w^{0} & w^{2} & w^{4} & w^{6} & w^{8} & w^{10} & w^{12} & w^{14} \\
w^{0} & w^{6} & w^{12} & w^{18} & w^{24} & w^{30} & w^{36} & w^{42} \\
w^{0} & w^{1} & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} \\
w^{0} & w^{5} & w^{10} & w^{15} & w^{20} & w^{25} & w^{30} & w^{35} \\
w^{0} & w^{3} & w^{6} & w^{9} & w^{12} & w^{15} & w^{18} & w^{21} \\
w^{0} & w^{7} & w^{14} & w^{21} & w^{28} & w^{35} & w^{42} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{pmatrix}
이 8x8 행렬을 $F'_8$ 로 놓고, 고속 푸리에 변환의 분해를 전치하면,
\begin{align}
F'_8= \ &
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{8} & w^{12} \\
w^{0} & w^{2} & w^{4} & w^{6} \\
w^{0} & w^{6} & w^{12} & w^{18} \\
&&&& w^{0} & w^{0} & w^{0} & w^{0} \\
&&&& w^{0} & w^{4} & w^{8} & w^{12} \\
&&&& w^{0} & w^{2} & w^{4} & w^{6} \\
&&&& w^{0} & w^{6} & w^{12} & w^{18} \\
\end{pmatrix}
\begin{pmatrix}
1 &&&& 1 \\
& 1 &&&& 1 \\
&& 1 &&&& 1 \\
&&& 1 &&&& 1 \\
w^{0} &&&& w^{4} \\
& w^{1} &&&& w^{5} \\
&& w^{2} &&&& w^{6} \\
&&& w^{3} &&&& w^{7} \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
F'_4 & \\
& F'_4 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& w^{0} \\
&&&&& w^{1} \\
&&&&&& w^{2} \\
&&&&&&& w^{3} \\
\end{pmatrix}
\begin{pmatrix}
1 &&&& 1 \\
& 1 &&&& 1 \\
&& 1 &&&& 1 \\
&&& 1 &&&& 1 \\
1 &&&& -1 \\
& 1 &&&& -1 \\
&& 1 &&&& -1 \\
&&& 1 &&&& -1 \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
F'_4 & \\
& F'_4 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& 1 \\
&&&&& 1 \\
&&&&&& w^{2} \\
&&&&&&& w^{2} \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& 1 \\
&&&&& w^{1} \\
&&&&&& 1 \\
&&&&&&& w^{1} \\
\end{pmatrix}
(H \otimes I \otimes I) \\
= \ &
(I \otimes F'_4) \ CR_{- \pi / 2} \ CR_{- \pi / 4} (H \otimes I \otimes I)
\end{align}
따라서 회로대로 3개의 양자 게이트를 통해 $N=4$ 의 양자 푸리에 변환을 재귀적으로 호출하면 $N=8$ 의 양자 푸리에 변환이 가능하다는 것을 알 수 있습니다.
고속 푸리에 변환 vs. 양자 푸리에 변환
그래서 이번에 소개한 회로에 대해 모아 보면,
고속 푸리에 변환
양자 푸리에 변환
재귀 호출
두 번
1회
지배적인 계산 단위
복소수의 곱셈
양자 게이트
계산량
$\mathcal{O}(N\log N)$
$\mathcal{O}((\log N)^2)$
가 되어, 양자 컴퓨터 쪽이 계산량 싼 것을 알 수 있군요.
고속 푸리에 변환에서는 2개로 분할해 각각 재귀하고 있던 계산을, 1회의 말미 재귀로 계산할 수 있어 버리는 것이 미소로, 이 근처 양자 컴퓨터가 병렬 처리에 강하다고 칭해지는 곳 이후라고 생각합니다.
물론, 이것만으로 양자 푸리에 변환이 고속 푸리에 변환보다 우수하다고는 할 수 없어, 계산 단위가 다르고, 양자 상태는 그대로 측정할 수 없고, 원래 보통으로 사용할 수 있는 실용적인 양자 컴퓨터는 아직 존재하지 않는다 하지만, 그래도 오더 레벨로 고속화할 수 있는 것에는 큰 가능성을 느낍니다.
그리고, 양자 푸리에 변환의 응용에의 유명한 쇼어의 소인수 분해 알고리즘이 있다고 하고, 소인수 분해가 고속화할 수 있으면 RSA 암호를 깨뜨릴지도 모르고… 공부를 진행합니다. 네.
Reference
이 문제에 관하여(양자 컴퓨터로 푸리에 변환하면 고속 푸리에 변환보다 빠른), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/piyo7/items/d6f95876c7ec0188f991
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
y_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} n k}
\begin{pmatrix}
y_{0} \\
y_{1} \\
y_{2} \\
y_{3} \\
y_{4} \\
y_{5} \\
y_{6} \\
y_{7} \\
\end{pmatrix} =
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{1} & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} \\
w^{0} & w^{2} & w^{4} & w^{6} & w^{8} & w^{10} & w^{12} & w^{14} \\
w^{0} & w^{3} & w^{6} & w^{9} & w^{12} & w^{15} & w^{18} & w^{21} \\
w^{0} & w^{4} & w^{8} & w^{12} & w^{16} & w^{20} & w^{24} & w^{28} \\
w^{0} & w^{5} & w^{10} & w^{15} & w^{20} & w^{25} & w^{30} & w^{35} \\
w^{0} & w^{6} & w^{12} & w^{18} & w^{24} & w^{30} & w^{36} & w^{42} \\
w^{0} & w^{7} & w^{14} & w^{21} & w^{28} & w^{35} & w^{42} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{pmatrix} \\
고속 푸리에 변환은 이산 푸리에 변환을 가속화합니다 (ぉ
분할통치법을 사용한 Cooley-Tukey형의 알고리즘이 유명하고, 왼쪽에서 오른쪽으로 수치를 흘리는 회로처럼 쓰면 이런 느낌이 듭니다. 사선이 교차하는 곳을 나비 연산이라고합니다.
입력열의 순서를 비트 반전을 하는 것이 미소로, 예를 들어 입력의 $x_3$ 의 첨자는 2진수라고 011이므로 반전시켜 110, 즉 0으로부터 세어 6번째에 둡니다.
이런 식으로 앞의 행렬 계산을 변형하면,
\begin{pmatrix}
y_{0} \\
y_{1} \\
y_{2} \\
y_{3} \\
y_{4} \\
y_{5} \\
y_{6} \\
y_{7} \\
\end{pmatrix} =
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{2} & w^{6} & w^{1} & w^{5} & w^{3} & w^{7} \\
w^{0} & w^{8} & w^{4} & w^{12} & w^{2} & w^{10} & w^{6} & w^{14} \\
w^{0} & w^{12} & w^{6} & w^{18} & w^{3} & w^{15} & w^{9} & w^{21} \\
w^{0} & w^{16} & w^{8} & w^{24} & w^{4} & w^{20} & w^{12} & w^{28} \\
w^{0} & w^{20} & w^{10} & w^{30} & w^{5} & w^{25} & w^{15} & w^{35} \\
w^{0} & w^{24} & w^{12} & w^{36} & w^{6} & w^{30} & w^{18} & w^{42} \\
w^{0} & w^{28} & w^{14} & w^{42} & w^{6} & w^{35} & w^{21} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{4} \\
x_{2} \\
x_{6} \\
x_{1} \\
x_{5} \\
x_{3} \\
x_{7} \\
\end{pmatrix}
이 8x8 행렬을 $F_8$ 로 두고 분해하면,
\begin{align}
F_8 = \ &
\begin{pmatrix}
1 &&&& w^{0} \\
& 1 &&&& w^{1} \\
&& 1 &&&& w^{2} \\
&&& 1 &&&& w^{3} \\
1 &&&& w^{4} \\
& 1 &&&& w^{5} \\
&& 1 &&&& w^{6} \\
&&& 1 &&&& w^{7} \\
\end{pmatrix}
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{2} & w^{6} \\
w^{0} & w^{8} & w^{4} & w^{12} \\
w^{0} & w^{12} & w^{6} & w^{18} \\
&&&& w^{0} & w^{0} & w^{0} & w^{0} \\
&&&& w^{0} & w^{4} & w^{2} & w^{6} \\
&&&& w^{0} & w^{8} & w^{4} & w^{12} \\
&&&& w^{0} & w^{12} & w^{6} & w^{18} \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
1 &&&& w^{0} \\
& 1 &&&& w^{1} \\
&& 1 &&&& w^{2} \\
&&& 1 &&&& w^{3} \\
1 &&&& w^{4} \\
& 1 &&&& w^{5} \\
&& 1 &&&& w^{6} \\
&&& 1 &&&& w^{7} \\
\end{pmatrix}
\begin{pmatrix}
F_4 & \\
& F_4 \\
\end{pmatrix}
\end{align}
로 회로대로, $N=4$ 의 고속 푸리에 변환을 재귀적으로 호출해 나비 연산을 실시하면, $N=8$ 의 고속 푸리에 변환을 할 수 있는 것을 알 수 있습니다.
양자 푸리에 변환♪
양자 푸리에 변환 은 양자 컴퓨터에서 이산 푸리에 변환을 수행합니다 (
양자 게이트의 회로로 쓰면 이런 느낌이 듭니다.
여기서 $ x, y $의 첨자를 2 진수로 표시하여 입력 양자 상태를
\newcommand{\ket}[1]{\left| #1 \right\rangle}
\begin{align}
& \sum_{i_0, i_1, i_2 \in \{0, 1\}} x_{i_0 i_1 i_2} \ket{i_0 \ i_1 \ i_2} \\
&= \ x_{000} \ket{000} + x_{001} \ket{001} + x_{010} \ket{010} + x_{011} \ket{011} + x_{100} \ket{100} + x_{101} \ket{101} + x_{110} \ket{110} + x_{111} \ket{111} \\
\end{align}
출력 양자 상태
\begin{align}
& \sum_{j_0, j_1, j_2 \in \{0, 1\}} y_{j_0 j_1 j_2} \ket{j_0 \ j_1 \ j_2} \\
&= \ y_{000} \ket{000} + y_{001} \ket{001} + y_{010} \ket{010} + y_{011} \ket{011} + y_{100} \ket{100} + y_{101} \ket{101} + y_{110} \ket{110} + y_{111} \ket{111} \\
\end{align}
하고 있습니다. 그리고 실은 이 회로, 고속 푸리에 변환과 동등한 행렬 분해를 이용하고 있습니다.
이번에는 출력을 비트 반전해 보면,
\begin{pmatrix}
y_{0} \\
y_{4} \\
y_{2} \\
y_{6} \\
y_{1} \\
y_{5} \\
y_{3} \\
y_{7} \\
\end{pmatrix} =
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{8} & w^{12} & w^{16} & w^{20} & w^{24} & w^{28} \\
w^{0} & w^{2} & w^{4} & w^{6} & w^{8} & w^{10} & w^{12} & w^{14} \\
w^{0} & w^{6} & w^{12} & w^{18} & w^{24} & w^{30} & w^{36} & w^{42} \\
w^{0} & w^{1} & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} \\
w^{0} & w^{5} & w^{10} & w^{15} & w^{20} & w^{25} & w^{30} & w^{35} \\
w^{0} & w^{3} & w^{6} & w^{9} & w^{12} & w^{15} & w^{18} & w^{21} \\
w^{0} & w^{7} & w^{14} & w^{21} & w^{28} & w^{35} & w^{42} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{pmatrix}
이 8x8 행렬을 $F'_8$ 로 놓고, 고속 푸리에 변환의 분해를 전치하면,
\begin{align}
F'_8= \ &
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{8} & w^{12} \\
w^{0} & w^{2} & w^{4} & w^{6} \\
w^{0} & w^{6} & w^{12} & w^{18} \\
&&&& w^{0} & w^{0} & w^{0} & w^{0} \\
&&&& w^{0} & w^{4} & w^{8} & w^{12} \\
&&&& w^{0} & w^{2} & w^{4} & w^{6} \\
&&&& w^{0} & w^{6} & w^{12} & w^{18} \\
\end{pmatrix}
\begin{pmatrix}
1 &&&& 1 \\
& 1 &&&& 1 \\
&& 1 &&&& 1 \\
&&& 1 &&&& 1 \\
w^{0} &&&& w^{4} \\
& w^{1} &&&& w^{5} \\
&& w^{2} &&&& w^{6} \\
&&& w^{3} &&&& w^{7} \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
F'_4 & \\
& F'_4 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& w^{0} \\
&&&&& w^{1} \\
&&&&&& w^{2} \\
&&&&&&& w^{3} \\
\end{pmatrix}
\begin{pmatrix}
1 &&&& 1 \\
& 1 &&&& 1 \\
&& 1 &&&& 1 \\
&&& 1 &&&& 1 \\
1 &&&& -1 \\
& 1 &&&& -1 \\
&& 1 &&&& -1 \\
&&& 1 &&&& -1 \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
F'_4 & \\
& F'_4 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& 1 \\
&&&&& 1 \\
&&&&&& w^{2} \\
&&&&&&& w^{2} \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& 1 \\
&&&&& w^{1} \\
&&&&&& 1 \\
&&&&&&& w^{1} \\
\end{pmatrix}
(H \otimes I \otimes I) \\
= \ &
(I \otimes F'_4) \ CR_{- \pi / 2} \ CR_{- \pi / 4} (H \otimes I \otimes I)
\end{align}
따라서 회로대로 3개의 양자 게이트를 통해 $N=4$ 의 양자 푸리에 변환을 재귀적으로 호출하면 $N=8$ 의 양자 푸리에 변환이 가능하다는 것을 알 수 있습니다.
고속 푸리에 변환 vs. 양자 푸리에 변환
그래서 이번에 소개한 회로에 대해 모아 보면,
고속 푸리에 변환
양자 푸리에 변환
재귀 호출
두 번
1회
지배적인 계산 단위
복소수의 곱셈
양자 게이트
계산량
$\mathcal{O}(N\log N)$
$\mathcal{O}((\log N)^2)$
가 되어, 양자 컴퓨터 쪽이 계산량 싼 것을 알 수 있군요.
고속 푸리에 변환에서는 2개로 분할해 각각 재귀하고 있던 계산을, 1회의 말미 재귀로 계산할 수 있어 버리는 것이 미소로, 이 근처 양자 컴퓨터가 병렬 처리에 강하다고 칭해지는 곳 이후라고 생각합니다.
물론, 이것만으로 양자 푸리에 변환이 고속 푸리에 변환보다 우수하다고는 할 수 없어, 계산 단위가 다르고, 양자 상태는 그대로 측정할 수 없고, 원래 보통으로 사용할 수 있는 실용적인 양자 컴퓨터는 아직 존재하지 않는다 하지만, 그래도 오더 레벨로 고속화할 수 있는 것에는 큰 가능성을 느낍니다.
그리고, 양자 푸리에 변환의 응용에의 유명한 쇼어의 소인수 분해 알고리즘이 있다고 하고, 소인수 분해가 고속화할 수 있으면 RSA 암호를 깨뜨릴지도 모르고… 공부를 진행합니다. 네.
Reference
이 문제에 관하여(양자 컴퓨터로 푸리에 변환하면 고속 푸리에 변환보다 빠른), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/piyo7/items/d6f95876c7ec0188f991
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
\newcommand{\ket}[1]{\left| #1 \right\rangle}
\begin{align}
& \sum_{i_0, i_1, i_2 \in \{0, 1\}} x_{i_0 i_1 i_2} \ket{i_0 \ i_1 \ i_2} \\
&= \ x_{000} \ket{000} + x_{001} \ket{001} + x_{010} \ket{010} + x_{011} \ket{011} + x_{100} \ket{100} + x_{101} \ket{101} + x_{110} \ket{110} + x_{111} \ket{111} \\
\end{align}
\begin{align}
& \sum_{j_0, j_1, j_2 \in \{0, 1\}} y_{j_0 j_1 j_2} \ket{j_0 \ j_1 \ j_2} \\
&= \ y_{000} \ket{000} + y_{001} \ket{001} + y_{010} \ket{010} + y_{011} \ket{011} + y_{100} \ket{100} + y_{101} \ket{101} + y_{110} \ket{110} + y_{111} \ket{111} \\
\end{align}
\begin{pmatrix}
y_{0} \\
y_{4} \\
y_{2} \\
y_{6} \\
y_{1} \\
y_{5} \\
y_{3} \\
y_{7} \\
\end{pmatrix} =
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{8} & w^{12} & w^{16} & w^{20} & w^{24} & w^{28} \\
w^{0} & w^{2} & w^{4} & w^{6} & w^{8} & w^{10} & w^{12} & w^{14} \\
w^{0} & w^{6} & w^{12} & w^{18} & w^{24} & w^{30} & w^{36} & w^{42} \\
w^{0} & w^{1} & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} \\
w^{0} & w^{5} & w^{10} & w^{15} & w^{20} & w^{25} & w^{30} & w^{35} \\
w^{0} & w^{3} & w^{6} & w^{9} & w^{12} & w^{15} & w^{18} & w^{21} \\
w^{0} & w^{7} & w^{14} & w^{21} & w^{28} & w^{35} & w^{42} & w^{49} \\
\end{pmatrix}
\begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{pmatrix}
\begin{align}
F'_8= \ &
\begin{pmatrix}
w^{0} & w^{0} & w^{0} & w^{0} \\
w^{0} & w^{4} & w^{8} & w^{12} \\
w^{0} & w^{2} & w^{4} & w^{6} \\
w^{0} & w^{6} & w^{12} & w^{18} \\
&&&& w^{0} & w^{0} & w^{0} & w^{0} \\
&&&& w^{0} & w^{4} & w^{8} & w^{12} \\
&&&& w^{0} & w^{2} & w^{4} & w^{6} \\
&&&& w^{0} & w^{6} & w^{12} & w^{18} \\
\end{pmatrix}
\begin{pmatrix}
1 &&&& 1 \\
& 1 &&&& 1 \\
&& 1 &&&& 1 \\
&&& 1 &&&& 1 \\
w^{0} &&&& w^{4} \\
& w^{1} &&&& w^{5} \\
&& w^{2} &&&& w^{6} \\
&&& w^{3} &&&& w^{7} \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
F'_4 & \\
& F'_4 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& w^{0} \\
&&&&& w^{1} \\
&&&&&& w^{2} \\
&&&&&&& w^{3} \\
\end{pmatrix}
\begin{pmatrix}
1 &&&& 1 \\
& 1 &&&& 1 \\
&& 1 &&&& 1 \\
&&& 1 &&&& 1 \\
1 &&&& -1 \\
& 1 &&&& -1 \\
&& 1 &&&& -1 \\
&&& 1 &&&& -1 \\
\end{pmatrix} \\
= \ &
\begin{pmatrix}
F'_4 & \\
& F'_4 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& 1 \\
&&&&& 1 \\
&&&&&& w^{2} \\
&&&&&&& w^{2} \\
\end{pmatrix}
\begin{pmatrix}
1 \\
& 1 \\
&& 1 \\
&&& 1 \\
&&&& 1 \\
&&&&& w^{1} \\
&&&&&& 1 \\
&&&&&&& w^{1} \\
\end{pmatrix}
(H \otimes I \otimes I) \\
= \ &
(I \otimes F'_4) \ CR_{- \pi / 2} \ CR_{- \pi / 4} (H \otimes I \otimes I)
\end{align}
그래서 이번에 소개한 회로에 대해 모아 보면,
고속 푸리에 변환
양자 푸리에 변환
재귀 호출
두 번
1회
지배적인 계산 단위
복소수의 곱셈
양자 게이트
계산량
$\mathcal{O}(N\log N)$
$\mathcal{O}((\log N)^2)$
가 되어, 양자 컴퓨터 쪽이 계산량 싼 것을 알 수 있군요.
고속 푸리에 변환에서는 2개로 분할해 각각 재귀하고 있던 계산을, 1회의 말미 재귀로 계산할 수 있어 버리는 것이 미소로, 이 근처 양자 컴퓨터가 병렬 처리에 강하다고 칭해지는 곳 이후라고 생각합니다.
물론, 이것만으로 양자 푸리에 변환이 고속 푸리에 변환보다 우수하다고는 할 수 없어, 계산 단위가 다르고, 양자 상태는 그대로 측정할 수 없고, 원래 보통으로 사용할 수 있는 실용적인 양자 컴퓨터는 아직 존재하지 않는다 하지만, 그래도 오더 레벨로 고속화할 수 있는 것에는 큰 가능성을 느낍니다.
그리고, 양자 푸리에 변환의 응용에의 유명한 쇼어의 소인수 분해 알고리즘이 있다고 하고, 소인수 분해가 고속화할 수 있으면 RSA 암호를 깨뜨릴지도 모르고… 공부를 진행합니다. 네.
Reference
이 문제에 관하여(양자 컴퓨터로 푸리에 변환하면 고속 푸리에 변환보다 빠른), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/piyo7/items/d6f95876c7ec0188f991텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
