쇼어 알고리즘 I

강한 처치-튜링 논제(Strong Church-Turing Thesis) 에 따르면, 모든 물리적 계산 모델은 확률론적 튜링 머신을 통해 다항 시간 내에 시뮬레이션할 수 있다. 이는 곧 고전 컴퓨터로 효율적인 해결이 불가능한 문제는 다른 어떤 계산 모델로도 해결할 수 없음을 의미한다. 하지만 양자 컴퓨터의 등장은 이 논제에 정면으로 도전하는 계기가 되었다.

그 중심에는 바로 쇼어 알고리즘이 있다. 고전 컴퓨터로는 다항 시간 내에 해결할 수 없는 소인수분해 문제 를 양자 알고리즘을 통해 효율적으로 처리할 수 있음을 증명했기 때문이다. 이는 계산 복잡도 이론의 패러다임을 바꾸는 중요한 변곡점이 된다. 이번 글에서는 쇼어 알고리즘이 어떤 원리로 이러한 계산적 난제를 해결하는지 그 핵심 아이디어를 살펴본다.

소인수분해 문제 (Factoring Problem)

쇼어 알고리즘이 해결하고자 하는 문제는 소인수분해 문제로, 합성수 $N = p_1 p_2$에서 소인수 $p_1, p_2$를 찾는 문제이다. 어떤 결정 문제에 대한 알고리즘을 찾는 방법 중 하나는 이미 효율적 해결이 가능한 알고리즘이 있는 다른 문제로 환원하여 해결하는 것이다. 쇼어 알고리즘 또한 소인수분해 문제를 위수 찾기(Order-finding) 문제로 환원하여 해결한다.

쇼어가 소인수분해 문제 해결을 위해 사용한 정수론의 개념은 다음과 같다.

\[\boxed{ \begin{gather*} 1 < x < N, \quad x^2 \equiv 1 \pmod N \text{에 대한 비자명 해 } x \text{를 구할 수 있으면} \\ \gcd(x-1, N) \text{과 } \gcd(x+1, N) \text{ 중 하나는 } N \text{의 인수이다.} \end{gather*} } \tag{1}\]

$x$가 비자명 해를 가진다는 것은 $x^2 \equiv 1 \pmod N$의 해가 $x \equiv 1 \pmod N$과 $x \equiv N-1 \pmod N$이 아님을 의미한다. 즉, $x^2 - 1 = (x-1)(x+1) \equiv 0 \pmod N$으로 나타낼 수 있으며, $x$가 비자명하므로 $(x-1)(x+1)$이 $N$으로 나누어떨어지기 위해 $(x-1)$ 또는 $(x+1)$ 중 어느 하나가 단독으로 $N$의 배수가 될 수 없다. 따라서 $\gcd(x-1, N)$ 또는 $\gcd(x+1, N)$ 중 적어도 하나는 $N$의 유효한 인수가 된다.

$\pmod N$: 모듈러 연산을 나타내며, $N$으로 나누었을 때의 나머지를 다룬다. 예를 들어 $4 \pmod 3$은 1이다.

$\gcd(a, b)$: $a$와 $b$의 최대공약수로, 유클리드 알고리즘을 통해 매우 효율적으로 계산할 수 있다.

앞선 논의를 통해 $x$를 구할 수 있으면 $N$의 인수를 찾을 수 있음을 알았다. 그렇다면 이러한 $x$는 어떻게 구할 것인가? 그 방법은 아래와 같이 정리된다.

\[\boxed{ \begin{gather*} 1 \le y < N \text{에 대해 N과 서로소이면서 임의로 선택한 } y \text{가 짝수인 위수 } r \text{을 가지며 } \\ y^{r/2} \not\equiv -1 \pmod N \text{이면} \\ y^{r/2} \text{는 } x^2 \equiv 1 \pmod N \text{에 대한 비자명 해이다.} \\ \text{이러한 } y \text{를 뽑을 확률은 최소 } \frac{1}{2} \text{ 이상이다.} \end{gather*} } \tag{2}\]

즉 임의로 선택한 $y$에 대해 식 $(2)$를 만족시키는 위수 $r$을 구할 수 있으면, 식 $(1)$에 의해 $N$의 인수를 구할 수 있다. 따라서 소인수분해 문제는 결과적으로 위수 찾기 문제로 환원된다.

양의 정수 $N$과 $\gcd(N, x)=1$을 만족하는 $x (1\le x \lt N)$에 대해 $x^r \equiv 1 \pmod N$인 $r$을 $x$의 $\text{위수(order)}$라 부른다.

쇼어의 알고리즘

앞선 과정에서 확인했듯 소인수분해 문제는 결과적으로 위수 찾기(Order-finding) 문제로 귀결된다. 양의 정수 $N$과 $\gcd(N, a)=1$인 $a$에 대해 $a^r \equiv 1 \pmod N$을 만족하는 최소의 양의 정수 $r$을 찾기 위해 다음 함수 $f(x)$를 정의하자.

\[f(x) = a^x \pmod N\]

이 함수는 $a^r \equiv 1 \pmod N$이라는 성질로 인해 $f(x+r) = a^{x+r} \equiv a^x \cdot a^r \equiv a^x \equiv f(x) \pmod N$을 만족하며, 결국 $r$을 주기로 갖는 주기함수가 된다.

이러한 함수의 주기성을 포착하기 위해 푸리에 변환을 적용하면 주기에 해당하는 지점에서 강한 피크(Peak)가 발생하는데, 이것이 바로 쇼어 알고리즘이 난제를 해결하는 핵심 원리다.

($N=877, a=33$일 때, $g(x)=e^{2\pi i f(x)/r}$의 허수부(좌)와 $g(x)$의 푸리에 변환 결과의 실수부(우))

고전 컴퓨터에서는 거대한 $r$ 값을 찾기 위해 함숫값을 일일이 계산해야 하므로 지수적인 시간이 소요되어 효율적인 처리가 불가능하지만, 양자 컴퓨터는 양자 중첩과 양자 푸리에 변환(QFT)을 결합하여 이 과정을 비약적으로 단축한다. 구체적인 위수 찾기 양자 회로의 동작 단계는 아래와 같다.

레지스터 준비: 각각 $m, n$개의 큐비트로 구성된 두 개의 레지스터를 준비한다.
중첩 상태 생성: 첫 번째 레지스터에 하다마드(Hadamard) 게이트를 적용하여 중첩상태를 만든다. 이는 함수에 대입할 값들을 만드는 과정이다.
양자 병렬 계산: 중첩된 $x$값들에 대해 $f(x) = a^x \pmod N$을 계산하여 함숫값을 얻는다. 이 과정에서 제어 레지스터 위상에 함숫값에 대한 정보가 각인되는 위상 킥백(Phase Kickback) 현상이 발생한다. (이는 나중에 위상 추정 파트에서 자세히 다룰 것이라 여기서는 그냥 그렇구나하고 넘어가자)
양자 푸리에 변환: 양자 푸리에 변환(QFT)을 통해 $f(x)$에서 주파수(주기) 성분을 뽑아낸다.
측정 및 후처리: 측정을 통해 주기값을 획득한다. (정확히 말하자면 바로 주기값을 얻어낼 수는 없으며, 여기서 측정된 값을 고전컴퓨터에서 후처리를 통해 얻어낸다.)

이렇게 찾아낸 위수 $r$을 이용하면 최종적으로 $N$의 인수를 얻을 수 있다. 본 포스트에서는 쇼어 알고리즘의 전반적인 개요를 짚어보았으며, 각 단계에 대한 상세한 수학적 원리는 다음 글에서 이어나갈 예정이다.