장 25 쇼어 알고리즘

자, 이제 쇼어 알고리즘을 살펴봅시다. $M=pq$ 를 $O\left((\log M)^{2}\right)$ 시간에 인수분해하는 방법입니다.

미국 국가안보국(NSA) 같은 기관들이 양자 컴퓨팅에 수백만 달러를 쏟아부어 온 것은 아마도 바로 이것 때문일 것입니다.

25.1 고전적 (역) 푸리에 변환

쇼어 알고리즘의 “결정적인 한 수”는 이른바 양자 푸리에 변환입니다. 푸리에 변환은 데이터에서 주기성을 추출하는 데 쓰이며, 양자 버전이 고전적인 버전보다 훨씬 빠르다는 사실이 밝혀졌습니다.

먼저 정의부터 제시하겠습니다. $N$ 을 양의 정수라 하고, $\omega_{N}=\exp\left(\frac{2\pi i}{N}\right)$ 라 합시다.

정의 25.1.1.

복소수 튜플

\left(x_{0},x_{1},\dots,x_{N-1}\right)

이 주어지면, 그 이산 역 푸리에 변환은 다음과 같이 정의되는 수열 $(y_{0},y_{1},\dots,y_{N-1})$ 입니다.

y_{k}=\frac{1}{N}\sum_{j=0}^{N-1}\omega_{N}^{jk}x_{j}.

이는 다음 행렬을 적용하는 것과 동치입니다.

\frac{1}{N}\begin{bmatrix}1&1&1&\dots&1\\ 1&\omega_{N}&\omega_{N}^{2}&\dots&\omega_{N}^{N-1}\\ 1&\omega_{N}^{2}&\omega_{N}^{4}&\dots&\omega_{N}^{2(N-1)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega_{N}^{N-1}&\omega_{N}^{2(N-1)}&\dots&\omega_{N}^{(N-1)^{2}}\end{% bmatrix}\begin{bmatrix}x_{0}\\ x_{1}\\ \vdots\\ x_{N-1}\end{bmatrix}=\begin{bmatrix}y_{0}\\ y_{1}\\ \vdots\\ y_{N-1}\end{bmatrix}.

이 연산이 중요한 이유는 $x_{i}$ 가 주기적인지 알아낼 수 있게 해 주기 때문입니다. 더 일반적으로, $1$ 이 주기 $r$ 로 나타나는 수열이 주어지면 진폭은 $\frac{N}{\gcd(N,r)}$ 로 나누어떨어지는 입력에서 최대가 됩니다. 수학적으로는 다음이 성립합니다.

x_{k}=\sum_{j=0}^{N-1}y_{j}\omega_{N}^{-jk}.

예제 25.1.2 (이산 역 푸리에 변환의 예).

$N=6$ , $\omega=\omega_{6}=\exp(\frac{2\pi i}{6})$ 라 하고 $(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5})=(0,1,0,1,0,1)$ 이라 가정합시다(따라서 $x_{i}$ 는 $2$ 를 법으로 주기적입니다). 그러면 다음과 같습니다.

	$\displaystyle y_{0}$	$\displaystyle=\tfrac{1}{6}\left(\omega^{0}+\omega^{0}+\omega^{0}\right)=1/2$
	$\displaystyle y_{1}$	$\displaystyle=\tfrac{1}{6}\left(\omega^{1}+\omega^{3}+\omega^{5}\right)=0$
	$\displaystyle y_{2}$	$\displaystyle=\tfrac{1}{6}\left(\omega^{2}+\omega^{6}+\omega^{10}\right)=0$
	$\displaystyle y_{3}$	$\displaystyle=\tfrac{1}{6}\left(\omega^{3}+\omega^{9}+\omega^{15}\right)=-1/2$
	$\displaystyle y_{4}$	$\displaystyle=\tfrac{1}{6}\left(\omega^{4}+\omega^{12}+\omega^{20}\right)=0$
	$\displaystyle y_{5}$	$\displaystyle=\tfrac{1}{6}\left(\omega^{5}+\omega^{15}+\omega^{25}\right)=0.$

따라서 역변환에서 “진폭”은 모두 $3$ 의 배수에 집중되며, 이로써 원래 수열의 주기가 $\frac{N}{3}=2$ 임이 드러납니다.

비고 25.1.3.

이 연산이 “역” 푸리에 변환이라고 불리는 것은 (제가 이해하기로는) 대체로 역사적 우연입니다. 혼란스럽게도, 이에 대응하는 양자 연산은 (역이 아닌) 푸리에 변환입니다.

