양자 알고리즘: 소인수 분해 알고리즘

이전 글 “양자 컴퓨터의 기원”에서 우리는 도이치-조사 알고리즘에 대해 이야기했다. 이 알고리즘을 통해 우리는 양자 컴퓨터가 특정한 문제에 대해서는 기존 컴퓨터에 비해서 훨씬 빠르게 답을 알아낼 수 있다는 점을 살펴보았다. 이는 양자 컴퓨터가 기존 컴퓨터보다 단순히 수십 배나 수백 배, 혹은 수억 배 빠른 속도로 같은 연산을 할 수 있기 때문이 아니다. 양자 컴퓨터에서는 (기존 컴퓨터에 존재하지 않는) 양자역학적인 효과를 이용한 연산을 할 수 있는데, 이런 특별한 연산 방식을 사용하면 문제를 푸는데 필요한 절대적인 연산량을 현격하게 줄일 수 있기 때문이다.

하지만 도이치-조사 알고리즘으로 해결할 수 있는 문제는 현실적으로 썩 유용한 문제는 아니다. 도이치와 조사가 만든 알고리즘은 주어진 함수의 치역이 하나 혹은 두 개의 값을 가질 때 둘 중 어느 경우인지 빠르게 구분할 수 있는 알고리즘인데, 이 알고리즘을 완전히 일반적인 함수에 적용할 수는 없기 때문이다. 사람들의 관심이 쏠릴 만한 유용한 문제를 해결할 수 있는 양자 알고리즘이 개발되기까지는 또다시 몇 년의 시간이 필요했다.

양자 컴퓨터에 대한 관심이 높아지게 된 계기는 1996년 피터 쇼어^{Peter Shor}의 소인수 분해 알고리즘의 발견이었다.[1] 이는 지금도 여전히 가장 유명한 양자 알고리즘 중 하나인데, 발견 당시에 엄청난 반향을 일으켰다. (고전적인 컴퓨터를 사용하는) 가장 빠른 알고리즘은 소인수 분해를 할 숫자의 크기가 \(n\)비트일 때 필요한 연산량이 \(n^{1/3}\)에 대해서 지수함수적으로 증가한다.[2] 그에 반해서 쇼어의 알고리즘은 \(n\)이 커짐에 따라 필요한 연산량이 대략 \(n^3\)처럼 증가한다. 이전 글 “양자 컴퓨터의 기원”에서도 말했듯이 \(n\)이 충분히 커지면 두 번째 (양자) 알고리즘이 첫 번째 (고전) 알고리즘보다 훨씬 빨라지게 된다. 

구체적인 숫자를 언급해 보자면, 최근 구글 양자 컴퓨터 연구팀에서는 \(2048\)-비트 자연수를 양자 컴퓨터를 이용해 소인수 분해하기 위해서는 대략 8시간 정도의 시간이 걸린다고 주장했다.[4] 이러한 자연수를 십진수라 나타내기 위해서는 대략 600여 개의 자리가 필요하다. 이렇게 큰 소인수의 분해를 양자 컴퓨터로 구현하기 위해서는 엄청나게 많은 숫자의 큐빗이 필요하고, 또 이러한 대규모의 컴퓨터를 만들기 위해서는 엄청나게 많은 노력과 투자가 필요할 것이다.¹ 하지만 이러한 컴퓨터를 만드는 데에는 기술적인 어려움이 있을 뿐이지 자연 법칙상 불가능한 것은 아니라고 많은 전문가들은 생각하고 있다. 현재의 수많은 암호 체계는 \(1024\) 내지 \(2048\)비트 자연수의 소인수 분해가 어렵다는 사실에 기반하고 있기 때문에, 만약 양자 컴퓨터의 소인수 분해가 정말 8시간 내에 가능하다면 이러한 암호체계들은 전부 무력화된다고 보아야 한다.

비록 쇼어의 알고리즘은 소인수 분해라는 문제에 국한되어 있지만, 그 작동 원리는 현재 개발되어 있는 다양한 양자 알고리즘에 많이 쓰이고 있다. 때문에, 이번 글에서는 소인수 분해 알고리즘의 작동 원리에 대해서 간단하게 이야기해보고자 한다. 소인수 분해 알고리즘이 어떠한 방식으로 작동하는지 잘 이해하면 다른 양자 알고리즘들의 원리를 이해하는 데 도움이 될 것이다.

