Amplitudes interfere; that's the whole trick.
양자 컴퓨터가 빠른 건 "여러 경우를 동시에 계산해서"가 아닙니다. 진짜 비결은 복소수 진폭이 서로 간섭해 — 틀린 답은 상쇄되고 옳은 답만 살아남게 만드는 것이죠. 왜 양자엔 복소수가 자연스러운지, 브라켓 표기가 무엇인지, 단 한 번의 질문으로 답을 알아내는 도이치–조사, 원 위에서 각도를 돌려 답을 찾는 그로버, 그리고 RSA의 전제를 흔든 쇼어까지 따라가 봅니다.
고전 비트는 \(0\) 아니면 \(1\)입니다. 큐비트는 둘의 중첩이죠.
$$ \lvert\psi\rangle = \alpha\,\lvert 0\rangle + \beta\,\lvert 1\rangle $$여기서 \(\alpha,\beta\)는 복소수 진폭입니다. "동시에 0이면서 1"이라는 말은 비유일 뿐 — 정확히는 \(\lvert0\rangle\)과 \(\lvert1\rangle\)을 두 축으로 하는 벡터예요. 측정하면 중첩이 무너져 \(0\) 또는 \(1\) 하나만 나오고, 그 확률이 진폭의 크기 제곱입니다(보른 규칙): \(\Pr(0)=|\alpha|^2,\ \Pr(1)=|\beta|^2\). 확률을 다 더하면 \(1\)이어야 하니 \(|\alpha|^2+|\beta|^2=1\) — 즉 상태는 길이 \(1\)의 단위벡터입니다.
중첩의 진짜 힘은 여럿 모일 때 드러납니다. 큐비트 \(n\)개의 상태는 \(2^n\)개의 진폭을 한꺼번에 지닌 벡터예요. 큐비트 \(300\)개면 진폭의 개수가 우주의 원자 수보다 많습니다. 다만 함정이 있죠 — 측정하는 순간 이 방대한 중첩이 단 하나의 \(n\)비트 결과로 붕괴하고, 나머지는 영영 사라집니다. 그러니 "\(2^n\)가지를 동시에 계산"은 결코 공짜 점심이 아닙니다.
그럼 그 방대한 중첩을 어떻게 써먹을까요? 양자 컴퓨팅의 핵심은 이겁니다 — 양자의 기이한 성질(중첩·간섭· 얽힘)을 복소 선형대수로 정확히 모델링한 뒤, 그 중첩을 의도대로 조종하는 것. 모델은 놀랄 만큼 단정합니다: 상태는 \(2^n\)차원 복소공간의 단위벡터, 연산(양자 게이트)은 길이를 보존하는 유니터리 행렬, 측정은 보른 규칙.
알고리즘 설계자가 하는 일은, 유니터리 변환을 영리하게 엮어 틀린 답들의 진폭은 서로 상쇄(소멸 간섭)시키고 정답의 진폭은 키우는(보강 간섭) 것입니다. 그래야 마지막에 측정했을 때 정답이 높은 확률로 튀어나오죠. 모든 양자 알고리즘은 이 한 레시피의 변주입니다 — "병렬로 다 해본다"가 아니라 "간섭으로 답만 남긴다".
"확률이면 그냥 양수로 충분하지 않나?" 핵심은 간섭입니다. 확률은 더하기만 하니 절대 줄어들지 않지만, 진폭은 부호와 위상을 가져 서로 상쇄될 수 있습니다. 두 경로의 진폭이 \(+\tfrac1{\sqrt2}\)와 \(-\tfrac1{\sqrt2}\)로 만나면 합이 \(0\) — 그 결과는 절대 나타나지 않습니다. 파동이 마루와 골로 만나 사라지듯, 양자 계산은 틀린 답의 진폭을 상쇄시켜 옳은 답만 남기죠.
왜 하필 ‘복소’수일까요? 양자의 시간 발전은 확률(길이)을 보존하는 가역 변환 — 즉 유니터리 변환입니다. 길이를 보존하면서 위상을 자유롭게 돌리는 회전의 가장 자연스러운 무대가 바로 복소수예요(회전 \(e^{i\theta}\)). 실수만으로는 이 위상 회전과 간섭을 담을 수 없습니다.
디랙의 브라켓 표기는 사실 선형대수의 깔끔한 속기입니다. 켓 \(\lvert\psi\rangle\)은 열벡터, 브라 \(\langle\psi\rvert\)는 그 켤레전치(행벡터)예요.
$$ \lvert 0\rangle=\begin{pmatrix}1\\0\end{pmatrix},\quad \lvert 1\rangle=\begin{pmatrix}0\\1\end{pmatrix},\quad \langle\phi\vert\psi\rangle=\text{두 벡터의 내적} $$브라와 켓을 맞붙인 \(\langle\phi\vert\psi\rangle\)은 내적(브라+켓="브라켓")이고, 측정 확률은 \(\Pr(\phi)=\bigl|\langle\phi\vert\psi\rangle\bigr|^2\)로 단정하게 써집니다. 양자 게이트는 이 벡터에 작용하는 유니터리 행렬일 뿐이죠. 표기가 어려워 보여도, 속은 "단위벡터에 회전행렬을 곱한다"가 전부입니다.
가장 단순하면서 양자 우위를 또렷이 보여주는 문제입니다. 함수 \(f\)가 \(n\)비트 입력을 받아 \(0\) 또는 \(1\)을 내는데, \(f\)가 상수(모든 입력에 같은 값)이거나 균형(정확히 절반은 \(0\), 절반은 \(1\)) 둘 중 하나임이 보장돼 있습니다. 어느 쪽인지 알아내세요.
고전적으로는 최악의 경우 \(2^{n-1}+1\)번 \(f\)를 불러봐야 합니다(절반을 넘겨 봐야 확신하니까). 하지만 도이치–조사 알고리즘은 단 한 번의 질의로 끝냅니다. 모든 입력을 중첩에 실어 \(f\)를 한 번 적용하고, 위상 간섭으로 \(\lvert 00\cdots0\rangle\)의 진폭을 \(\tfrac{1}{2^n}\sum_x(-1)^{f(x)}\)로 만들죠 — 상수면 이 값이 \(\pm1\)이라 측정하면 반드시 전부 0, 균형이면 \(0\)이라 절대 전부 0이 안 나옵니다. 측정 한 번이 둘을 가릅니다. (\(n=1\)인 원조가 도이치 알고리즘: 2번을 1번으로.)
이번엔 숨은 \(n\)비트 문자열 \(s\)가 있고, 물어볼 수 있는 건 \(f(x)=s\cdot x \bmod 2\) (\(s\)와 \(x\)의 비트별 곱의 합)뿐입니다. \(s\)를 알아내세요. 고전적으로는 \(s\)의 비트를 하나씩 캐려고 \(e_1,e_2,\dots,e_n\)(한 자리만 \(1\)인 입력)을 넣어 \(n\)번 물어야 합니다.
번스타인–바지라니 알고리즘은 단 한 번의 질의로 \(s\) 전체를 끄집어냅니다. 아다마르 게이트로 균일 중첩을 만들고 \(f\)를 한 번 건 뒤 다시 아다마르하면 — 간섭이 정확히 정렬되어 — 측정 결과가 그대로 \(s\)예요. \(n\)비트짜리 숨은 비밀번호가 질문 한 번에 통째로 드러나는 셈이죠.
정렬되지 않은 \(N\)개 중 정답 하나를 찾는 문제. 고전적으로는 평균 \(N/2\)번 들춰봐야 하지만, 그로버 알고리즘은 \(\sqrt{N}\)번이면 됩니다. 비결이 기막히게 기하적이에요 — 상태를 ‘정답’ 축과 ‘나머지’ 축이 이루는 평면 위의 단위벡터로 보면, 매 단계가 그 벡터를 정답 축 쪽으로 일정 각도만큼 회전시키는 일이거든요.
처음 균일 중첩 상태는 정답 축에서 각도 \(\theta\)만큼 떨어져 있고(\(\sin\theta=1/\sqrt N\)), 한 번 반복할 때마다 \(2\theta\)씩 돌아갑니다. \(k\)번 후 정답이 측정될 확률은
$$ \Pr_{\text{정답}}(k)=\sin^2\!\bigl((2k+1)\theta\bigr) $$이 각도가 \(90^\circ\)에 닿을 때(약 \(\frac{\pi}{4}\sqrt N\)번) 확률이 최대가 됩니다. 너무 많이 돌리면 지나쳐(overshoot) 확률이 도로 떨어지죠. 아래에서 직접 돌려 보세요.
사이먼의 문제는 숨은 주기 \(s\)에 대해 \(f(x)=f(x\oplus s)\)인 \(2\)대 \(1\) 함수에서 \(s\)를 찾는 것입니다. 고전적으로는 충돌하는 두 입력을 찾을 때까지 지수적으로 많이 물어야 하지만, 사이먼 알고리즘은 다항 번이면 됩니다 — 역사상 처음으로 지수적 양자 우위를 보인 사례죠.
그리고 이 ‘숨은 주기 찾기’ 발상이 자라서, 다음다음 장의 쇼어 알고리즘이 됩니다. 도이치–조사가 ‘위상 간섭’을, 사이먼이 ‘주기 간섭’을 보여 줬다면, 쇼어는 그 주기 찾기를 정수론에 꽂아 RSA를 겨눕니다.
지금까지의 알고리즘이 위상 간섭을 ‘조금’ 썼다면, 양자 푸리에 변환(QFT)은 그 간섭을 가장 강력하게 휘두르는 도구입니다. 고전 푸리에 변환이 신호를 주파수 성분으로 분해해 반복되는 패턴(주기)을 봉우리로 드러내듯, QFT는 같은 분해를 양자 진폭에 적용하는 유니터리 변환이에요. 중첩 속에 숨은 주기·위상을 간섭으로 도드라지게 만들죠.
속도가 핵심입니다. 고전 FFT는 \(N=2^n\)개 데이터에 \(O(n\,2^n)\) 연산이 들지만, QFT는 \(O(n^2)\)개의 게이트면 됩니다 — 지수적으로 빠르게. (다만 결과가 중첩 속에 있어 통째로 읽진 못하고, 간섭으로 한 점을 뽑아내는 데 씁니다.) 이 QFT가 위상 추정의 심장이고, 위상 추정은 곧 주기 찾기 — 그래서 사이먼·이산로그, 그리고 다음 장의 쇼어 인수분해까지, 알려진 지수 가속 양자 알고리즘 대부분의 공통 엔진이 됩니다.
RSA의 안전은 "큰 수의 소인수분해는 어렵다"는 가정 하나에 걸려 있었죠. 1994년 피터 쇼어가 양자 컴퓨터라면 이걸 빠르게 깰 수 있음을 보입니다. 열쇠는 소인수분해를 주기 찾기로 바꾸는 것이었어요.
\(N\)과 서로소인 \(a\)를 골라 \(a^x \bmod N\)을 보면, 반드시 주기적입니다 — \(a^r\equiv 1 \pmod N\)이 되는 가장 작은 주기 \(r\)이 존재하죠. 이 \(r\)만 알면(그리고 \(r\)이 짝수면)
$$ \gcd\!\bigl(a^{r/2}-1,\ N\bigr),\quad \gcd\!\bigl(a^{r/2}+1,\ N\bigr) $$이 \(N\)의 진짜 약수가 됩니다. 문제는 주기 \(r\)을 찾는 일인데, 고전 컴퓨터엔 느리지만 — 양자 푸리에 변환이 간섭으로 주기를 단번에 드러냅니다. 아래는 그 핵심인 ‘주기 → 약수’ 단계를 직접 보는 것입니다(주기 찾기 자체가 양자가 빨리 하는 부분).
양자 컴퓨터의 힘은 "동시에 다 해본다"가 아니라, 복소수 진폭의 간섭으로 틀린 답을 지우는 데 있습니다. 그로버는 그 간섭을 원 위의 회전으로, 쇼어는 주기를 드러내는 공명으로 빚어냈죠. 추상적이던 복소수와 선형대수가, 암호의 운명까지 흔드는 알고리즘이 되어 돌아온 셈입니다.