양자컴퓨팅의 수학 (Mathematics of Quantum Computing)
양자컴퓨터(Quantum Computer)는 "더 빠른 컴퓨터"이기만 한 기계가 아닙니다. 상태를 표현하는 방식부터 다릅니다. 보통 컴퓨터가 0과 1을 분명히 구분된 상태로 저장한다면, 양자컴퓨터는 복소수(Complex Number) 계수를 가진 벡터로 상태를 표현하고, 계산은 행렬 곱셈으로, 관측은 확률로 해석합니다.
그래서 양자컴퓨팅을 이해하려면 회로도만 보는 것으로는 부족합니다. 선형대수학, 확률론, 조화해석학, 암호학의 수학이 서로 어떻게 연결되는지 함께 보아야 합니다. 이 페이지에서는 그중에서도 가장 핵심적인 수학 골격만 골라 차례대로 정리합니다.
- 큐비트: 0과 1이 아니라 복소 2차원 벡터로 상태를 표현하는 방식을 봅니다.
- 측정: 확률진폭(Probability Amplitude)이 어떻게 실제 확률이 되는지 봅니다.
- 유니터리 게이트: 양자 게이트가 왜 길이와 내적을 보존하는 행렬이어야 하는지 봅니다.
- 텐서곱과 얽힘: 여러 큐비트가 합쳐질 때 상태 공간이 어떻게 커지는지 봅니다.
- 양자 푸리에 변환: 위상이 간섭을 일으켜 정보를 드러내는 방식을 봅니다.
- 쇼어와 그로버: 대표 알고리즘이 어떤 수학을 쓰는지 큰 그림으로 봅니다.
왜 양자컴퓨팅에 수학이 필요합니까
양자컴퓨팅에서는 계산이 "상태를 조금씩 바꾸는 과정"이 아니라, 상태 벡터 전체를 선형 변환으로 옮기는 과정으로 표현됩니다. 이때 상태를 저장하는 공간은 복소 벡터 공간이고, 계산 규칙은 유니터리 행렬이며, 측정 결과는 내적과 확률 규칙으로 읽습니다. 즉, 하드웨어보다 먼저 수학적 모델이 필요합니다.
클래식 비트는 어느 순간에 0 아니면 1입니다. 반면 큐비트는 "$0$ 성분"과 "$1$ 성분"을 동시에 가지는 벡터로 적습니다. 물론 측정하면 0 또는 1 하나만 나오지만, 측정 전 계산 과정에서는 두 성분이 함께 움직이며 서로 간섭합니다. 이 차이를 가장 정확히 다루는 언어가 선형대수학입니다.
- 암호 해독: 쇼어 알고리즘은 소인수분해와 이산 로그를 주기 찾기 문제로 바꾸고, 여기에 양자 푸리에 변환을 사용합니다.
- 탐색: 그로버 알고리즘은 상태 공간 안에서 특정 방향의 진폭을 반복적으로 키웁니다.
- 물리 시뮬레이션: 분자와 재료의 양자 상태는 원래부터 복소 힐베르트 공간에 살기 때문에, 양자계 시뮬레이션과 수학 구조가 자연스럽게 맞닿습니다.
- 오차 보정: 양자 오류는 단순한 비트 뒤집기만이 아니라 위상 변화까지 포함하므로, 선형대수적 부호 이론이 필요합니다.
난이도: ★★★★☆ (대학교 초중반 수준, 직관 위주로 읽을 수 있습니다)
큐비트는 복소 2차원 벡터입니다
큐비트(Qubit)는 양자컴퓨팅의 가장 기본적인 상태 단위입니다. 수학적으로는 복소수체 위의 2차원 벡터 공간 $\mathbb{C}^2$의 단위 벡터로 표현합니다. 먼저 계산 기준이 되는 두 기저 상태를 다음과 같이 둡니다.
$$|0\rangle = \begin{pmatrix}1\\0\end{pmatrix}, \qquad |1\rangle = \begin{pmatrix}0\\1\end{pmatrix}$$그러면 임의의 큐비트 상태는
$$|\psi\rangle = \alpha |0\rangle + \beta |1\rangle = \begin{pmatrix}\alpha\\\beta\end{pmatrix}, \qquad \alpha,\beta \in \mathbb{C}$$처럼 씁니다. 여기서 $\alpha$, $\beta$는 단순한 확률이 아니라 확률진폭(Probability Amplitude)입니다. 실제 확률이 되려면 다음 정규화 조건을 만족해야 합니다.
$$|\alpha|^2 + |\beta|^2 = 1$$클래식 비트는 "지금 0" 또는 "지금 1"이라고만 적으면 됩니다. 큐비트는 두 기저 상태에 대한 가중치 두 개를 함께 적어야 합니다. 그래서 기억해야 할 정보량도 단순한 0/1보다 훨씬 풍부합니다.
| 대상 | 상태 표현 | 가능한 계산 |
|---|---|---|
| 클래식 비트 | 0 또는 1 | 논리 게이트로 상태를 바꿈 |
| 큐비트 | $\alpha |0\rangle + \beta |1\rangle$ | 유니터리 행렬로 상태 벡터를 바꿈 |
예를 들어
$$|+\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$$은 0과 1이 똑같은 비중으로 섞인 상태입니다. 하지만 이것을 "반은 0, 반은 1"이라고만 이해하면 부족합니다. 진폭은 복소수이므로 크기뿐 아니라 위상(Phase)도 들어 있으며, 이 위상이 뒤에서 간섭을 만들어 냅니다.
실수만으로는 위상 차이에서 오는 간섭을 충분히 표현하기 어렵습니다. 양자계에서는 $+1$과 $-1$뿐 아니라 $i$와 같은 허수 위상도 실제 계산 결과에 영향을 줍니다. 그래서 양자컴퓨팅의 상태 공간은 보통 $\mathbb{R}^2$가 아니라 $\mathbb{C}^2$로 잡습니다.
위상과 블로흐 구: 한 큐비트를 더 정확히 보기
한 큐비트를 더 자세히 이해하려면 정규화뿐 아니라 위상(Phase)도 함께 봐야 합니다. 특히 양자 상태에서는 "전체에 같은 복소수 위상을 곱한 것"과 "두 성분 사이의 상대적인 위상 차이"를 구분하는 것이 중요합니다.
전체 위상과 상대 위상
$|\psi\rangle$에 $e^{i\theta}$를 곱해도
$$|e^{i\theta}\alpha|^2 + |e^{i\theta}\beta|^2 = |\alpha|^2 + |\beta|^2$$이므로 측정 확률은 바뀌지 않습니다. 그래서 $|\psi\rangle$와 $e^{i\theta}|\psi\rangle$는 물리적으로 같은 상태로 봅니다. 이를 전체 위상(Global Phase)이라고 합니다.
반면 두 성분 사이의 부호나 위상 차이는 실제로 중요합니다. 예를 들어
$$\frac{|0\rangle + |1\rangle}{\sqrt{2}}, \qquad \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$은 계산 기저에서 측정하면 둘 다 0과 1이 반반 나오지만, 다른 기저에서 보면 완전히 다른 상태입니다. 이런 차이를 만드는 것이 상대 위상(Relative Phase)입니다.
| 비교 | 예시 | 물리적으로 같은가 |
|---|---|---|
| 전체 위상 | $|0\rangle$ 와 $i|0\rangle$ | 같습니다 |
| 상대 위상 | $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$ 와 $\frac{|0\rangle - |1\rangle}{\sqrt{2}}$ | 다릅니다 |
전체 위상은 모든 성분이 함께 같은 만큼 회전한 것이어서 서로의 관계가 바뀌지 않습니다. 하지만 상대 위상은 성분들 사이의 "엇갈림"을 바꾸므로, 뒤에서 게이트를 한 번 더 적용했을 때 더해질지 상쇄될지가 달라집니다. 간섭은 바로 이 상대 위상에 민감합니다.
블로흐 구 (Bloch Sphere)의 직관
정규화된 한 큐비트 상태는 보통
$$|\psi\rangle = \cos\frac{\theta}{2}|0\rangle + e^{i\phi}\sin\frac{\theta}{2}|1\rangle$$처럼 적습니다. 여기서 $\theta$는 0과 1의 "섞임 비율"을, $\phi$는 두 성분 사이의 상대 위상을 나타냅니다. 이 두 각도로 한 큐비트 상태를 구 위의 한 점으로 나타낸 그림이 블로흐 구(Bloch Sphere)입니다.
- 북극: $|0\rangle$
- 남극: $|1\rangle$
- 적도: 0과 1이 반반 섞인 상태들
- 적도 위의 각도: 상대 위상이 어떻게 달라지는지 보여 줌
중첩과 측정: 확률진폭과 보른 규칙
중첩(Superposition)이란 상태가 여러 기저 상태의 선형결합으로 주어지는 것을 말합니다. 하지만 우리가 기계에서 직접 읽는 값은 벡터 그 자체가 아니라 측정(Measurement) 결과입니다. 이때 실제 확률을 정하는 규칙이 보른 규칙(Born Rule)입니다.
$$P(0) = |\alpha|^2, \qquad P(1) = |\beta|^2$$즉, 진폭의 절댓값 제곱이 확률이 됩니다. 예를 들어
$$|\psi\rangle = \frac{\sqrt{3}}{2}|0\rangle + \frac{1}{2}|1\rangle$$이면
$$P(0) = \left|\frac{\sqrt{3}}{2}\right|^2 = \frac{3}{4}, \qquad P(1) = \left|\frac{1}{2}\right|^2 = \frac{1}{4}$$입니다. 따라서 이 상태를 여러 번 준비하고 측정하면, 평균적으로 4번 중 3번은 0, 4번 중 1번은 1이 나옵니다.
측정을 한 뒤에는 상태가 결과에 맞는 기저 상태로 바뀝니다. 0이 나왔으면 상태는 $|0\rangle$로, 1이 나왔으면 상태는 $|1\rangle$로 바뀝니다. 이를 흔히 상태 붕괴(State Collapse)라고 부릅니다.
$\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$와 $\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$는 계산 기준에서 측정하면 둘 다 0과 1이 반반 나옵니다. 즉, 같은 확률 분포를 가집니다. 그러나 뒤에 다른 게이트를 한 번 더 붙이면 결과가 달라질 수 있습니다. 이는 부호와 위상이 진폭 안에 남아 있기 때문입니다.
측정 기준이 바뀌면 결과도 바뀝니다
측정은 단순히 "상태를 읽는다"가 아니라, 어떤 기저(Basis)에서 읽느냐를 먼저 정하는 과정입니다. 가장 익숙한 것은 계산 기저 $\{|0\rangle, |1\rangle\}$에서의 측정이지만, 다른 기저를 써도 됩니다.
예를 들어 다음 두 상태를 생각합시다.
$$|+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}, \qquad |-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$이 둘은 $X$ 기저라고 부르는 새로운 기준을 이룹니다. 이제 상태 $|+\rangle$를 어떻게 측정하느냐에 따라 결과가 달라집니다.
| 측정 기준 | $|+\rangle$의 해석 | 결과 |
|---|---|---|
| 계산 기저 $\{|0\rangle, |1\rangle\}$ | $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$ | 0과 1이 각각 1/2 |
| $X$ 기저 $\{|+\rangle, |-\rangle\}$ | $|+\rangle$ 자체 | 항상 $|+\rangle$ |
같은 상태라도 어떤 축에서 보느냐에 따라 "기저 벡터 하나"로 보일 수도 있고, "중첩"으로 보일 수도 있습니다. 그래서 양자 게이트는 종종 상태를 바꾸는 동시에 측정하기 좋은 기준으로 회전시키는 역할을 합니다.
양자 게이트: 유니터리 행렬과 기저 변화
양자 게이트(Quantum Gate)는 큐비트 상태를 바꾸는 선형 변환입니다. 그러나 아무 행렬이나 쓸 수 있는 것은 아닙니다. 확률의 총합이 항상 1이어야 하므로, 길이를 보존하는 행렬이어야 합니다. 이런 행렬을 유니터리 행렬(Unitary Matrix)이라고 합니다.
$$U^\dagger U = I$$여기서 $U^\dagger$는 켤레전치(Conjugate Transpose)입니다. 유니터리 행렬은 벡터의 길이를 보존하므로 정규화 조건이 깨지지 않습니다. 실수 벡터 공간의 직교행렬이 복소 벡터 공간으로 확장된 것이라고 생각하면 이해가 쉽습니다.
대표적인 한 큐비트 게이트는 다음과 같습니다.
$$X = \begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad Z = \begin{pmatrix}1&0\\0&-1\end{pmatrix}, \qquad H = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$$- $X$ 게이트: $|0\rangle$와 $|1\rangle$를 서로 바꿉니다. 클래식 NOT과 비슷합니다.
- $Z$ 게이트: 1 상태에만 부호를 바꿉니다. 값은 그대로지만 위상을 바꿉니다.
- $H$ 게이트: 기저 상태를 균등한 중첩으로 바꿉니다. 간섭을 만드는 출발점으로 자주 등장합니다.
$H$ 게이트를 실제로 계산하면
$$H|0\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix} = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$$ $$H|1\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\-1\end{pmatrix} = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$이처럼 양자 회로는 사실상 상태 벡터에 행렬을 차례로 곱하는 과정입니다. 여러 게이트를 잇달아 적용하면 행렬의 곱으로 한꺼번에 표현할 수 있습니다.
$H$ 게이트는 단순히 값을 뒤섞는 연산이 아니라, 계산 기준을 바꾸는 역할을 합니다. 어떤 상태는 계산 기저에서 보면 복잡한 중첩이지만, 다른 기저에서는 단순한 기저 벡터일 수 있습니다. 이 관점은 기저 변환과 정확히 연결됩니다.
두 큐비트 게이트: CNOT과 벨 상태 만들기
한 큐비트 게이트만으로는 각 큐비트를 따로따로 바꾸는 일만 할 수 있습니다. 얽힘을 만들려면 여러 큐비트를 연결하는 두 큐비트 게이트(Two-Qubit Gate)가 필요합니다. 가장 대표적인 것이 CNOT 게이트입니다.
CNOT는 첫 번째 큐비트를 제어 비트(Control), 두 번째 큐비트를 표적 비트(Target)로 삼습니다. 제어 비트가 0이면 아무 일도 하지 않고, 제어 비트가 1이면 표적 비트를 뒤집습니다.
$$\mathrm{CNOT}|00\rangle = |00\rangle,\quad \mathrm{CNOT}|01\rangle = |01\rangle,\quad \mathrm{CNOT}|10\rangle = |11\rangle,\quad \mathrm{CNOT}|11\rangle = |10\rangle$$이 게이트 하나만으로는 특별해 보이지 않을 수 있지만, 하다마드 게이트와 합치면 얽힘을 직접 만들 수 있습니다.
- 처음 상태를 $|00\rangle$로 둡니다.
- 첫째 큐비트에 하다마드 게이트를 걸면 $\frac{|00\rangle + |10\rangle}{\sqrt{2}}$가 됩니다.
- 이 상태에 CNOT를 걸면 $\frac{|00\rangle + |11\rangle}{\sqrt{2}}$가 됩니다.
즉, "중첩 만들기"와 "조건부 뒤집기"를 결합하면 얽힘이 만들어집니다. 이것이 양자 회로에서 가장 기본적인 패턴 가운데 하나입니다.
복합계와 얽힘: 텐서곱과 벨 상태
큐비트가 여러 개로 늘어나면 상태 공간은 덧셈이 아니라 텐서곱(Tensor Product)으로 커집니다. 한 큐비트의 상태 공간이 $\mathbb{C}^2$이면, 두 큐비트의 상태 공간은
$$\mathbb{C}^2 \otimes \mathbb{C}^2 = \mathbb{C}^4$$가 됩니다. 표준 기저는 다음 네 개입니다.
$$|00\rangle,\quad |01\rangle,\quad |10\rangle,\quad |11\rangle$$예를 들어 첫 번째 큐비트가 $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$이고 두 번째 큐비트가 $|0\rangle$이면
$$\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right)\otimes |0\rangle = \frac{|00\rangle + |10\rangle}{\sqrt{2}}$$이 됩니다. 이것은 각 큐비트를 따로 적을 수 있는 분리 가능 상태(Separable State)입니다.
하지만 모든 상태가 이렇게 쪼개지지는 않습니다. 대표적인 예가 벨 상태(Bell State)입니다.
$$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}}$$이 상태는 두 큐비트가 강하게 연결된 얽힘(Entanglement) 상태입니다. 한쪽을 측정해서 0이 나오면 다른 쪽도 0, 한쪽을 측정해서 1이 나오면 다른 쪽도 1이 나옵니다.
만약 $|\Phi^+\rangle$가 $(a|0\rangle + b|1\rangle)\otimes(c|0\rangle + d|1\rangle)$ 꼴이라면, 전개 결과는 $ac|00\rangle + ad|01\rangle + bc|10\rangle + bd|11\rangle$가 됩니다. 그런데 벨 상태에는 $|01\rangle$와 $|10\rangle$ 성분이 없으므로 $ad = 0$, $bc = 0$이어야 합니다. 동시에 $|00\rangle$와 $|11\rangle$ 성분은 모두 살아 있어야 하므로 $ac \neq 0$, $bd \neq 0$이어야 합니다. 이 네 조건은 함께 만족할 수 없습니다. 그래서 벨 상태는 분리 가능한 상태가 아닙니다.
간섭과 양자 푸리에 변환
양자 계산의 핵심은 단순한 병렬성보다 간섭(Interference)에 있습니다. 진폭이 더해질 때는 결과가 커지고, 부호가 반대이면 서로 상쇄됩니다. 원하는 답 쪽 진폭은 키우고, 원하지 않는 답 쪽 진폭은 줄이는 것이 양자 알고리즘의 기본 전략입니다.
가장 간단한 예는 하다마드 게이트를 두 번 적용하는 경우입니다.
$$H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}, \qquad H\!\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right) = |0\rangle$$두 번째 $H$에서 $|0\rangle$ 쪽 진폭은 더해지고, $|1\rangle$ 쪽 진폭은 상쇄됩니다. 이것이 간섭의 가장 기본적인 모습입니다.
위상이 어떻게 결과를 바꿉니까
위상은 눈에 바로 보이지 않아도, 기저를 한 번 더 바꾸면 실제 측정 결과로 나타납니다. 예를 들어
$$|0\rangle \xrightarrow{H} \frac{|0\rangle + |1\rangle}{\sqrt{2}} \xrightarrow{Z} \frac{|0\rangle - |1\rangle}{\sqrt{2}} \xrightarrow{H} |1\rangle$$가 됩니다. 중간 단계에서 $Z$ 게이트는 1 성분의 부호만 바꾸었을 뿐인데, 마지막 $H$ 이후에는 결과가 완전히 1 상태로 바뀝니다. 즉, 보이지 않던 상대 위상이 마지막 간섭에서 실제 출력으로 드러난 것입니다.
이 아이디어를 큰 상태 공간으로 확장한 것이 양자 푸리에 변환(Quantum Fourier Transform, QFT)입니다. $N$차원 계산 기저에서 QFT는 다음과 같이 정의됩니다.
$$\mathrm{QFT}_N |x\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i xk/N}|k\rangle$$이 식은 고전적 이산 푸리에 변환(Discrete Fourier Transform, DFT)과 같은 행렬을 사용하지만, 해석 방식은 다릅니다. 고전 DFT는 전체 계수를 모두 계산해 표로 꺼내 보려는 연산이고, QFT는 상태 벡터의 기저를 바꾸어 유용한 구조가 측정되기 쉬운 쪽으로 진폭을 재배열하는 연산입니다.
| 구분 | 고전 DFT | 양자 QFT |
|---|---|---|
| 입력 | 숫자 배열 | 진폭을 가진 상태 벡터 |
| 출력 해석 | 푸리에 계수 전체 | 기저가 바뀐 양자 상태 |
| 목표 | 스펙트럼을 직접 계산 | 간섭을 일으켜 원하는 정보를 측정 가능하게 만듦 |
특히 $N=2$인 경우에는 QFT가 하다마드 게이트와 같습니다. 즉, 한 큐비트의 하다마드 변환은 가장 작은 크기의 양자 푸리에 변환입니다.
QFT의 작은 예시: 주기 2가 어떻게 드러납니까
두 큐비트 공간, 즉 $N=4$인 경우를 봅시다. 다음 상태는 0과 2에서만 같은 간격으로 값이 살아 있으므로 "주기 2" 구조를 가진다고 볼 수 있습니다.
$$|\psi\rangle = \frac{|0\rangle + |2\rangle}{\sqrt{2}}$$이 상태에 $\mathrm{QFT}_4$를 적용하면, 계산해 보면 다시
$$\mathrm{QFT}_4 |\psi\rangle = \frac{|0\rangle + |2\rangle}{\sqrt{2}}$$가 됩니다. 중요한 점은, 주기 2의 구조가 특정 기저 성분에 집중되어 남는다는 것입니다. 실제 쇼어 알고리즘에서는 이 원리가 더 큰 상태 공간에서 작동하여, 모듈러 함수의 주기를 측정 가능한 형태로 바꾸어 줍니다.
QFT를 했다고 해서 고전 DFT처럼 모든 푸리에 계수를 한 번에 읽어 내는 것은 아닙니다. 측정은 한 번에 하나의 결과만 주기 때문입니다. QFT의 진짜 역할은, 주기나 위상 정보가 특정 결과에 집중되도록 상태를 재배열하는 것입니다.
쇼어와 그로버에서 어떤 수학이 쓰입니까
양자컴퓨팅의 대표 알고리즘을 보면, 지금까지 본 개념들이 실제로 어떻게 결합되는지 더 잘 보입니다.
| 알고리즘 | 핵심 수학 | 무슨 일을 합니까 |
|---|---|---|
| 쇼어 알고리즘 (Shor) | 모듈러 산술, 주기성, 복소 위상, 양자 푸리에 변환 | 소인수분해와 이산 로그를 주기 찾기로 바꿉니다. |
| 그로버 알고리즘 (Grover) | 내적, 반사, 2차원 부분공간에서의 회전 | 정답 상태의 진폭을 반복적으로 키웁니다. |
쇼어 알고리즘은 왜 암호학을 위협합니까
쇼어 알고리즘의 핵심은 소인수분해 자체를 정면으로 푸는 것이 아니라, 정수 $N$에 대해 함수
$$f(x) = a^x \bmod N$$의 주기(Period) $r$를 찾는 데 있습니다. 이 함수가 주기 $r$를 가지면 $a^r \equiv 1 \pmod{N}$이므로, 적절한 조건에서
$$\gcd(a^{r/2} - 1, N), \qquad \gcd(a^{r/2} + 1, N)$$를 계산하여 $N$의 인수를 얻을 수 있습니다. 여기서 결정적인 역할을 하는 것이 QFT입니다. QFT는 주기 구조를 진폭 패턴으로 바꾸어, 측정 결과가 주기를 드러내도록 만듭니다.
쇼어 알고리즘의 작은 예시: 15를 분해해 봅시다
$N=15$를 분해하고 싶다고 합시다. $a=2$를 택하면
$$2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 \equiv 8,\quad 2^4 \equiv 16 \equiv 1 \pmod{15}$$이므로 주기는 $r=4$입니다. 그러면
$$2^{r/2} = 2^2 = 4$$이어서
$$\gcd(4-1,15)=\gcd(3,15)=3,\qquad \gcd(4+1,15)=\gcd(5,15)=5$$를 얻습니다. 이렇게 15의 인수 3과 5가 나타납니다. 실제 쇼어 알고리즘의 어려운 부분은 바로 이 주기 $r$를 빠르게 찾는 단계이며, 양자 푸리에 변환이 그 핵심입니다.
그로버 알고리즘은 왜 기하학으로 설명됩니까
그로버 알고리즘은 모든 후보 상태를 균등한 중첩으로 시작한 뒤, 목표 상태의 부호를 뒤집는 오라클(Oracle)과 평균에 대한 반사인 확산 연산(Diffusion Operator)을 번갈아 적용합니다. 이 두 반사를 합치면, 상태 벡터가 "전체 평균 방향"과 "정답 방향"이 만드는 2차원 평면 안에서 조금씩 회전합니다.
그래서 그로버 알고리즘은 대수적으로는 행렬 곱이지만, 기하학적으로는 원하는 방향 쪽으로 상태를 회전시키는 과정이라고 이해할 수 있습니다. 고전 탐색이 평균적으로 $O(N)$번 확인해야 하는 문제를, 그로버 알고리즘은 약 $O(\sqrt{N})$번으로 줄입니다.
그로버 알고리즘의 작은 예시: 후보가 4개뿐이면
후보가 $|00\rangle, |01\rangle, |10\rangle, |11\rangle$ 네 개뿐이고, 정답이 $|10\rangle$라고 합시다. 시작 상태는
$$|s\rangle = \frac{|00\rangle + |01\rangle + |10\rangle + |11\rangle}{2}$$입니다. 여기서 오라클은 정답 상태의 부호만 뒤집습니다.
$$|s\rangle \longrightarrow \frac{|00\rangle + |01\rangle - |10\rangle + |11\rangle}{2}$$이제 평균에 대한 반사, 즉 확산 연산을 하면 세 개의 틀린 상태 진폭은 0이 되고 정답 상태 진폭은 1이 됩니다. 그래서 이 경우에는 단 한 번의 그로버 반복만으로
$$|10\rangle$$을 정확히 얻습니다. 이 예시는 그로버 알고리즘의 핵심이 "정답 쪽 진폭 키우기"라는 사실을 아주 선명하게 보여 줍니다.
쇼어는 주기와 푸리에 분석의 알고리즘이고, 그로버는 반사와 회전의 알고리즘입니다. 둘 다 결국 선형대수학의 언어로 아주 선명하게 설명됩니다.
자주 생기는 오해와 한계
양자컴퓨터를 처음 배울 때는 "모든 경우를 동시에 계산하니까 무조건 엄청 빠르다"라고 생각하기 쉽습니다. 하지만 실제로는 몇 가지 중요한 제약이 있습니다.
- 중첩만으로는 부족합니다. 상태가 여러 경우를 동시에 포함하더라도, 측정하면 하나의 결과만 나옵니다. 그래서 중첩을 그냥 많이 만드는 것만으로는 속도 향상이 생기지 않습니다.
- 간섭 설계가 핵심입니다. 원하는 답은 커지고 원하지 않는 답은 상쇄되도록 회로를 짜야 합니다. 이것이 양자 알고리즘 설계의 본질입니다.
- 모든 문제에 빠르지 않습니다. 쇼어나 그로버처럼 구조가 잘 맞는 문제에서는 큰 이득이 있지만, 임의의 문제에 자동으로 마법 같은 속도 향상이 생기는 것은 아닙니다.
- 오류에 약합니다. 실제 장치는 잡음과 오차에 민감하므로, 이론만큼 쉽게 계산되지 않습니다. 그래서 양자 오류 정정과 오차 보정이 매우 중요합니다.
"양자컴퓨터는 모든 답을 한 번에 계산하고, 그중 정답만 바로 꺼낸다"라고 말하면 정확하지 않습니다. 실제로는 모든 진폭이 한꺼번에 존재하지만, 측정은 하나만 꺼냅니다. 따라서 알고리즘은 정답이 나올 확률이 커지도록 진폭을 조정하는 과정이어야 합니다.
전체 정리와 다음 읽을거리
양자컴퓨팅의 수학은 하나의 공식을 외워서 끝나는 과목이 아닙니다. 상태를 벡터로 보고, 계산을 유니터리 변환으로 보고, 측정을 확률로 읽고, 여러 시스템을 텐서곱으로 묶고, 위상 정보를 푸리에 변환으로 꺼내 보는 큰 그림이 함께 있어야 합니다.
| 수학 개념 | 양자컴퓨팅에서 하는 일 | 함께 읽을 문서 |
|---|---|---|
| 복소 벡터와 내적 | 큐비트 상태, 정규화, 측정 확률의 바탕 | 선형대수학의 내적공간 |
| 유니터리 행렬 | 양자 게이트와 시간 발전을 표현 | 수리물리학의 양자역학 절 |
| 텐서곱 | 다중 큐비트 상태와 얽힘을 표현 | 선형대수학의 텐서곱 절 |
| 푸리에 변환 | 위상과 주기 정보를 간섭으로 읽음 | 조화해석학의 푸리에 변환 절 |
| 정수론과 암호학 | 쇼어 알고리즘의 의미와 양자 위협 이해 | 암호학의 수학 |
정리하면, 양자컴퓨팅의 핵심 수학은 "복소 벡터 공간 위의 확률적 계산"입니다. 큐비트는 벡터이고, 게이트는 유니터리 행렬이며, 측정은 내적에서 나오는 확률이고, 여러 큐비트는 텐서곱으로 묶이며, 강력한 알고리즘은 간섭과 푸리에 변환을 이용해 정보를 드러냅니다. 이 틀을 머릿속에 넣어 두면, 양자컴퓨터 관련 개념을 훨씬 덜 막연하게 이해할 수 있습니다.