소인수 분해 알고리즘은 말 그대로, 어떤 자연수 \(N\)을 소수의 곱으로 나타내는 것을  목표로 한다. 쉽게 설명하기 위해서 자연수 \(N\)이 두 개의 소수 \(p,q\)의 곱으로 이루어져 있다고 가정해 보겠다. 우리의 목표는 \(N\)이 주어졌을 때 \(p\)와 \(q\)를 빠른 시간 안에 알아내는 것이다. 가장 쉽게 시도해 볼 수 있는 방법은 일일이 소수를 하나씩 대입해서 \(N\)이 그 소수로 나누어지는지 확인해 보는 것이다. 만약 \(N\)이 \(n\)-비트 짜리 숫자라면 이 방법은 \(n\)에 대해서 지수함수적으로 많은 연산을 필요로 한다.

쇼어는 이 문제를 풀기 위해서 다음과 같은 정수론의 잘 알려진 사실을 이용했다. 앞에서도 말했듯이 자연수 \(N\)이 주어졌을 때 이를 소인수 분해하는 것이 목표라고 하자. 일단 어떤 자연수 \(a\)가 주어졌을 때, \(a^{x}=1\mod N\)을 만족하는 자연수 \(x\)를 찾았다고 하자. 여기서 \(c \mod M\)은 \(c\)를 \(M\)으로 나눈 나머지를 의미한다.² 만약 이런 조건을 만족하는 \(x\)를 찾았다면 \(a^x-1\)은 \(N\)의 배수가 된다. 그리고 만약 \(x\)가 짝수라면 \(a^x-1\)을 \((a^{x/2}-1)(a^{x/2}+1)\)로 쉽게 소인수 분해할 수 있는데, 이 점을 이용해서 \(N\)의 소인수 분해를 쉽게 할 수 있다. 실제로, 만약 \(x\)가 짝수이고 \(a^{x/2}+1\mod N\)이 \(0\)이 아니면 \(a^{x/2} -1\)과 \(N\)의 최대 공약수는 \(N\)의 소인수가 되어야만 한다는 정수론에서 잘 알려진 사실이 있다.

여기서 주목해야 할 점 세 가지가 있다. 첫째 \(a\)를 \(1\)과 \(N-1\) 사이의 범위에서 아무 정수나 무작위로 골랐을 때, 최소한 \(50\%\)의 확률로 위의 조건을 만족하는 \(x\)가 존재한다.[1] 이 또한 정수론에서 잘 알려진 사실이다. 둘째 두 개의 \(n\)-비트 자연수가 주어졌을 때 이 둘의 최대 공약수는 효율적으로 계산할 수 있다. 독자들이 초등학교 때 배운 방식으로 최대 공약수를 구하면 대략 \(n\)에 비례하는 횟수의 사칙 연산을 통해서 최대 공약수를 구할 수 있다.³ 셋째 \(a^{x}\mod N\) 역시 \(n\)에 비례하는 횟수의 사칙 연산을 통해서 계산할 수 있다. 얼핏 생각하면 \(x\)는 \(1\)부터 \(N-1\)까지의 정수값을 가질 수 있으므로, 최악의 경우 \(N-2\)번의 곱셈을 해야 한다고 생각할 수도 있다. 예를 들어서 \(a^{N-1}\)을 계산하기 위해서는 다음과 같은 방법을 사용한다고 생각해 보자.

\begin{equation}
\begin{aligned}
a \times a &= a^2 \\
a^2 \times a &= a^3 \\
\vdots & \\
a^{N-2} \times a &= a^{N-1}.
\end{aligned}\quad \cdots \quad (1)
\end{equation}

이 경우 총 \(N-2\)번의 곱셈을 해야 한다. 하지만 다음과 같은 방법을 이용하면 훨씬 빠르게 계산을 할 수 있다. 예를 들어서 \(x\)가 \(2\)의 지수 꼴이라고 가정해보자. 만약 \(x=2^m\)이면, 다음처럼 \(m\)번의 거듭제곱을 이용해서 \(a^x\)를 계산할 수 있다.

\begin{equation}
\begin{aligned}
a \times a &= a^2 \\
a^2 \times a^2 &= a^4 \\
\vdots & \\
a^{2^{m-1}} \times a^{2^{m-1}} &= 2^{2^m}.
\end{aligned}
\label{eq:trick}\quad \cdots \quad (2)
\end{equation}

