제2장. 양자 병렬성과 초기 알고리즘

1장에서 우리는 큐빗의 중첩을 만드는 하다마드(H) 게이트와 얽힘을 만드는 CNOT 게이트를 배웠습니다. 양자 알고리즘의 놀라운 힘은 이 두 가지, 중첩(Superposition)과 간섭(Interference)을 결합하는 데서 나옵니다.

이 장에서는 양자 컴퓨터가 단 한 번의 연산으로 수많은 입력값을 동시에 계산하는 양자 병렬성(Quantum Parallelism)의 원리를 배웁니다. 그리고 이 병렬성을 이용해 고전 컴퓨터보다 명백히 빠른 최초의 알고리즘들—도이치-조사(Deutsch-Jozsa)와 사이먼(Simon) 알고리즘—을 탐구합니다. 이 알고리즘들은 그 자체로 유용하기보다는, 양자 컴퓨터가 ‘어떻게’ 고전 컴퓨터와 다르게 작동하는지 보여주는 핵심적인 개념 증명입니다.

1. 기본 개념 (Fundamental Concepts)

양자 병렬성 (Quantum Parallelism): \(n\)개의 큐빗이 하다마드(H) 게이트를 통과하면 \(2^n\)개의 모든 가능한 입력 상태(\(|00\dots 0\rangle\)부터 \(|11\dots 1\rangle\)까지)가 균등하게 중첩된 상태가 됩니다. \[H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} |x\rangle\] 만약 이 중첩 상태에 함수 \(f(x)\)를 계산하는 양자 연산(\(U_f\))을 단 한 번 적용하면, \(2^n\)개의 모든 \(f(x)\) 값이 동시에, 병렬적으로 계산되어 상태에 저장됩니다.
함수 계산과 오라클 (Function Evaluation & Oracle): 고전 함수 \(f(x)\)를 계산하는 양자 회로를 오라클(Oracle) 또는 블랙박스(\(U_f\))라고 부릅니다. 이 오라클은 입력 \(|x\rangle\)를 \(|f(x)\rangle\)로 바꾸는 것이 아니라, 별도의 출력 레지스터에 그 값을 더하는 방식으로(유니터리 성질 유지를 위해) 작동합니다. \[U_f : |x\rangle |y\rangle \mapsto |x\rangle |y \oplus f(x)\rangle\] (여기서 \(\oplus\)는 XOR, 즉 mod 2 덧셈입니다.)
위상 반동 (Phase Kickback): 양자 병렬성의 결과를 읽어내는 핵심 기술입니다. 만약 출력 레지스터를 \(|-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}}\) 상태로 준비하면, 함수 \(f(x)\)의 값은 출력 레지스터가 아닌 입력 레지스터의 위상(phase)으로 되돌아옵니다. \[U_f |x\rangle |-\rangle = (-1)^{f(x)} |x\rangle |-\rangle\]

상세 설명: 위상 반동은 왜 일어나는가? \(f(x)\)가 0 또는 1이라고 가정해 봅시다.
- If \(f(x)=0\): \(U_f |x\rangle |-\rangle = |x\rangle |y \oplus 0\rangle = |x\rangle |y\rangle\). \(|-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}} \implies \frac{|0\oplus 0\rangle - |1\oplus 0\rangle}{\sqrt{2}} = \frac{|0\rangle - |1\rangle}{\sqrt{2}} = |-\rangle\). 결과: \(|x\rangle |-\rangle \to |x\rangle |-\rangle\). (변화 없음 \(\implies (-1)^0\) 곱)
- If \(f(x)=1\): \(U_f |x\rangle |-\rangle = |x\rangle |y \oplus 1\rangle\). \(|-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}} \implies \frac{|0\oplus 1\rangle - |1\oplus 1\rangle}{\sqrt{2}} = \frac{|1\rangle - |0\rangle}{\sqrt{2}} = -|-\rangle\). 결과: \(|x\rangle |-\rangle \to -|x\rangle |-\rangle\). (전체 위상 반전 \(\implies (-1)^1\) 곱)
이 트릭을 통해 \(f(x)\)의 값이 \(|x\rangle\)의 계수에 ’표시’됩니다.
도이치-조사 문제 (Deutsch-Jozsa Problem): \(n\)비트 입력, 1비트 출력 함수 \(f: \{0,1\}^n \to \{0,1\}\)이 상수(constant)(모든 \(x\)에 대해 \(f(x)\)가 0 또는 1로 동일)이거나 균형(balanced)(전체 \(x\)의 절반은 \(f(x)=0\), 절반은 \(f(x)=1\))임이 보장될 때, 이 함수가 상수인지 균형인지 단 한 번의 오라클 호출로 알아내는 문제입니다. (고전적으로는 최악의 경우 \(2^{n-1}+1\)번 필요)