정의를 그대로 적용하면 변환을 계산하는 데 $O(N^{2})$ 시간이 걸립니다. 고속 푸리에 변환이라는 고전적 알고리즘(자세한 내용은 다루지 않겠지만, 사실상 계산을 “재사용”합니다)을 사용하면 이를 $O(N\log N)$ 시간으로 줄일 수 있다는 사실이 알려져 있습니다. 그러나 쇼어 알고리즘에는 이것으로도 부족하며, 대신 $O\left((\log N)^{2}\right)$ 정도가 필요합니다. 바로 여기서 양자 푸리에 변환이 등장합니다.

25.2 양자 푸리에 변환

푸리에 변환을 계산하려면 $N\times N$ 행렬에 $N$ -벡터를 곱해야 하므로 $O(N^{2})$ 번의 곱셈이 필요하다는 점에 유의하십시오. 그러나 이제 보이겠지만, 양자 컴퓨터를 사용하면 $N=2^{n}$ 일 때 $n$ 개의 큐비트로 이루어진 시스템에서 $O((\log N)^{2})$ 개의 양자 게이트로 이를 수행할 수 있습니다.

먼저 표기법을 몇 가지 더 도입하겠습니다.

표기의 남용 25.2.1.

이하에서 $\ket{x}$ 는 $\ket{x_{n}}\otimes\ket{x_{n-1}}\otimes\dots\otimes\ket{x_{1}}$ 을 가리키며, 여기서 $x=x_{n}x_{n-1}\dots x_{1}$ 은 이진법 표기입니다. 예를 들어 $n=3$ 이면 $\ket{6}$ 은 실제로 $\ket{1}\otimes\ket{1}\otimes\ket{0}$ 을 의미합니다. 마찬가지로 $0.x_{1}x_{2}\dots x_{n}$ 도 이진법 표기로 봅니다.

이제 $n$ -큐비트 공간이 정규직교 기저 $\ket{0}$ , $\ket{1}$ , …, $\ket{N-1}$ 을 가진다는 것을 관찰하십시오.

정의 25.2.2.

다음과 같은 $n$ -큐비트 상태를 생각합시다.

\ket{\psi}=\sum_{k=0}^{N-1}x_{k}\ket{k}.

양자 푸리에 변환은 다음과 같이 정의됩니다.

U_{\mathrm{QFT}}(\ket{\psi})=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left(\sum_{k=0% }^{N-1}\omega_{N}^{jk}x_{k}\right)\ket{j}.

다시 말해, 기저 $\ket{0}$ , …, $\ket{N-1}$ 을 사용하면 $U_{\mathrm{QFT}}$ 는 다음 행렬로 주어집니다.