만약 \(x=2^m\)의 꼴이라면 이 방법을 이용해서 총 \(m\)번만의 곱셈으로 \(a^{2^m}\)을 계산할 수 있다. 총 \(m\)번의 곱셈을 통해서 \(a^{2^m}\)을 계산할 수 있다. 더 일반적인 \(x\)의 경우는 총 \(\frac{n(n-1)}{2}\)번의 사칙 연산을 통해서 계산할 수 있다.

요지는 이렇다. \(a\)가 무작위로 주어졌을 때, \(a^{x}=1\mod N\)을 만족하는 \(x\)를 구할 수만 있다면 소인수 분해를 빠르게 할 수 있다. 문제는 고전 컴퓨터에서는 이러한 \(x\)를 빠르게 구할 수 있는 알고리즘이 알려져 있지 않다는 점이다. 쇼어는 정확히 이 문제를 양자 컴퓨터를 이용해서 빠르게 해결할 수 있다는 사실을 발견했다. 그렇다면 이 문제를 어떠한 접근 방식으로 해결할 수 있는지 좀 더 자세히 알아보자.

주기 함수의 특징

쇼어의 소인수 분해 알고리즘에서 핵심적인 대목은 함수 \(f(x) = a^x \mod N\)가 주어졌을 때 \(f(p)= 1\)을 만족하는 \(p\)를 찾는 것이다. 쇼어는 함수 \(f(x)\)가 주기 함수라는 사실을 이용해서 빠른 소인수 분해 알고리즘을 찾아낸다. 주기 함수는 일정한 주기로 같은 패턴이 반복되는 함수를 말한다. 함수 \(f(x)\)의 경우에는 모든 \(x\)에 대해서\(f(x+p) = f(x)\)라는 사실을 쉽게 알 수 있다. 이 함수는 다음과 같은 식을 만족하기 때문이다.

\begin{equation}
\begin{aligned}
a^{x+p} \mod N &= (a^x \mod N) \times (a^p \mod N) \\
&= a^x \mod N.
\end{aligned}\quad \cdots \quad (3)
\end{equation}

여기서 흥미로운 사실은 다음과 같다. 비록 어떤 \(x\)값에 대해서 함수값 \(f(x)\)를 계산하는 일 자체는 효율적으로 할 수 있지만, 이 함수의 주기를 알아내는 일은 효율적으로 하기가 쉽지 않다. 함수 \(f(x)\)는 위에 등장하는 식 (2)의 방법을 사용하면  빠르게 계산할 수 있지만 여전히 주기를 알아내기 위해서는 수많은 \(x\)에 대해서 함수 \(f(x)\)의 값을 일일이 구해야 하기 때문이다. 고전적인 컴퓨터를 이용해서 이렇게 주기적인 함수의 주기를 효율적으로 알아내는 방법은 알려져 있지 않다. 앞에서도 말했듯이 다양한 \(x\)를 일일이 넣어가면서 \(f(x)=1\)을 만족하는지 확인하려면 \(N\)에 비례하는 연산 시간이 필요하다. \(N\)은 \(n\)-비트 숫자이므로 이에 필요한 연산 시간은 \(n\)에 대해 지수함수적으로 증가한다. 현재 암호 체계에서 쓰이고 있는 \(n\)의 크기는 \(1000\)비트 정도 되는데, 이 경우 \(N\)의 범위는 \(1\)부터 \(10^{300}\)정도 된다. 함수의 값을 일일이 계산하기에는 너무나도 많은 연산이 필요하다.

어떤 함수의 주기를 좀 더 간단하게 알아내는 방법은 없을까? 주기적인 함수를 분석하는 데 큰 도움이 되는 방법 중 하나는 퓨리에 변환^{Fourier transform}이다. 이는 다음과 같이 정의되는 수학적 변환이다.

\begin{equation}
g(x) \to \hat{g}(p) = \int_{-\infty}^{\infty} g(x) e^{- 2\pi ip x} dx
\quad \cdots \quad (4) \end{equation}