2. 기호 및 핵심 관계식

N-큐빗 하다마드 변환: \[H^{\otimes n} |0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} |x\rangle\]
오라클 \(U_f\) (Standard Oracle): \[U_f |x, y\rangle = |x, y \oplus f(x)\rangle\]
위상 오라클 (Phase Oracle): (위상 반동을 이용한 \(U_f\)의 등가적 표현) \[U_f \left( \frac{1}{\sqrt{2^n}}\sum_{x} |x\rangle \right) |-\rangle = \left( \frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{f(x)} |x\rangle \right) |-\rangle\]
도이치-조사 알고리즘의 최종 상태: 알고리즘(H \(\to U_f \to\) H) 적용 후, 입력 레지스터의 최종 상태 \(|\psi_f\rangle\)는 다음과 같습니다. \[|\psi_f\rangle = \frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1} \left[ \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} (-1)^{f(x) \oplus x \cdot y} \right] |y\rangle\] (여기서 \(x \cdot y\)는 비트별 내적(dot product)입니다.)

3. 손쉬운 예제 (Examples with Deeper Insight)

예제 1: 도이치 알고리즘 (n=1)

문제: \(f: \{0,1\} \to \{0,1\}\) (1비트 함수)가 상수(\(f(0)=f(1)\))인지 균형(\(f(0)\neq f(1)\))인지 단 한 번의 오라클 호출로 판별하시오.
회로: \(|0\rangle \longrightarrow [H] \longrightarrow |\quad| \longrightarrow [H] \longrightarrow \text{측정}\) \(|1\rangle \longrightarrow [H] \longrightarrow |U_f| \longrightarrow [ ] \longrightarrow\)
계산 (단계별):
1. 초기 상태: \(|\psi_0\rangle = |01\rangle\)
2. H 게이트 적용: \(|\psi_1\rangle = (H|0\rangle) \otimes (H|1\rangle) = |+\rangle \otimes |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\) \(= \frac{1}{2}(|0\rangle(|0\rangle-|1\rangle) + |1\rangle(|0\rangle-|1\rangle))\)
3. 오라클 \(U_f\) 적용 (위상 반동): \(|\psi_2\rangle = \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right) \otimes |-\rangle\)
4. 마지막 H 게이트 적용 (입력 레지스터에만): \(|\psi_3\rangle = \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}H|0\rangle + (-1)^{f(1)}H|1\rangle \right) \otimes |-\rangle\) \(= \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}\frac{|0\rangle+|1\rangle}{\sqrt{2}} + (-1)^{f(1)}\frac{|0\rangle-|1\rangle}{\sqrt{2}} \right) \otimes |-\rangle\) \(= \frac{1}{2} \left( [(-1)^{f(0)} + (-1)^{f(1)}] |0\rangle + [(-1)^{f(0)} - (-1)^{f(1)}] |1\rangle \right) \otimes |-\rangle\)
5. 측정 (첫 번째 큐빗):
💡 상세 설명 (경우의 수 분석):
- Case 1: \(f\)가 상수 (Constant) \(f(0) = f(1)\) 이므로 \((-1)^{f(0)} = (-1)^{f(1)}\). \(|\psi_3\rangle = \frac{1}{2} ( [\pm 2] |0\rangle + [0] |1\rangle ) \otimes |-\rangle = \pm |0\rangle \otimes |-\rangle\). 첫 번째 큐빗을 측정하면 항상 \(|0\rangle\)이 나옵니다.
- Case 2: \(f\)가 균형 (Balanced) \(f(0) \neq f(1)\) 이므로 \((-1)^{f(0)} = -(-1)^{f(1)}\). \(|\psi_3\rangle = \frac{1}{2} ( [0] |0\rangle + [\pm 2] |1\rangle ) \otimes |-\rangle = \pm |1\rangle \otimes |-\rangle\). 첫 번째 큐빗을 측정하면 항상 \(|1\rangle\)이 나옵니다.
결론: 우리는 \(2^n=2\)개의 \(f(x)\) 값을 단 한 번의 오라클 호출로 계산(병렬성)한 뒤, H 게이트를 이용한 간섭(interference)을 통해 최종적으로 \(|0\rangle\) 또는 \(|1\rangle\)이라는 단일한 답으로 수렴시켰습니다.

