Deutsch-Jozsa 알고리즘 — 단 한 번의 오라클 호출로 판별하기

개념 소개

다음 문제를 생각하자. 함수 $f:\{0,1{\}}^n\to \{0,1\}$가 블랙박스(오라클) 형태로 주어졌을 때, 이 함수가 **상수 함수(constant function)**인지 **균형 함수(balanced function)**인지 판별하라.

• 상수 함수: 입력에 무관하게 출력이 항상 0이거나 항상 1이다.
• 균형 함수: 정확히 절반의 입력에 대해 0, 나머지 절반에 대해 1을 출력한다.

함수의 내부 구조는 알 수 없고 오직 입출력을 통해서만 접근할 수 있다. 고전적으로 최악의 경우 $2^{n-1}+1$번 평가해야 확실한 결론을 낼 수 있다. 예를 들어 $n=3$이면 최대 5회가 필요하다. Deutsch-Jozsa 알고리즘은 이 문제를 단 한 번의 오라클 호출로 해결한다.

---

핵심 원리

알고리즘은 $n$개의 입력 레지스터 큐비트와 1개의 보조 큐비트로 구성된다.

알고리즘 단계

초기 상태 준비

$$|{\psi }_0⟩=|0{⟩}^{\otimes n}|1⟩$$

1단계: 균등 중첩 생성

모든 큐비트에 아다마르(Hadamard) 게이트를 적용한다.

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

2단계: 오라클 적용

오라클 $U_f$는 $|x⟩|y⟩\mapsto |x⟩|y\oplus f(x)⟩$로 정의된다. 보조 큐비트가 $\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태일 때 위상 되차기(phase kickback) 현상이 일어난다.

$$U_f|x⟩\frac{|0⟩-|1⟩}{\sqrt{2}}=(-1{)}^{f(x)}|x⟩\frac{|0⟩-|1⟩}{\sqrt{2}}$$

오라클 적용 후 입력 레지스터는 다음 상태가 된다.

$$|{\psi }_2⟩=\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}|x⟩$$

3단계: 두 번째 아다마르 변환

입력 레지스터에 다시 $H^{\otimes n}$을 적용하면:

$$|{\psi }_3⟩=\sum _{z=0}^{2^n-1}\left[\frac{1}{2^n}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)+x\cdot z}\right]|z⟩$$

여기서 $x\cdot z=x_1{z}_1\oplus \cdots \oplus x_n{z}_n$는 비트 내적이다.

판별 기준

$|00\cdots 0⟩$ 상태의 진폭은 $z=0$을 대입하면:

$${\alpha }_0=\frac{1}{2^n}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}$$

• 상수 함수이면: 모든 항의 부호가 동일하므로 $|{\alpha }_0|=1$. 측정 결과는 반드시 $|00\cdots 0⟩$이다.
• 균형 함수이면: 양수 항과 음수 항이 정확히 상쇄되어 ${\alpha }_0=0$. $|00\cdots 0⟩$이 측정될 확률이 0이다.

따라서 측정 결과가 모두 0이면 상수 함수, 하나라도 1이 있으면 균형 함수로 결정된다.

---

예시·응용

$n=1$: Deutsch 알고리즘

$f:\{0,1\}\to \{0,1\}$의 경우 균형 함수 $f(x)=x$는 CNOT 게이트로 구현된다. 아래 Qiskit 코드는 이 경우를 시뮬레이션한다.

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

qc = QuantumCircuit(2, 1)  # 큐비트 0: 입력, 큐비트 1: 보조

qc.x(1)       # 보조 큐비트 |1⟩ 초기화
qc.h(0)       # 입력 레지스터 H 게이트
qc.h(1)       # 보조 큐비트 H 게이트

# 오라클: f(x)=x (균형 함수) → CNOT
qc.cx(0, 1)

qc.h(0)       # 두 번째 H 게이트
qc.measure(0, 0)

sim = AerSimulator()
result = sim.run(transpile(qc, sim), shots=1024).result()
print(result.get_counts())
# 출력: {'1': 1024}  → 균형 함수

오라클을 항등(아무 게이트 없음)으로 교체하면 출력은 {'0': 1024}가 되어 상수 함수임을 알 수 있다.

알고리즘의 위치와 의의

Deutsch-Jozsa 문제 자체의 실용적 중요성은 크지 않다. 그러나 이 알고리즘은 중첩 → 오라클 위상 인코딩 → 간섭에 의한 전역 성질 추출이라는 구조를 최초로 명확히 보여주었다. 이 구조는 이후 Simon 알고리즘, 양자 푸리에 변환, Shor 알고리즘 등 실용적 양자 알고리즘의 공통 뼈대가 된다.

---

정리

Deutsch-Jozsa 알고리즘의 핵심은 두 가지 양자 현상의 협력이다. 위상 되차기는 $f(x)$의 정보를 진폭의 위상으로 인코딩하고, 양자 간섭은 두 번째 아다마르 변환에서 전역적 성질(상수/균형)에 따라 진폭을 선택적으로 강화하거나 소거한다. 고전적으로 $2^{n-1}+1$번 필요한 평가를 단 한 번으로 줄이는 이 과정은, 양자 병렬성이 단순히 "여러 계산을 동시에 수행"하는 것이 아니라 간섭을 통해 유용한 정보를 추출하는 과정임을 보여준다.