예를 들어 [그림1]에 보이는 함수에 퓨리에 변환하면, [그림2]처럼 어떤 한 점을 중심으로 큰 피크가 발생하고 나머지 구간에서는 거의 \(0\)에 가까운 값을 갖는 함수를 얻게 된다. 피크가 발생하는 점은 바로 함수 \(g(x)\)의 주파수에 해당된다. 함수 \(f(x)\)의 주기와 \(g(x)\)의 주파수는 동일하므로, \(g(x)\)의 주파수를 통해서 \(f(x)\)의 주파수를 구할 수 있다. 주파수 \(f\)와 주기 \(T\)는 \(f=2\pi / T\)의 관계를 가지므로 주파수를 통해서 \(f(x)\)의 주기를 알아낼 수 있다.

이를 통해 우리는 다음과 같은 중요한 사실을 알아낼 수 있다. 만약 일반적인 함수의 퓨리에 변환에서 피크가 발생한 지점을 쉽게 찾아낼 수 있다면, 이를 통해서 소인수 분해를 쉽게 할 수 있다. 그 이유는 다음과 같다. 만약 퓨리에 변환의 피크를 쉽게 찾아낼 수 있는 방법이 존재한다면 이를 통해서 본래 함수인 \(g(x)\)의 주기를 알아낼 수가 있다. 이러한 방법은 주기함수의 사례라고 할 수 있는 \(f(x)=a^x\mod N\)에도 적용될 수 있으므로 이 함수의 주기를 쉽게 알아낼 수 있다. 함수 \(f(x)\)의 주기를 쉽게 알아낼 수 있으면 소인수 분해도 쉽게 할 수 있다.

아쉽게도 고전 컴퓨터에서는 이 사실을 이용하더라도 소인수 분해를 하기는 여전히 어렵다. 앞선 식 (4)에서 도입한 퓨리에 변환을 하기 위해서는 수많은 점에서의 함수 값을 읽어 들여야 하기 때문이다. 일반적으로 퓨리에 변환을 하는데 필요한 연산의 개수는 \( N \log N\)처럼 증가한다고 알려져 있다.⁴ \(N\)은 \(n\)에 대해 지수적으로 증가하기 때문에 퓨리에 변환을 하기 위한 연산은 \(n\)에 대해서 결국 지수적으로 증가하게 된다.

빠른 주기 찾기

고전 컴퓨터와는 다르게, 양자 컴퓨터에서는 주기적인 함수의 주기를 빠르게 알아낼 수 있다. 앞에서도 말했듯이, 고전 컴퓨터에서 퓨리에 변환을 통해 주기를 알아내는 데에는 두 가지 문제가 있다. 첫째, 퓨리에 변환을 하기 이전에 이미 함수의 값을 여러 \(x\)값에서 계산해 두어야 한다. 둘째, 퓨리에 변환을 하는 과정 자체가 많은 연산을 요구한다.⁵ 

양자 컴퓨터에서는 이 두 가지 문제를 동시에 해결할 수 있다. 우선 첫 번째 문제를 어떻게 해결할 수 있는지에 대해서 알아보자. 이전 글에서도 말했지만, 양자 컴퓨터에서는 다음과 같은 두 가지 연산을 쉽게 할 수 있다. 첫째, \(n\)개의 큐빗이 있을 때, \(N=2^n\)개의 상태가 중첩된 상태를 만들어 낼 수 있다:

\begin{equation*}
|0\rangle + |1\rangle + \cdots + |N-1\rangle.
\end{equation*}

둘째, 고전적 컴퓨터를 이용해서 실수 함수인 \(f(x)\)의 값을 효율적으로 계산했다고 치면, 위에 등장하는 파동 함수의 상태 각각에 대해 위상 변환을 아래처럼 준 상태를 어렵지 않게 만들어 낼 수 있다:

\begin{equation*}
e^{2\pi if(0)/N}|0\rangle + e^{2\pi if(1)/N}|1\rangle + \cdots e^{2\pi if(2^n-1)/N}|N-1\rangle.
\end{equation*}

각 양자역학적 상태 앞에 곱해진 함수는 정확히 [그림1]에 나온 함수의 형태와 일치한다. 조금 더 설명하자면, [그림1]은 위상 \(e^{2\pi if(x)/N}\)의 실수 부분에 해당한다.

