Deutsch-Jozsa 알고리즘 — 단 한 번의 평가로 함수의 성질 판별

개념 소개

다음 상황을 상상해 보자. 블랙박스 함수 $f:\{0,1{\}}^n\to \{0,1\}$ 가 있고, 이 함수는 반드시 두 가지 중 하나임이 보장된다.

• 상수 함수(constant): 모든 입력에 대해 출력이 0 또는 1로 동일
• 균형 함수(balanced): 정확히 절반의 입력에서 0, 나머지 절반에서 1을 출력

고전적으로 이를 확실하게 판별하려면 최악의 경우 $2^{n-1}+1$번 함수를 호출해야 한다. $n=100$이면 이미 천문학적인 수다. Deutsch-Jozsa 알고리즘은 단 1번의 오라클 호출로 이를 결정한다.

---

핵심 원리

오라클과 위상 반동

함수 $f$는 유니타리 오라클 $U_f$로 구현된다.

$$U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$$

보조 큐비트(ancilla)를 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태로 준비하면, 오라클 적용 후 전체 상태는

$$U_f|x⟩|-⟩=(-1{)}^{f(x)}|x⟩|-⟩$$

가 된다. 함수의 출력값이 보조 큐비트 대신 위상으로 전이되는 이 현상이 위상 반동이다.

알고리즘 회로

초기 상태 $|0{⟩}^{\otimes n}|1⟩$에서 출발한다.

① 하다마르 변환 적용

$$H^{\otimes n}|0{⟩}^{\otimes n}\otimes H|1⟩=\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}|x⟩\otimes |-⟩$$

② 오라클 $U_f$ 적용

$$\frac{1}{\sqrt{2^n}}\sum _x(-1{)}^{f(x)}|x⟩\otimes |-⟩$$

③ 첫 번째 레지스터에 다시 $H^{\otimes n}$ 적용

$$H^{\otimes n}\left(\frac{1}{\sqrt{2^n}}\sum _x(-1{)}^{f(x)}|x⟩\right)=\sum _z\left(\frac{1}{2^n}\sum _x(-1{)}^{f(x)+x\cdot z}\right)|z⟩$$

④ 측정

$|0{⟩}^{\otimes n}$이 관측될 확률은

$$P(0^n)={\left|\frac{1}{2^n}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}\right|}^2$$

• 상수 함수: 모든 $(-1{)}^{f(x)}$ 가 동일 → 합이 $\pm 2^n$ → $P(0^n)=1$
• 균형 함수: 절반은 $+1$, 절반은 $-1$ → 합이 $0$ → $P(0^n)=0$

따라서 $|0{⟩}^{\otimes n}$이 관측되면 상수, 그 외 결과면 균형 함수로 판별한다.

---

예시·응용

n=2, 균형 함수 예시

$f(00)=0,f(01)=1,f(10)=1,f(11)=0$ 이면 균형 함수다.

오라클 적용 후 첫 번째 레지스터 상태:

$$\frac{1}{2}(|00⟩-|01⟩-|10⟩+|11⟩)$$

이 상태에 $H^{\otimes 2}$를 적용하면 $|11⟩$ 만 남아, 측정 결과는 $11$이 된다 — $00$이 아니므로 균형 함수 판별 성공.

Qiskit 구현 예시

from qiskit import QuantumCircuit

def deutsch_jozsa_balanced(n=2):
    qc = QuantumCircuit(n + 1, n)
    # 초기화: 보조 큐비트를 |1⟩로
    qc.x(n)
    qc.h(range(n + 1))

    # 균형 오라클 예시: CNOT으로 f(x) = x_0 XOR x_1 구현
    qc.cx(0, n)
    qc.cx(1, n)

    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

qc = deutsch_jozsa_balanced()
print(qc.draw())

측정 결과가 00이 아닌 값이 나오면 균형 함수, 00이면 상수 함수임을 알 수 있다.

의의

Deutsch-Jozsa 알고리즘은 실용적 문제 해결보다 원리적 중요성이 크다. 양자 중첩이 지수적 병렬성을 제공함을 최초로 엄밀하게 증명했으며, 이후 Shor 알고리즘, Grover 알고리즘의 토대가 되는 오라클 기반 설계 패러다임을 확립했다.

---

정리

Deutsch-Jozsa 알고리즘의 핵심은 중첩으로 모든 입력을 동시에 탐색하고, 위상 반동으로 함수 정보를 위상에 인코딩한 뒤, 하다마르 변환으로 전역적 성질을 단일 측정 결과에 집결시키는 데 있다. 고전 최악의 경우 지수 쿼리 대 양자 1 쿼리라는 이 지수적 분리(exponential separation)는 양자 우위의 가장 깔끔한 이론적 시연이다.