Shor

먼저 기억할 것: 후보를 반복해서 찾는 알고리즘

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 계산과 후보 검증이라는 고전 후처리에서 이뤄집니다.

유클리드 호제법과 확장 유클리드 호제법

유클리드 호제법은 두 정수의 최대공약수를 빠르게 구합니다.

$$
\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으로

합성수 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

함수 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
$$

위상추정

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는 주기적인 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

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를 얻습니다.

비용과 현실성

Shor의 이론적 장점은 다항시간입니다. 하지만 실제 회로는 modular exponentiation 때문에 매우 많은 논리 게이트와 오류정정이 필요합니다. NISQ 장비에서 큰 수를 바로 깨는 알고리즘이 아니라, fault-tolerant quantum computer의 대표 응용으로 보는 것이 맞습니다.

전체 흐름 요약

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이 필요한 이유

측정은 정확한 실수 s/r을 주지 않고, y/Q라는 근사값을 줍니다. 따라서 분모가 너무 크지 않은 유리수 중에서 가장 그럴듯한 s/r을 찾아야 합니다.

$$
\left|{y\over Q}-{s\over r}\right|
\lesssim {1\over 2Q}
$$

continued fraction은 이 근사 분수를 효율적으로 찾아주는 고전 후처리입니다.

실패할 수 있는 경우

• 고른 a가 우연히 유용한 짝수 order를 주지 않을 수 있습니다.
• a^{r/2}\equiv -1\pmod N이면 gcd가 자명해질 수 있습니다.
• 위상추정 precision이 부족하면 잘못된 r 후보가 나올 수 있습니다.

그래서 Shor는 확률적 알고리즘입니다. 실패하면 다른 a로 다시 시도합니다.

order가 왜 인수로 이어지는가

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을 찾고, 인수 추출은 이 고전 정수론 후처리로 합니다.

주기 상태가 생기는 방식

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

현대 설명에서는 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를 조금 더 길게 계산하기

나머지 거듭제곱을 직접 쓰면 주기가 보입니다.

패턴은 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이 병목인 이유

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 비용을 가집니다.