즉, 양자 컴퓨터에서는 각각의 상태 \(|x\rangle\)가 \(g(x) = e^{2\pi i f(x)/N}\)의 위상을 갖는 중첩 상태를 손쉽게 만들어 낼 수 있다. 중요한 점은 이러한 중첩 상태를 만들어 내는데 필요한 기본 연산의 숫자가 \(n\)에 대해서 “겨우” 다항식처럼 증가한다는 점이다. 첫 번째 단계인 \(N\)개의 상태가 중첩된 상태를 만들어 내는 데에는 \(n\)번의 기본 연산으로 충분하고, 두 번째 단계에서는 \(f(x)\)를 단 한 번만 계산하는 것으로 충분하다.⁶ 

마지막으로, 양자 컴퓨터에서는 \(g(x)|x\rangle\)의 중첩 상태, 즉

\begin{equation*}
g(0)|0\rangle + g(1)|1\rangle +\cdots + g(N-1)|N-1\rangle
\end{equation*}

가 주어졌을 때, 이를 \(\hat{g}(p)|p\rangle\)의 중첩상태로 쉽게 바꿀 수 있다. (여기서 \(\hat{g}(p)\)는\(g(x)\)의 퓨리에 변환이다.) 좀 더 정확히 말하자면, 쇼어는 양자 컴퓨터에서 다음과 같은 변환을 \(\sim n \log n\)에 비례하는 연산량으로 해결할 수 있다는 사실을 발견한다.

\begin{equation*}
g(0)|0\rangle + g(1)|1\rangle +\cdots + g(N-1)|N-1\rangle \to \hat{g}(0)|0\rangle + \hat{g}(1)|1\rangle + \cdots + \hat{g}(N-1)|N-1\rangle.
\end{equation*}
앞에서 말한 세 가지 양자 연산에 대해서 다시 정리해 보자. 첫 번째 단계에서 모든 상태들이 동시에 존재하는 중첩 상태를 만든다. 여기에서는 \(n\)에 비례하는 연산량이 필요하다. 두 번째 단계에서는 \(f(x)\)를 한번 계산하는데 필요한 연산량이 필요하다. 세 번째 단계, 즉 퓨리에 변환에서는 \(\sim n\log n\)에 비례하는 연산량이 필요하다. 때문에, 만약 \(f(x)\)를 계산하는데 필요한 연산량이 \(n\)에 대해서 다항식처럼 증가하게 되면 이 세 단계의 연산을 하는데 총 필요한 연산량은 \(n\)에 대해서 다항식처럼 증가하게 된다.

비슷한 과정을 고전 컴퓨터에서 하려면 훨씬 많은 연산량이 필요하다. 첫 번째 단계는 고전 컴퓨터에 비슷한 과정이 없어서 비교하기 어렵지만, 최소한 퓨리에 변환을 하는데 \(N\)에 비례하는 시간이 걸린다. 여기서 \(N=2^n\)이므로 총 필요한 연산량은 \(n\)에 대해서 지수함수적으로 증가하게 된다.

마지막으로, 주기를 알아내기 위해서는 상태를 직접 측정해야 한다. 양자 역학의 공리상 \(\hat{g}(p)|p\rangle\)의 중첩 상태를 측정하면 \(|\hat{g}(p)|^2\)에 비례하는 확률로 \(p\)값이 측정된다. [그림2]에서 보이는 것처럼 \(|\hat{g}(p)|^2\)는 대부분의 점에서 \(0\)에 가까운 값을 가지고 \(g(x)\)의 주파수 근처에서만 큰 값을 갖는다. 때문에, 높은 확률로 우리는 \(g(x)\)의 정확한 주파수를 알아낼 수 있다. 주파수의 값을 알아내기 위해 우리가 해야 할 일이라곤 그저 상태를 읽어내는 것뿐이다. 읽어낸 상태는 2진수 숫자인데, 이 숫자는 대단히 높은 확률로 \(g(x)\)의 주파수의 값을 가지게 된다. 함수 \(f(x)\)의 주파수는 함수 \(g(x) = e^{2\pi i f(x)/N}\)의 주파수와 동일하므로 이를 통해서 우리는 \(f(x)\)의 주파수를 알아낼 수 있다.⁷ 물론 이를 통해서 \(f(x)\)의 주기를 빠르게 알아낼 수 있다. 이 방법을 통해서 양자 컴퓨터에서는 (효율적으로 계산할 수 있는) 함수 \(f(x)\)의 주기를 고전 컴퓨터보다 훨씬 빠르게 알아낼 수 있다.

빠른 소인수 분해

