Deutsch-Jozsa 알고리즘 — 단 한 번의 평가로 결정하기

개념 소개

동전 $2^n$개가 앞면 또는 뒷면을 보이고 있다고 하자. 규칙은 두 가지뿐이다. 모든 동전이 같은 면을 보이거나(상수), 정확히 절반은 앞면이고 절반은 뒷면이다(균형). 최악의 경우 고전적으로는 $2^{n-1}+1$번을 확인해야 확신할 수 있다. Deutsch-Jozsa 알고리즘은 이 문제를 단 한 번의 오라클 평가로 확정적으로 답한다.

형식적으로, $f:\{0,1{\}}^n\to \{0,1\}$이 주어질 때:

• 상수 함수(constant): 모든 입력에 대해 $f(x)=0$ 또는 $f(x)=1$
• 균형 함수(balanced): 정확히 절반의 입력에서 $f(x)=0$, 나머지에서 $f(x)=1$

핵심 원리

알고리즘은 $n+1$개의 큐비트를 사용한다. 입력 레지스터 $n$개는 $|0{⟩}^{\otimes n}$으로, 보조 큐비트는 $|1⟩$로 초기화한다.

1단계 — 중첩 생성

모든 큐비트에 Hadamard 게이트를 적용한다.

$$|0{⟩}^{\otimes n}|1⟩\stackrel{H^{\otimes n+1}}{\to }\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}|x⟩\otimes \frac{|0⟩-|1⟩}{\sqrt{2}}$$

2단계 — 오라클 적용 (위상 킥백)

오라클 $U_f$는 $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$로 정의된다. 보조 큐비트가 $\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태일 때 위상 킥백(phase kickback)이 발생한다.

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

$f(x)$의 값이 보조 큐비트의 비트를 뒤집는 대신 전체 진폭의 부호를 결정하게 된다.

3단계 — 간섭과 측정

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

$$\sum _{z\in \{0,1{\}}^n}\left(\frac{1}{2^n}\sum _x(-1{)}^{f(x)+x\cdot z}\right)|z⟩$$

$|z⟩=|0{⟩}^{\otimes n}$일 때의 진폭은 $\frac{1}{2^n}{\sum }_x(-1{)}^{f(x)}$이다.

• $f$가 상수이면: 모든 항의 부호가 같아 진폭 $=\pm 1$ → $|00\cdots 0⟩$이 반드시 측정됨
• $f$가 균형이면: 양의 항과 음의 항이 상쇄되어 진폭 $=0$ → $|00\cdots 0⟩$은 절대 측정되지 않음

따라서 입력 레지스터를 한 번 측정하는 것으로 결정이 완료된다.

예시·응용

아래는 Qiskit을 이용한 $n=3$ 균형 함수(첫 큐비트에 CNOT 오라클) 구현 예시다.

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

n = 3
qc = QuantumCircuit(n + 1, n)

# 초기화
qc.x(n)                  # 보조 큐비트 |1⟩
qc.h(range(n + 1))       # H^{⊗n+1}

# 오라클: 첫 번째 큐비트에 의존하는 균형 함수
qc.cx(0, n)

# 역 Hadamard
qc.h(range(n))

# 측정
qc.measure(range(n), range(n))

sampler = StatevectorSampler()
result = sampler.run([qc], shots=1024).result()
print(result[0].data.c.get_counts())
# 출력: {'001': 1024} — 0 이외의 결과 → 균형 함수 확정

실용적 의의: Deutsch-Jozsa 알고리즘 자체는 인위적인 문제를 다루지만, 여기서 사용된 위상 킥백과 Hadamard 간섭 기법은 Bernstein-Vazirani 알고리즘, Simon 알고리즘, 나아가 Shor 알고리즘의 핵심 구성 요소다.

정리

Deutsch-Jozsa 알고리즘은 양자 중첩으로 모든 입력을 동시에 인코딩하고, 오라클을 통해 함수 정보를 위상으로 변환한 뒤, Hadamard 간섭으로 답을 단일 측정 결과에 집중시킨다. 고전 결정론적 알고리즘 대비 지수적 쿼리 감소를 엄밀히 보장하는 이 구조는 이후 모든 양자 알고리즘 설계의 원형이 된다.