예제 2: 도이치-조사 알고리즘 (n-bit)

상황: n-bit 함수 \(f\)가 상수이거나 균형일 때, \(n\)개의 H 게이트 \(\to U_f \to n\)개의 H 게이트를 적용합니다.
최종 상태 분석: \(|\psi_f\rangle = \frac{1}{\sqrt{2^n}}\sum_{y} \left[ \frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{f(x) \oplus x \cdot y} \right] |y\rangle\) 우리는 첫 번째 큐빗이 아닌, 전체 입력 레지스터를 측정합니다.
측정 결과 ( \(y=|00\dots 0\rangle\) 상태의 진폭): \(y=0\) 이면 \(x \cdot y = 0\) 입니다. \(y=0\) 상태(\(|0\rangle^{\otimes n}\))의 진폭 \(C_0\)는 \(C_0 = \frac{1}{2^n} \sum_{x} (-1)^{f(x)}\)
💡 상세 설명 (경우의 수 분석):
- Case 1: \(f\)가 상수 (Constant) 모든 \(f(x)\)가 0 또는 1로 같습니다. \(C_0 = \frac{1}{2^n} \sum_{x} (\pm 1) = \frac{1}{2^n} (2^n \cdot (\pm 1)) = \pm 1\). \(|0\rangle^{\otimes n}\) 상태를 측정할 확률 \(P_0 = |C_0|^2 = 1\) 입니다. 측정 결과는 항상 \(|00\dots 0\rangle\) 입니다.
- Case 2: \(f\)가 균형 (Balanced) \(f(x)=0\)인 \(x\)가 \(2^{n-1}\)개, \(f(x)=1\)인 \(x\)가 \(2^{n-1}\)개 있습니다. \(C_0 = \frac{1}{2^n} ( (2^{n-1} \cdot 1) + (2^{n-1} \cdot (-1)) ) = 0\). \(|0\rangle^{\otimes n}\) 상태를 측정할 확률 \(P_0 = |C_0|^2 = 0\) 입니다. 측정 결과는 절대로 \(|00\dots 0\rangle\)이 아닙니다. (다른 상태가 나옴)
결론: 단 한 번의 측정을 수행하여, 결과가 \(|00\dots 0\rangle\)이면 함수는 상수이고, 그 외의 것이면 균형입니다. 고전적으로 \(2^{n-1}+1\)번 필요한 일을 단 1번 만에 해결했습니다.

예제 3: 사이먼 알고리즘 (Simon’s Algorithm)

문제: \(n\)비트 함수 \(f(x)\)가, 어떤 숨겨진 비트열 \(s \neq 0\)에 대해 \(f(x) = f(y) \iff y = x \oplus s\) (XOR 관계)를 만족합니다. \(s\)를 찾으십시오.
알고리즘: 도이치-조사와 유사하게 H \(\to U_f \to\) H를 적용합니다.
핵심 결과: 측정 결과로 나오는 비트열 \(y\)는 항상 \(s \cdot y = 0 \pmod 2\) (숨겨진 \(s\)와 직교)를 만족하는 값만 나옵니다.
💡 상세 설명 (쇼어 알고리즘의 영감):