다시 소인수 분해 알고리즘에 대해서 생각해 보자. 우리는 위에서 양자 컴퓨터가 일반적인 함수의 주기를 고전 컴퓨터보다 훨씬 빠르게 계산할 수 있다는 사실을 발견했다. 만약 함수 \(f(x)\)를 어떤 방법으로 (가령 고전 컴퓨터를 이용해서) 효율적으로 계산할 수 있다면, 양자 컴퓨터로는 함수 \(f(x)\)의 주기를 고전 컴퓨터에 비해 훨씬 효율적으로 계산할 수 있다.

쇼어의 알고리즘은 이 사실을 다음과 같이 이용한다. 소수 \(p,q\)의 곱으로 이루어진 자연수 \(N\)이 주어졌다고 가정하자. 우리는 \(p\)와 \(q\)를 다음과 같은 방식으로 계산할 수 있다.

여기서 첫 번째와 세 번째 단계는 기존의 컴퓨터로도 쉽게 처리할 수 있다. 하지만 두  번째 단계에서는 양자 컴퓨터가 반드시 필요하다. 세 번째 단계에서 \(N\)의 소인수를 구할 확률은 \(50\%\)이상이므로, 이 과정을 반복하다 보면 높은 확률로 \(N\)의 소인수 분해를 할 수 있다.

앞에서도 말했듯이 \(f(x) = a^x \mod N\)을 계산하는 데에는 \(n\)에 대해서 다항식처럼 증가하는 연산량으로 충분하다. 이 때문에 양자 컴퓨터를 이용해서 이 함수의 주기를 알아내는 데에는 \(n\)에 대해서 다항식처럼 증가하는 연산량으로 충분하다. 알고리즘의 나머지 부분은 쉽게 할 수 있는 계산이므로 이 알고리즘을 이용해서 자연수의 소인수 분해를 빠르게 할 수 있다. 이것이 쇼어의 소인수 분해 알고리즘이 작동하는 원리이다.

마치며

쇼어의 소인수 분해 알고리즘이 놀라운 점은 고전 컴퓨터를 사용하는 그 어떠한 알고리즘보다 필요한 연산량이 \(n\)에 대해서 지수함수적으로 적다는 점이다. 이 때문에 사람들은 양자 컴퓨터를 이용해서 다양한 문제를 기존 컴퓨터보다 훨씬 빠르게 풀 수 있지 않을까 하는 기대감을 가졌었다. 양자 역학을 이용해서 기존의 컴퓨터에게 어려운 문제를 훨씬 빠르게 풀 수 있을지도 모른다는 기대감은 양자 컴퓨터라는 분야를 이끌어 온 중요한 원동력 중의 하나였다.

쇼어의 소인수 분해 알고리즘 발견을 계기로 사람들은 양자 컴퓨터를 이용한 빠른 알고리즘 개발에 대해서 본격적으로 연구하기 시작했다. 1990년대에 시작된 이러한 노력들은 지금까지 이어지고 있고, 더 이상 양자 알고리즘에 관한 연구는 소인수 분해에만 국한되지 않는다. 많은 연구자들이 이제 물질 시뮬레이션, 최적화, 인공 지능과 같은 다양한 분야에 걸친 알고리즘들을 개발 중이다. 이와 더불어 구글이나 IBM, 마이크로소프트 같은 대기업들의 투자가 이어지면서 양자 컴퓨터 분야에 활기가 돌고 있다.

이렇게 다양한 알고리즘이 얼마나 단기간에 현실에서 실현될 수 있을지, 또 사회에 어떠한 영향을 미칠 수 있는지 이해하기 위해서는 양자 컴퓨터의 소프트웨어와 하드웨어적 측면에 대한 복합적인 고려가 필요하다. 예를 들어, 소인수 분해 알고리즘을 이용해서 현존하는 암호를 깨기 위해서는 상당한 대규모의 양자 컴퓨터가 필요하다. 때문에 전문가들은 당분간 양자 컴퓨터 때문에 암호 체계가 붕괴될 위험은 많지 않을 것으로 예상하고 있다. 하지만 양자역학적인 물질 시뮬레이션 같은 목적으로는 비교적 작은 양자 컴퓨터로도 현재 해결하기 어려운 문제들을 해결할 수 있을 것이라는 것이 정론이다. 이러한 이야기들은 다음 연재에 이어서 이야기해보도록 하겠다.