U_{\mathrm{QFT}}=\frac{1}{\sqrt{N}}\begin{bmatrix}1&1&1&\dots&1\\ 1&\omega_{N}&\omega_{N}^{2}&\dots&\omega_{N}^{N-1}\\ 1&\omega_{N}^{2}&\omega_{N}^{4}&\dots&\omega_{N}^{2(N-1)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega_{N}^{N-1}&\omega_{N}^{2(N-1)}&\dots&\omega_{N}^{(N-1)^{2}}\end{bmatrix}

이는 $U_{\mathrm{QFT}}$ 가 유니터리가 되도록 $\sqrt{N}$ 인자를 추가했다는 점을 제외하면 앞의 정의와 정확히 같습니다. 그러나 요령은 양자 설정에서는 이 행렬을 다음과 같이 다시 쓸 수 있다는 점입니다.

명제 25.2.3 (텐서 표현).

$\ket{x}=\ket{x_{n}x_{n-1}\dots x_{1}}$ 이라 합시다. 그러면 다음이 성립합니다.

	$\displaystyle U_{\mathrm{QFT}}(\ket{x_{n}x_{n-1}\dots x_{1}})=\frac{1}{\sqrt{N}}$	$\displaystyle\left(\ket{0}+\exp(2\pi i\cdot 0.x_{1})\ket{1}\right)$
		$\displaystyle\otimes\left(\ket{0}+\exp(2\pi i\cdot 0.x_{2}x_{1})\ket{1}\right)$
		$\displaystyle\otimes\dots$
		$\displaystyle\otimes\left(\ket{0}+\exp(2\pi i\cdot 0.x_{n}\dots x_{1})\ket{1}\right)$

증명.

직접 계산하면 되지만, 꽤 번거롭습니다. 요컨대 모든 것을 전개하십시오. ∎

따라서 혼합 상태를 사용함으로써, 양자 푸리에 변환은 고전적으로는 불가능한 이 “텐서곱에 의한 곱셈” 기법을 사용할 수 있습니다.

이제 더 지체하지 않고 회로를 보이겠습니다. 회전 행렬을 다음과 같이 정의합니다.

R_{k}=\begin{bmatrix}1&0\\ 0&\exp(2\pi i/2^{k})\end{bmatrix}.

그러면 $n=3$ 일 때 회로는 제어 $R_{k}$ 들을 사용하여 다음과 같이 주어집니다.

연습문제 25.2.4.

이 회로에서 $\ket{x_{3}x_{2}x_{1}}$ 의 상이 다음과 같음을 보이십시오.

\Big{(}\ket{0}+\exp(2\pi i\cdot 0.x_{1})\ket{1}\Big{)}\otimes\Big{(}\ket{0}+% \exp(2\pi i\cdot 0.x_{2}x_{1})\ket{1}\Big{)}\otimes\Big{(}\ket{0}+\exp(2\pi i% \cdot 0.x_{3}x_{2}x_{1})\ket{1}\Big{)}

주장한 바와 같습니다.

일반적인 $n$ 에 대해서는 이를 귀납적으로 다음과 같이 쓸 수 있습니다.

질문 25.2.5.

$n=3$ 일 때 제시된 두 회로가 동치임을 스스로 확인하십시오.

따라서 양자 푸리에 변환은 $O(n^{2})$ 개의 게이트로 구현할 수 있으며, 이는 고전적인 고속 푸리에 변환이 필요로 하는 $O(N\log N)$ 번의 연산(여기서 $N=2^{n}$ )보다 월등히 좋습니다.

25.3 쇼어 알고리즘

양자 푸리에 변환은 쇼어 알고리즘의 핵심 요소입니다. 이제 이것을 갖추었으므로 소인수분해 문제를 풀 수 있습니다.

$p,q>3$ 을 홀수 소수라 하고 $p\neq q$ 라고 가정합니다. 핵심 아이디어는 정수 $M=pq$ 를 소인수분해하는 문제를 $x\pmod{M}$ 의 위수를 구하는 문제로 바꾸는 것입니다. 후자는 양자 푸리에 변환으로 풀 수 있는 “주기성” 문제입니다. 구체적으로, $x\pmod{M}$ 이 다음 조건을 만족하면 좋다고 합니다.

(i)

$\gcd(x,M)=1$ ,
(ii)

$x\pmod{M}$ 의 위수 $r$ 이 짝수이고,
(iii)

$0\equiv(x^{r/2}-1)(x^{r/2}+1)\pmod{M}$ 으로 인수분해하였을 때, 두 인수 모두 $0\pmod{M}$ 이 아닙니다. 따라서 둘 중 하나는 $p$ 로 나누어떨어지고, 다른 하나는 $q$ 로 나누어떨어집니다.

연습문제 25.3.1 (경시대회 정수론 연습용).

$M=pq$ 일 때 $(\mathbb{Z}/M\mathbb{Z})^{\times}$ 의 잉여류 중 적어도 절반이 좋다는 것을 보이십시오.

따라서 임의의 $x\in(\mathbb{Z}/M\mathbb{Z})^{\times}$ 의 위수를 구할 수 있다면, 좋은 $x$ 를 고를 때까지 계속 $x$ 를 고르기만 하면 됩니다(이는 절반 이상의 확률로 일어납니다). 그렇게 되면 유클리드 알고리즘을 사용하여 $\gcd(x^{r/2}-1,M)$ 를 계산해 $M$ 의 소인수 중 하나를 추출하고, 이로써 문제가 해결됩니다.

그렇다면 이것을 어떻게 할까요? 아이디어는 그리 어렵지 않습니다. 먼저 법 $r$ 에 대해 주기적인 수열을 생성합니다.

예제 25.3.2 ( $77$ 의 소인수분해: 주기적 상태 생성하기).

$M=77$ 을 소인수분해하려 하는데, 무작위로 $x=2$ 를 골랐고 그 위수 $r$ 을 구하고자 한다고 합시다. $n=13$ , $N=2^{13}$ 이라 두고, 먼저 상태를 다음과 같이 초기화합니다.

\ket{\psi}=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\ket{k}.

이제 $\ket{k}\ket{0}$ 을 $\ket{k}\ket{x^{k}\bmod M}$ 으로 보내는 ( $x$ 에 의존하는) 회로 $U_{x}$ 를 만듭니다. 이를 $\ket{\psi}\otimes\ket{0}$ 에 적용하면 다음을 얻습니다.

U(\ket{\psi}\ket{0})=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\ket{k}\otimes\ket{x^{k% }\bmod M}.

이제 두 번째 큐비트를 측정하여 $\ket{51}$ 상태를 얻었다고 가정합니다( $2^{7}\equiv 51\pmod{77}$ 임에 유의하십시오). 그러면 붕괴된 상태는 이제 상수배를 무시하면 다음과 같습니다.

(\ket{7}+\ket{7+r}+\ket{7+2r}+\dots)\otimes\ket{51}.

실제 병목은 회로 $U_{x}$ 입니다. 반복 제곱법을 사용하여 $x^{k}\pmod{M}$ 를 계산할 수 있지만, 여전히 이것이 전체 연산에서 번거로운 부분입니다.

일반적으로 이 연산은 다음과 같습니다.

•

충분히 큰 $N=2^{n}$ 을 고릅니다(예를 들어 $N\geq M^{2}$ ).
•

$\ket{\psi}=\sum_{k=0}^{2^{n}-1}\ket{k}$ 를 생성합니다.
•

$\ket{x^{k}\mod M}$ 을 계산하는 회로 $U_{x}$ 를 구성합니다.
•

이를 적용하여 상태 $\frac{1}{\sqrt{N}}\sum_{k=0}^{2^{n}-1}\ket{k}\otimes\ket{x^{k}\mod M}$ 을 얻습니다.
•

두 번째 큐비트를 측정하여 첫 번째 큐비트가 $r$ 을 법으로 주기적인 상태로 붕괴하도록 합니다. 왼쪽 큐비트를 $\ket{\phi}$ 로 나타냅시다.

이제 왼쪽 큐비트 $\ket{\phi}$ 에 양자 푸리에 변환을 적용한다고 가정합시다. 왼쪽 비트는 $r$ 을 법으로 주기적이므로, 이 변환이 $r$ 의 값을 알려 주리라 기대할 수 있습니다. 안타깝게도 이 방법은 그대로는 잘 되지 않습니다. $N$ 은 2의 거듭제곱이지만 $r$ 은 그렇지 않을 것으로 예상되기 때문입니다.

그럼에도 불구하고, 다음 상태를 생각해 봅시다

\ket{\phi}=\ket{k_{0}}+\ket{k_{0}+r}+\dots

예를 들어 앞에서 $x=2$ 일 때 $51$ 을 측정했다면 $k_{0}=7$ 이었습니다. 양자 푸리에 변환을 적용하면, 변환된 상에서 $\ket{j}$ 의 계수가 다음과 같음을 알 수 있습니다

\omega_{N}^{k_{0}j}\cdot\left(\omega_{N}^{0}+\omega_{N}^{jr}+\omega_{N}^{2jr}+% \omega_{N}^{3jr}+\dots\right)

이것은 단위근의 합이므로, $\omega_{N}^{jr}=1$ 이 아닌 한 상쇄 간섭이 일어난다는 것을 알 수 있습니다( $N$ 이 크기 때문입니다). 다시 말해, 근사적으로 다음이 성립합니다.

U_{\mathrm{QFT}}(\ket{\phi})\approx\sum_{\begin{subarray}{c}0\leq j<N\\ jr/N\in\mathbb{Z}\end{subarray}}\ket{j}

여기서 늘 그렇듯 스케일링 차이는 무시합니다. 요점은 다음과 같습니다

$U_{\mathrm{QFT}}\ket{\phi}$ 를 측정하면 $\frac{jr}{N}$ 이 어떤 $s\in\mathbb{Z}$ 에 가까운 $\ket{j}$ 를 얻습니다.

따라서 운이 충분히 따른다면 연분수를 사용하여 $r$ 의 값을 추출할 수 있습니다.

예제 25.3.3 ( $M=77$ 의 인수분해 마무리).

앞에서와 같이 두 번째 큐비트를 관측했으므로, 첫 번째 큐비트는 상태 $\ket{\phi}=\ket{7}+\ket{7+r}+\dots$ 로 붕괴합니다. 이제 측정을 하여 $j=4642$ 를 얻었는데, 이는 어떤 정수 $s$ 에 대해 다음이 성립함을 뜻합니다

\frac{4642r}{2^{13}}\approx s.

이제 $\frac{4642}{2^{13}}$ 의 연분수를 분석합니다. 처음 몇 개의 수렴은 다음과 같습니다.

0,\;1,\;\frac{1}{2},\;\frac{4}{7},\;\frac{13}{23},\;\frac{17}{30},\;\frac{1152% }{2033},\;\dots

따라서 $\frac{17}{30}$ 이 좋은 근사이므로, $s=17$ 과 $r=30$ 을 후보로 추론합니다. 실제로 $r=30$ 이 구하려던 위수임을 확인할 수 있습니다.

이 방법이 항상 통하지는 않습니다¹¹1잡음이라는 일반적인 문제는 말할 것도 없지만, 그것은 공학자들이 걱정할 일입니다. (예를 들어 운이 나쁘면 $j=0$ , 즉 $s=0$ 을 측정할 수도 있는데, 이는 아무런 정보도 주지 않습니다).

그러나

\gcd(s,r)=1.

일 때마다 성공한다는 것을 보일 수 있습니다. 이는 적어도 $\frac{1}{\log r}$ 의 비율로 일어나며, $r<M$ 이므로 충분히 많이 시행하면 결국 올바른 위수 $r$ 을 추출하게 됩니다. 이것이 쇼어 알고리즘입니다.