고전적으로는 \(s\)를 찾기 위해 \(x\)를 무작위로 뽑아 \(f(x)\)가 같은 쌍을 찾아야 하므로 지수적 시간이 걸립니다. 양자 컴퓨터는 H \(\to U_f \to\) H 과정을 \(n-1\)번 반복하여, \(s \cdot y_1 = 0, s \cdot y_2 = 0, \dots, s \cdot y_{n-1} = 0\) 를 만족하는 \(n-1\)개의 독립적인 \(y_k\) 값들을 얻습니다. 이는 \(s\)에 대한 \(n-1\)개의 선형 연립방정식을 푸는 것과 같으며, \(s\)를 유일하게 결정할 수 있습니다. (고전적 후처리) 사이먼 알고리즘은 도이치-조사보다 더 실용적인 문제(주기 찾기)를 다루며, 이는 4장에서 배울 쇼어의 소인수분해 알고리즘의 핵심 아이디어에 직접적인 영감을 주었습니다.

4. 연습문제

위상 반동 증명: \(U_f |x\rangle |+\rangle\) (\(|+\rangle = \frac{|0\rangle+|1\rangle}{\sqrt{2}}\))를 계산하고, 이 경우 위상 반동이 일어나지 않음을 보이십시오.
도이치 알고리즘 (수동 계산): \(f(x)\)가 \(f(0)=1, f(1)=1\) (상수)인 경우, 예제 1의 \(|\psi_3\rangle\)를 단계별로 계산하여 최종적으로 \(|0\rangle\) 상태가 나옴을 확인하십시오.
오라클 설계 (n=2): \(f(x_1 x_0) = x_1\) (입력 2비트 중 첫 번째 비트만 반환)인 함수가 있습니다. 이 오라클 \(U_f\)를 CNOT과 같은 기본 게이트로 어떻게 구현할 수 있을지 회로를 그려보십시오.
사이먼 알고리즘 (n=2): \(n=2\)이고 숨겨진 \(s=11\)이라고 가정합시다. (즉, \(f(00)=f(11), f(01)=f(10)\)). 알고리즘을 1회 실행했을 때 측정될 수 있는 \(y\) 값은 무엇이며, 그 이유는 무엇입니까?

5. 해설

\(U_f |x\rangle |+\rangle = |x\rangle |y \oplus f(x)\rangle\).
- \(f(x)=0\): \(|x\rangle \frac{|0\oplus 0\rangle + |1\oplus 0\rangle}{\sqrt{2}} = |x\rangle |+\rangle\).
- \(f(x)=1\): \(|x\rangle \frac{|0\oplus 1\rangle + |1\oplus 1\rangle}{\sqrt{2}} = |x\rangle \frac{|1\rangle + |0\rangle}{\sqrt{2}} = |x\rangle |+\rangle\). 두 경우 모두 동일한 \(|x\rangle |+\rangle\)가 나옵니다. 위상이 반전되지 않습니다.
\(f(0)=1, f(1)=1 \implies (-1)^{f(0)}=-1, (-1)^{f(1)}=-1\). \(|\psi_3\rangle = \frac{1}{2} ( [(-1) + (-1)] |0\rangle + [(-1) - (-1)] |1\rangle ) \otimes |-\rangle\) \(= \frac{1}{2} ( [-2] |0\rangle + [0] |1\rangle ) \otimes |-\rangle = -|0\rangle \otimes |-\rangle\). 첫 번째 큐빗 측정 시 (전역 위상 무시) \(|0\rangle\)을 100% 확률로 얻습니다.
입력 \(|x_1 x_0\rangle\), 출력 \(|y\rangle\). \(U_f |x_1 x_0, y\rangle = |x_1 x_0, y \oplus x_1\rangle\). 이는 \(x_1\)이 제어 큐빗, \(y\)가 대상 큐빗인 CNOT 게이트입니다. \(x_0\)는 아무런 게이트에도 연결되지 않습니다. 회로: \(x_1 \to \bullet \to\) \(x_0 \to \text{----} \to\) \(y \to \oplus \to\)
측정 결과 \(y=y_1 y_0\)는 \(s \cdot y = 0 \pmod 2\) 를 만족해야 합니다. \(s=11\) 이므로, \(s \cdot y = (1 \cdot y_1) \oplus (1 \cdot y_0) = y_1 \oplus y_0 = 0 \pmod 2\) 입니다. \(y_1 \oplus y_0 = 0\) 인 경우는 \(y_1=y_0\)인 경우, 즉 \(y=00\) 또는 \(y=11\) 입니다. 따라서 측정될 수 있는 값은 \(|00\rangle\) 또는 \(|11\rangle\) 뿐입니다.