Shor 알고리즘은 소인수분해를 order finding으로 바꾸고, order finding을 양자 위상추정과 QFT(양자 푸리에 변환)로 풉니다. 중요한 점은 이 알고리즘이 인수를 한 번에 찍어내는 절차가 아니라, 소인수분해 후보를 만들고 고전적으로 검증하는 과정을 성공할 때까지 반복한다는 것입니다.
## 먼저 기억할 것: 후보를 반복해서 찾는 알고리즘 {#candidate-loop}
Shor 알고리즘을 처음 볼 때 가장 흔한 오해는 “양자컴퓨터가 바로 $p,q$를 출력한다”고 생각하는 것입니다. 실제 구조는 다릅니다. 고전적으로 임의의 $a$를 고르고, 그 $a$가 좋은 후보를 만들 수 있는지 검사하고, 실패하면 다른 $a$로 다시 시도합니다.
1. 고전적으로 $1<a<N$을 고릅니다.
2. 유클리드 호제법으로 $\gcd(a,N)$을 계산합니다.
3. 만약 $\gcd(a,N)>1$이면 이미 비자명한 인수를 찾은 것입니다.
4. $\gcd(a,N)=1$이면 양자 부분으로 $a$의 order $r$ 후보를 찾습니다.
5. $r$이 인수 후보를 만들 조건을 만족하는지 고전적으로 검증합니다.
6. 검증이 실패하면 다른 $a$를 골라 반복합니다.
즉 Shor의 양자 부분은 전체 소인수분해 절차 안의 강력한 subroutine입니다. 이 subroutine은 좋은 $a$가 주어졌을 때 order 후보를 빠르게 찾아줍니다. 하지만 최종 인수 확정은 gcd 계산과 후보 검증이라는 고전 후처리에서 이뤄집니다.
## 유클리드 호제법과 확장 유클리드 호제법 {#euclidean}
유클리드 호제법은 두 정수의 최대공약수를 빠르게 구합니다.
$$
\gcd(a,N)
$$
Shor의 첫 단계에서 $\gcd(a,N)$을 계산하는 이유는 간단합니다. 만약 무작위로 고른 $a$가 우연히 $N$과 공약수를 공유하면, 양자컴퓨터를 쓰기도 전에 인수 하나를 얻습니다.
확장 유클리드 호제법은 최대공약수뿐 아니라 아래 정수 $x,y$도 함께 찾습니다.
$$
ax+Ny=\gcd(a,N)
$$
$\gcd(a,N)=1$이면 아래가 됩니다.
$$
ax+Ny=1
$$
양변을 mod $N$으로 보면 $ax\equiv1\pmod N$이므로, $x$는 $a$의 modular inverse입니다. 이 사실은 Shor에서 중요합니다. $\gcd(a,N)=1$일 때 $x\mapsto ax\bmod N$가 permutation이 되고, 그래서 양자 회로에서 유니터리로 만들 수 있기 때문입니다.
정리하면, 유클리드 호제법은 후보 $a$가 바로 인수를 주는지 확인하고, 확장 유클리드 호제법은 서로소일 때 modular inverse와 permutation 구조를 보장하는 정수론적 배경을 줍니다.
## 소인수분해에서 order finding으로 {#reduction}
합성수 $N$과 서로소인 $a$를 고릅니다. 여기서 “서로소”라는 조건은 단순한 장식이 아닙니다. 서로소가 아니면 gcd에서 이미 인수를 얻고, 서로소라면 modular multiplication이 뒤에서 양자 유니터리가 됩니다. order $r$은 아래를 만족하는 가장 작은 양의 정수입니다.
$$
a^r \equiv 1 \pmod N
$$
$r$이 짝수이고 $a^{r/2}\not\equiv -1\pmod N$이면 인수를 얻을 수 있습니다.
$$
\gcd(a^{r/2}-1,N),\qquad
\gcd(a^{r/2}+1,N)
$$
여기서도 핵심은 “후보”입니다. 양자 부분이 준 $r$이 쓸모 있는지, gcd 결과가 $1$이나 $N$ 같은 자명한 값이 아닌지는 반드시 고전적으로 다시 검사합니다.
## 양자 부분: modular multiplication {#unitary}
함수 $x\mapsto ax\bmod N$는 서로소 조건에서 permutation이므로 유니터리로 만들 수 있습니다.
$$
U_a|x\rangle=|ax\bmod N\rangle
$$
이 유니터리의 고유값은 order $r$과 관련된 위상입니다.
$$
U_a|u_s\rangle=e^{2\pi i s/r}|u_s\rangle
$$
## 위상추정 {#phase-estimation}
quantum phase estimation은 유니터리의 고유위상 $\phi=s/r$를 추정합니다.
$$
U|u\rangle=e^{2\pi i\phi}|u\rangle
$$
제어된 $U^{2^k}$들을 적용하면 counting register에 위상 정보가 새겨지고, inverse QFT가 이를 이진수 근사로 바꿉니다.
## QFT의 역할 {#qft}
QFT는 주기적인 phase pattern을 sharp한 측정 분포로 바꿉니다.
$$
\mathrm{QFT}_Q|x\rangle
=
{1\over\sqrt{Q}}\sum_{y=0}^{Q-1}e^{2\pi ixy/Q}|y\rangle
$$
측정값 $y$는 대략 $y/Q\approx s/r$를 만족합니다. continued fraction으로 $r$을 복원합니다.
## 작은 예제: N=15, a=2 {#example}
$2^4=16\equiv1\pmod{15}$이므로 order는 $r=4$입니다.
$$
\gcd(2^{2}-1,15)=\gcd(3,15)=3
$$
$$
\gcd(2^{2}+1,15)=\gcd(5,15)=5
$$
따라서 $15=3\cdot5$를 얻습니다.
## 비용과 현실성 {#cost}
Shor의 이론적 장점은 다항시간입니다. 하지만 실제 회로는 modular exponentiation 때문에 매우 많은 논리 게이트와 오류정정이 필요합니다. NISQ 장비에서 큰 수를 바로 깨는 알고리즘이 아니라, fault-tolerant quantum computer의 대표 응용으로 보는 것이 맞습니다.
## 전체 흐름 요약 {#full-flow}
1. 고전적으로 $a$를 고르고 유클리드 호제법으로 $\gcd(a,N)$을 확인합니다.
2. $\gcd(a,N)>1$이면 그 값은 이미 인수 후보가 아니라 실제 인수입니다.
3. 서로소이면 확장 유클리드 호제법 관점에서 $a$의 modular inverse가 존재하고, modular multiplication이 permutation이 됩니다.
4. 양자 부분으로 order $r$ 후보를 찾습니다.
5. 위상추정이 $s/r$에 가까운 분수를 줍니다.
6. continued fraction으로 $r$ 후보를 복원합니다.
7. $a^r\equiv1\pmod N$인지 검증하고 gcd로 인수 후보를 구합니다.
8. 후보가 자명하면 실패입니다. 다른 $a$로 다시 반복합니다.
## continued fraction이 필요한 이유 {#continued-fraction}
측정은 정확한 실수 $s/r$을 주지 않고, $y/Q$라는 근사값을 줍니다. 따라서 분모가 너무 크지 않은 유리수 중에서 가장 그럴듯한 $s/r$을 찾아야 합니다.
$$
\left|{y\over Q}-{s\over r}\right|
\lesssim {1\over 2Q}
$$
continued fraction은 이 근사 분수를 효율적으로 찾아주는 고전 후처리입니다.
## 실패할 수 있는 경우 {#failure-cases}
- 고른 $a$가 우연히 유용한 짝수 order를 주지 않을 수 있습니다.
- $a^{r/2}\equiv -1\pmod N$이면 gcd가 자명해질 수 있습니다.
- 위상추정 precision이 부족하면 잘못된 $r$ 후보가 나올 수 있습니다.
그래서 Shor는 확률적 알고리즘입니다. 실패하면 다른 $a$로 다시 시도합니다.
## order가 왜 인수로 이어지는가 {#why-order-factors}
$a^r\equiv1\pmod N$이고 $r$이 짝수이면 아래처럼 쓸 수 있습니다.
$$
a^r-1
=
\left(a^{r/2}-1\right)\left(a^{r/2}+1\right)
\equiv0\pmod N
$$
즉 $N$은 두 인수의 곱을 나눕니다. 만약 $a^{r/2}\not\equiv \pm1\pmod N$이면 두 괄호는 각각 $N$ 전체를 포함하지 않으면서도 $N$과 공약수를 공유할 가능성이 생깁니다. 그래서 gcd를 계산합니다.
$$
p=\gcd(a^{r/2}-1,N),
\qquad
q=\gcd(a^{r/2}+1,N)
$$
Shor에서 양자컴퓨터가 직접 인수를 뱉는 것이 아닙니다. 양자 부분은 order $r$을 찾고, 인수 추출은 이 고전 정수론 후처리로 합니다.
## 주기 상태가 생기는 방식 {#periodic-state}
order finding을 함수 관점에서 보면 $f(x)=a^x\bmod N$의 주기 $r$을 찾는 문제입니다.
$$
f(x+r)=a^{x+r}\bmod N
=a^x a^r\bmod N
=a^x\bmod N
=f(x)
$$
첫 번째 레지스터에 균등중첩을 만들고 두 번째 레지스터에 $a^x\bmod N$을 계산하면 아래 상태가 됩니다.
$$
{1\over\sqrt Q}\sum_{x=0}^{Q-1}|x\rangle|a^x\bmod N\rangle
$$
두 번째 레지스터를 어떤 값으로 관측하면 첫 번째 레지스터는 같은 함수값을 만드는 $x$들의 등차수열 중첩으로 줄어듭니다.
$$
{1\over\sqrt L}\sum_{\ell=0}^{L-1}|x_0+\ell r\rangle
$$
QFT는 이런 주기적 spike를 주파수 영역의 spike로 바꿉니다. 이때 측정값이 $Q/r$의 배수 근처로 모입니다.
## 위상추정 버전으로 보는 Shor {#qpe-version}
현대 설명에서는 period-finding 회로를 phase estimation으로 정리하는 경우가 많습니다. $U_a|y\rangle=|ay\bmod N\rangle$를 두고, $|1\rangle$에서 시작하면 $U_a$의 고유상태들의 중첩으로 볼 수 있습니다.
$$
|1\rangle
=
{1\over\sqrt r}\sum_{s=0}^{r-1}|u_s\rangle
$$
각 고유상태는 서로 다른 고유위상 $s/r$을 가집니다.
$$
U_a|u_s\rangle
=
e^{2\pi i s/r}|u_s\rangle
$$
phase estimation을 걸면 측정은 어떤 $s$에 대한 근사분수 $s/r$를 하나 줍니다. 이 값 하나만으로도 continued fraction을 통해 $r$ 후보를 복원할 수 있습니다.
## N=15, a=2를 조금 더 길게 계산하기 {#n15-more}
나머지 거듭제곱을 직접 쓰면 주기가 보입니다.
| $x$ | $2^x\bmod15$ |
| --- | --- |
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 1 |
| 5 | 2 |
| 6 | 4 |
| 7 | 8 |
패턴은 $1,2,4,8$이 반복되므로 $r=4$입니다. 만약 counting register 크기 $Q=2^m$가 $8$이라면 이상적으로 측정값은 $0,2,4,6$ 근처로 나타납니다. 이들은 각각 $0/4,1/4,2/4,3/4$에 해당합니다.
$y=2$를 얻었다면 $y/Q=2/8=1/4$이고 분모 4가 order 후보입니다. $2^4\equiv1\pmod{15}$로 검증됩니다.
## modular exponentiation이 병목인 이유 {#modexp-cost}
phase estimation은 controlled-$U_a^{2^k}$를 요구합니다. 여기서 $U_a^{2^k}$는 아래 연산입니다.
$$
|y\rangle
\mapsto
|a^{2^k}y\bmod N\rangle
$$
$a^{2^k}\bmod N$ 자체는 고전적으로 미리 계산할 수 있습니다. 문제는 “상수 $c$를 곱하고 mod $N$으로 줄이는 reversible 회로”를 만들어야 한다는 점입니다. 이 회로는 덧셈, 비교, 조건부 뺄셈, uncompute를 많이 포함합니다.
그래서 Shor의 큰 비용은 QFT가 아니라 modular exponentiation 쪽입니다. QFT는 $O(n^2)$ controlled phase로 구현되지만, 산술 회로는 훨씬 큰 상수와 Toffoli/T-count 비용을 가집니다.