장 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}$ 가 주기적인지 검출할 수 있게 해 주기 때문입니다. 더 일반적으로, 주기 $r$ 로 나타나는 $1$ 들의 수열이 주어지면, 진폭은 $\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}$ 는 이진법으로 $x=x_{n}x_{n-1}\dots x_{1}$ 일 때 $\ket{x_{n}}\otimes\ket{x_{n-1}}\otimes\dots\otimes\ket{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$ 를 뽑을 때까지 계속 뽑기만 하면 됩니다(이는 절반 이상의 확률로 일어납니다). 일단 그렇게 되면, 유클리드 호제법을 사용하여 $\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}.

이제 ( $x$ 에 의존하는) 회로 $U_{x}$ 를 만들어 $\ket{k}\ket{0}$ 을 $\ket{k}\ket{x^{k}\bmod M}$ 으로 보내도록 합니다. 이를 $\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$ 을 추출하게 됨을 의미합니다. 이것이 쇼어 알고리즘입니다.