수많은 양자컴퓨터에 관한 연구가 보고되고 있는 요즈음, 뉴스에서도 종종 양자컴퓨터에 대한 이야기를 들을 수 있다. 그러한 기사에서는 종종 "쇼어 알고리즘"을 언급하며 기존 보안체계 붕괴 등을 전망한다. 본 글에서는 양자컴퓨팅이란 무엇인지부터 시작하여 양자컴퓨팅에 대한 기반 지식이 없는 독자가 쇼어 알고리즘을 이해하는 것을 목표로 한다.
Part I. What is "Qubit"?
"비트(bit)"라는 말을 들어보았는가? 고전적인 컴퓨터(현재 사용되는 컴퓨터)에서 다루는 가장 기본적인 단위의 데이터이며, 0 또는 1의 값을 갖는 한 자리의 이진수이다. 고전 컴퓨터는 여러 비트를 조합하여 여러 자리의 이진수를 표현하고, 이를 이용하여 수많은 데이터를 표현한다. 예를 들자면, 이진수로 1011101로 표현되는 수 93은 7개 이상의 비트를 조합하여 표현할 수 있다. 고전적인 컴퓨터는 전류가 흐르거나 흐르지 않음으로 비트의 값을 표현한다. 일반적인 디지털 컴퓨터는 전류의 구체적 세기와는 무관하게 역치값 이상의 전류가 흐르느냐의 여부로 0과 1이 정확히 나뉘는 이산적인 체계를 갖고 있다. 이것이 "디지털" 컴퓨터라고 불리는 이유이기도 하다.
양자컴퓨터는 "큐비트(Qubit)"라는 단위로 정보를 저장한다. 고전적인 컴퓨터에서 비트에 대응되는 개념인데, 그 저장 방식이 처음 보면 다소 신기하다. 양자컴퓨터의 핵심은 "중첩"이라는 물리적 현상으로, 간단하게 이야기하자면 매우 작은 입자를 관측하지 않는다면 그 입자는 여러 상태가 동시에 존재하다가 관측할 경우 그 중 하나로 랜덤하게 상태가 확정되는 현상이다. 랜덤박스를 생각한다면 이해가 좀 더 쉬울 것이다. 열기 전까진(관측하기 전까진) 내용물을 알 수 없지만(여러 상태가 동시에 존재하지만) 상자를 열면(관측하면) 내용물이 무엇인지를 확실히 알 수 있다.(상태가 확정된다.) 다만 이러한 비유는 실제 물리적인 현상과는 차이가 있어 오개념이 생길 수 있으므로, 이해가 잘 되지 않는다면 단순히 관측하면 여러 값 중 하나가 랜덤으로 선택되어 보여진다고 생각하면 된다.
이제부터 약간의 수식들과 함께 설명하고자 한다. 수식 없이 쇼어 알고리즘을 설명하기란 불가능에 가깝기 때문에, 양해를 바란다.
하나의 큐비트는, 관측할 때 "0"과 "1"이라는 두 가지 상태 중 하나로 확정되는 중첩 상태에 놓여있다. 즉, 큐비트는 관측 시 각각의 상태가 될 확률을 표기하는 것으로 표현하는 것이 합리적일 것이다.
위 이미지에서 $a$와 $b$는 무엇을 의미하는 것일까? 자세한 물리적 내용은 생략하나 각각의 상태는 파동으로써 표현되어, 확률은 파동의 변위의 제곱으로 표현되므로 $a^2+b^2$이 확률의 총 합으로 1이 되어야 함을 알 수 있다. $a$와 $b$는 두 상태에 해당하는 파동의 scale factor라고 생각할 수 있다. (물리적인 디테일은 크게 중요하진 않으므로 이해가 가지 않는다면 생략해도 좋다.)
우리는 큐비트들을 벡터를 이용하여 표현한다. Bra-Ket Notation이라 하는 표기법을 이용하는데, 행벡터를 Bra, 열벡터를 Ket이라 부르고 다음과 같이 표기한다.
$$\vert x\rangle=\begin{bmatrix}a_1 \\a_2 \\\vdots\end{bmatrix}$$
$$\langle x\vert=\begin{bmatrix}a_1 a_2 \cdots\end{bmatrix}$$
양자컴퓨팅과 관련한 수식 전개에서 흔히 사용되는 곱셈은 주로 내적(inner product)이므로, 우리는 $\vert a\rangle$와 $\vert b\rangle$의 내적을 $\langle a\vert b\rangle$과 같이 적는다.
또한, 본 글에서 사용되는 모든 벡터는 복소수체 $\mathbb{C}$에서 정의되므로, transpose 대신 hermition을 취한다는 것을 염두하고 글을 읽도록 하자.
$$\langle x\vert = \vert x \rangle^H$$
임의의 큐비트의 상태는 $\vert x\rangle = A\vert 0\rangle+B\vert 1\rangle$과 같이 표현된다. 이때 아래의 사실을 기억하고 넘어가자.
$$\vert 0\rangle=\begin{bmatrix}1\\0\end{bmatrix},\vert 1\rangle=\begin{bmatrix}0\\1\end{bmatrix}$$
$$|A|^2+|B|^2=1$$
여기서 $A,B$는 복소수이므로 단순히 제곱하는 것이 아닌, norm의 제곱을 구하여야 한다.
복소수의 극형식을 이용하면 $\vert x\rangle=ae^{i\theta}\vert 0\rangle+be^{i\phi}\vert 1\rangle$와 같이 표현할 수 있고, 두 상태0과 1이 물리적으로는 파동으로 표현된다는 것을 생각하면 중요한 것은 진폭과 위상 차이뿐이며, 실제 위상의 값은 중요하지 않으므로 $e^{i\theta}$로 나누어 소거하면 $\vert x\rangle=a\vert 0\rangle+be^{i\phi}\vert 1\rangle$로 표현할 수 있다.
$a^2+b^2=1$이므로 $a=\cos{\frac{\theta}{2}},b=e^{i\phi}\sin{\frac{\theta}{2}}$로 표현해보자. 구면좌표계 $(\sin\theta \cos\phi,\sin\theta \sin\phi,\cos\theta)$를 이용하면 우리는 임의의 큐비트 상태를 어떤 구면 위에 표현할 수 있음을 알 수 있다. 이를 블로흐 구면(Bloch Sphere)라고 부른다. x,y,z축의 단위벡터는 각각의 $\theta,\phi$를 계산해보면 $\frac{\vert 0\rangle+\vert 1\rangle}{\sqrt{2}},\frac{\vert 0\rangle+i\vert 1\rangle}{\sqrt{2}},\vert 0\rangle$라는 사실을 발견할 수 있다. 흔히 $\frac{\vert 0\rangle+\vert 1\rangle}{\sqrt{2}}$를 $\vert+\rangle$로, $\frac{\vert 0\rangle-\vert 1\rangle}{\sqrt{2}}$를 $\vert-\rangle$로 쓴다.
여러 수식을 이용하여 거창하게 설명했으나, 기억해야 할 점은 아직 단 하나의 큐비트에 대해서 설명했을 뿐이라는 사실이다. 당연하게도 실제로 유의미한 알고리즘을 작성하려면 여러 개의 큐비트를 동시에 사용해야 한다. 큐비트 $\vert x\rangle_0,\vert x\rangle_1,\vert x\rangle_2,\cdots$를 동시에 사용하면, 그 전체를 다루기 위한 벡터를 다음과 같이 표기할 수 있다.
$$\vert \psi\rangle=\vert x\rangle_0\otimes\vert x\rangle_1\otimes\vert x\rangle_2\otimes\cdots$$
여기서 $\otimes$는 tensor product로, $m\times n$ 행렬 $A$와 $p\times q$ 행렬 $B$의 tensor product는 다음과 같은 $mp\times nq$ 행렬로 정의된다. 또한 정의에서 알 수 있듯, tensor product는 결합 법칙이 성립한다.
$$A\otimes B = \begin{bmatrix}A_{11}B & A_{12}B & \cdots & A_{1n}B \\A_{21}B & A_{22}B & \cdots & A_{2n}B \\\vdots & \vdots & \ddots & \vdots \\A_{m1}B & A_{m2}B & \cdots &A_{mn}B\end{bmatrix}$$
우리는 여러 큐비트를 다룰 때 $2\times 1$ 행렬 $n$개의 tensor product를 이용하므로 이는 $2^n\times 1$ 행렬로써 표현된다. 이는 각각의 큐비트가 0 또는 1로 관측되는 $2^n$개의 모든 경우의 수를 표현하며, 해당 entry에 존재하는 값은 그 상태로 관측될 확률에 비례한다고 볼 수 있다. 따라서 우리는 $n$개의 큐비트를 사용할 때 $2^n$개의 기저가 필요하며, 이를 0부터 $2^n-1$까지의 수에 대응하여 다음과 같은 벡터로 표기한다.
$$\vert 0\rangle,\vert 1\rangle,\vert 2\rangle,\cdots,\vert 2^n-1\rangle$$
Part II. Control Qubits
고전적인 컴퓨터에서는 비트를 조작하는 방법으로 논리 게이트를 이용한다. 하나, 혹은 그 이상의 비트의 값을 받아 또 다른 값(혹은 값들)을 생성하는 것이 AND, OR, NOT, XOR과 같은 게이트들의 기능임을 알고 있을 것이다. 마찬가지로 양자컴퓨터에서는 큐비트를 조작하는 방법으로써 양자 논리 게이트를 이용한다.
논리 게이트는 여러 값을 받아서 하나의 값을 출력하거나 하나의 값을 받아 여러 값을 출력할 수도 있었으나, 이는 양자 논리 게이트에서는 불가능하다. 양자 논리 게이트에서는 정보의 소실이 발생할 수 없기 때문이다. 이러한 조건을 만족하는 연산을 unitary operation이라 하며 며 이에 해당하는 행렬 $U$는 unitary matrix이다.
$$UU^H=I, U^{-1}=U^H$$
다음은 몇가지 게이트의 예시이다.
$$\text{Pauli-X}=\begin{bmatrix}0&1\\1&0\end{bmatrix}$$
$$\text{Hadamard}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$$
$$\text{Controlled Not(CX)}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$
Pauli-X 게이트는 블로흐 구면에서 X축을 기준으로 180도 회전하는 연산이며, Hadamard 게이트는 Y축을 기준으로 반시계 방향 90도 회전하는 연산이다. $H(\vert 0\rangle) = \vert+\rangle, H(\vert 1\rangle)=\vert-\rangle$이며 $H(\vert +\rangle) = \vert 1\rangle, H(\vert -\rangle)=\vert0\rangle$이므로 초기 상태를 중첩상태로 만드는 등의 상황에서 자주 사용한다. Controlled Not 게이트는 입력 중 첫 비트를 Controlled bit로 사용하여, 해당 비트가 1일 때만 두 번째 비트에 Pauli-X 게이트를 적용한다.
Part III. Shor's Algortihm explained
드디어 글의 주제인 쇼어 알고리즘을 설명하고자 한다. 쇼어 알고리즘은 어떤 자연수 $N$의 비자명한 인수를 비트 수에 대한 다항시간복잡도에 해결하는 알고리즘이다. 고전적인 컴퓨터에서는 현재 $O(N^{1/4+\epsilon})$ 정도의 알고리즘이 알려져 있다는 사실을 생각하면 큰 수에 대해서는 가히 혁명적인 개선이다. 쇼어 알고리즘은 크게 다음과 같은 4개의 단계로 구분할 수 있다. 단계에 따라 살펴보자.
- 임의의 정수 $1<a<N$을 선택한다. $\gcd(a,N)\neq 1$이라면 $\gcd(a,N)$은 $N$의 비자명 인수이므로 이를 반환한다. (classic)
- 정의역이 $\{0,1,2,\cdots,Q-1\}$인 함수 $f(x)=a^x\mod N$의 주기 $r$을 구한다. (quantum)
- $r$이 홀수이거나, $a^{r/2}\equiv -1\text{ }(\text{mod }N)$이라면 1.로 돌아간다. (classic)
- $\gcd(a^{r/2}-1,N)$과 $\gcd(a^{r/2}+1,N)$을 반환한다. (classic)
Step 1.
gcd의 정의에 따라 $\gcd(a,N)$은 $N$의 약수이다. $1\le \gcd(a,N)\le a<N$이므로 $\gcd(a,N)\neq 1$이면 $1<\gcd(a,N)<N$, 즉 비자명 인수가 된다.
Step 2.
본 과정에서는 $N^2<Q=2^q<2N^2$인 $Q,q$에 대해 $q+n$개의 큐비트를 이용한다. 이중 $q$개의 큐비트는 함수 $f$의 값이 동일한 입력이 충분하도록 $\frac{Q}{r}>N$을 보장하기 위해서이며, $n$개의 큐비트는 함수값을 계산하는 과정에서 이용한다.
Step 2는 다음과 같이 세분화할 수 있다.
- Hadamard 게이트를 이용하여 0부터 Q-1까지의 모든 수가 동등한 비율로 존재하는 중첩 상태를 만든다.
$$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x\rangle = \left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_0\right)\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_1\right)\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_2\right)\otimes\cdots\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_{q-1}\right)$$ - 함수 $f$를 양자게이트로 구현한 연산 $U_f$를 적용한다. ($U_f(\vert x\rangle)=\vert a^x\mod N\rangle$)
이는 지수인 $x$를 이진 전개하면 $a^x=a^{\sum x_i\times 2^i}=\prod a^{x_i\times2^i}$과 같이 식을 변형할 수 있으므로 $t$번째 비트(0-based)가 1인 $\vert x\rangle$을 $\vert a^t x \mod N\rangle$로 바꿔주는 conditional multiplication을 이용하여 구현할 수 있다.
$$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,0^n\rangle\Rightarrow \frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,f(x)\rangle$$ - Quantum Fourier Transform을 적용한다.
$$w=e^{\frac{2\pi i}{Q}}$$
$$QFT = \begin{bmatrix}1&1&1&\cdots&1\\1&w&w^2&\cdots&w^{Q-1}\\1&w^2&w^4&\cdots&w^{Q-2}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&w^{Q-1}&w^{Q-2}&\cdots&w\end{bmatrix}$$
$$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,f(x)\rangle\Rightarrow \frac{1}{Q}\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1} w^{xy}\vert y,f(x)\rangle$$
이를 $f(x)$의 값을 기준으로 묶어 다시 쓰면
$$\frac{1}{Q}\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1} w^{xy}\vert y,f(x)\rangle\Rightarrow \frac{1}{Q}\sum_{y=0}^{Q-1}\sum_{z=0}^{Q-1}\left(\sum_{f(x)=z}w^{xy}\right)\vert y,z\rangle$$
집합 $\{x\vert f(x)=z\}$는 최솟값 $x_0$과 $x_0+kr$ ($k\in\mathbb{N}$)으로 구성된다. 즉, $\sum_{f(x)=z}w^{xy}$는 등비가 $w^{ry}$인 등비수열이다. $m=\left\lceil\frac{Q-x_0-1}{r}\right\rceil$로 정의하면 다음과 같이 $\vert y,z\rangle$이 관측될 확률을 계산할 수 있다.
$$\begin{align}\Pr(\vert y,z\rangle) &= \frac{1}{Q}\left\vert\frac{w^{mry}-1}{w^{ry}-1}\right\vert^2 = \frac{1}{Q}\left\vert\frac{\cos\left(\frac{2\pi mry}{Q}\right)-1+i\sin\left(\frac{2\pi mry}{Q}\right)}{\cos\left(\frac{2\pi ry}{Q}\right)-1+i\sin\left(\frac{2\pi ry}{Q}\right)}\right\vert^2\\ &= \frac{1}{Q}\left\vert\frac{2-2\cos\left(\frac{2\pi mry}{Q}\right)}{2-2\cos\left(\frac{2\pi ry}{Q}\right)}\right\vert = \frac{1}{Q}\left\vert\frac{4\sin^2\left(\frac{\pi mry}{Q}\right)}{4\sin^2\left(\frac{\pi ry}{Q}\right)}\right\vert \\&=\frac{1}{Q}\left\vert\frac{\sin\left(\frac{\pi mry}{Q}\right)}{\sin\left(\frac{\pi ry}{Q}\right)}\right\vert^2 \end{align}$$ - 위 확률은 $\frac{ry}{Q}$가 정수에 가까울 수록 다른 경우에 비해 극단적으로 값이 커지는 경향을 보인다. 따라서 우리는 그러한 $y$를 구할 수 있다. 이때 $\frac{ry}{Q}\approx c\in\mathbb{Z}$라 하자. $\frac{y}{Q}$는 알려진 값이며, $\frac{c}{r}$의 근사치이다. 따라서, $\frac{y}{Q}$를 연분수 전개(continued fraction expansion)하면 $\frac{c}{r}$의 좋은 근사값을 여럿 얻을 수 있으며, 높은 확률로 정확한 $r$의 값을 얻을 수 있다.
Step 3.
$r$이 홀수라면 Step 4를 진행할 수 없고, $a^{r/2}\equiv -1\text{ }(\text{mod }N)$이면 비자명 인수를 얻을 수 없으므로 알고리즘을 다시 실행한다. 그러할 확률은 크지 않아 알고리즘을 재실행하는 횟수는 일반적으로 0회, 매우 높은 확률로 수 회 내로 성공한다.
Step 4.
$b=a^{r/2}\mod N$은 $\text{mod }N$에서의 1의 비자명한 제곱근이다. 이는 $b^2\equiv 1\text{ }(\text{mod }N)$을 의미하며, $b^2=kN+1$을 만족하는 $k\in\mathbb{Z}$가 존재한다. 따라서 $(b-1)(b+1)=kN$이므로, $\gcd(b-1,N)$과 $\gcd(b+1,N)$은 $N$의 비자명한 인수이다.
Part IV. Essence of Shor's Algorithm
쇼어 알고리즘을 자연수 $N$의 비자명한 인수를 찾는 알고리즘이라고 소개했지만, 가장 중요한 부분은 양자컴퓨터를 이용해 계산한 Step 2이다. $f(x)=a^x\mod N$의 특수한 성질을 쓴 것이 아니라, 그저 주기함수이며 양자 게이트로 구현 가능하다는 사실이 중요했다. 이는 바꿔말하자면, 그러한 함수들은 양자컴퓨터를 이용하여 빠르게 그 주기를 계산할 수 있다는 뜻이다. 이러한 방식은 다양하게 응용될 수 있으며, 군 등의 순환 구조를 핵심으로 하여 위수의 기밀성이 중요한 (양자 내성이 없는) 현대 암호가 취약할 수 있음을 알 수 있다. 실제로 RSA는 물론이거니와, 타원곡선에 대한 공격 또한 연구된 바 있다. 아직은 실질적인 공격이 가능한 만큼의 큐비트를 이용할 수 없지만, 머지 않은 미래에 가능해질 수 있다.
'ctf' 카테고리의 다른 글
| 2023 GoN Spring Qual writeup (0) | 2023.03.23 |
|---|---|
| 2022 Christmas CTF 후기 (0) | 2022.12.26 |
| Whitehat Contest 2022 본선 Crypto writeup (0) | 2022.12.04 |
| 2022 Fall GoN Open Qual CTF Write-up (0) | 2022.08.28 |
| Introduction and Proof of Baby-step Giant-step Algorithm (BSGS) (3) | 2022.08.13 |