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

개념 소개

문제 정의: $n$비트 입력을 받는 함수 $f:\{0,1{\}}^n\to \{0,1\}$이 블랙박스(오라클)로 주어진다. 이 함수는 다음 두 경우 중 하나임이 보장된다.

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

어느 쪽인지 판별하는 것이 목표다. 고전 컴퓨터는 확실한 답을 얻으려면 최악의 경우 $2^{n-1}+1$번 질의해야 한다. Deutsch-Jozsa 알고리즘은 단 한 번의 오라클 호출로 확정적 답을 낸다.

---

핵심 원리

알고리즘은 $n$개의 입력 큐비트와 1개의 보조(ancilla) 큐비트, 총 $n+1$개를 사용한다.

1단계 — 초기 상태 준비

입력 레지스터는 $|0{⟩}^{\otimes n}$, 보조 큐비트는 $|1⟩$로 설정한다.

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

2단계 — Hadamard 변환

전체 큐비트에 Hadamard 게이트를 적용하면 입력 레지스터는 모든 $2^n$개 상태의 균일 중첩이 되고, 보조 큐비트는 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$가 된다.

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

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

오라클 $U_f$는 $|x⟩|y⟩\mapsto |x⟩|y\oplus f(x)⟩$로 정의된다. 보조 큐비트가 $|-⟩$일 때 위상 킥백(phase kickback) 현상으로 $f(x)$의 정보가 전역 위상 대신 상대 위상으로 인코딩된다.

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

4단계 — 두 번째 Hadamard 및 측정

입력 레지스터에 Hadamard를 재적용하면:

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

전부 0인 상태 $|0{⟩}^{\otimes n}$를 측정할 확률은 다음과 같다.

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

• 상수 함수: 모든 $(-1{)}^{f(x)}$의 부호가 같으므로 합은 $\pm 2^n$ → $P(0^n)=1$
• 균형 함수: 양수와 음수 항이 정확히 상쇄 → $P(0^n)=0$

측정 결과가 $0^n$이면 상수 함수, 그 외이면 균형 함수로 오류 없이 결론짓는다.

---

예시·응용

n=1: Deutsch 알고리즘

가장 단순한 특수 경우로, 2큐비트 회로로 $f(0)=f(1)$인지 아닌지를 한 번에 판별한다.

from qiskit import QuantumCircuit

def build_dj_circuit(oracle_circuit, n):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)           # 보조 큐비트 |1⟩ 초기화
    qc.h(range(n+1))  # 전체 Hadamard
    qc.compose(oracle_circuit, inplace=True)  # 오라클
    qc.h(range(n))    # 입력 레지스터에 Hadamard 재적용
    qc.measure(range(n), range(n))
    return qc

고급 알고리즘과의 연결

이 알고리즘의 구조—Hadamard → 오라클 → Hadamard → 측정—는 이후 Simon 알고리즘, Grover 알고리즘, Shor 알고리즘 설계의 원형이 된다. 위상 킥백과 간섭을 결합해 전역 함수 특성을 단번에 추출하는 방식은 양자 알고리즘 설계의 핵심 패턴이다.

단, Deutsch-Jozsa 문제 자체는 문제가 인위적으로 제한되어(상수/균형 보장) 실용적 쓸모는 크지 않다. 이 알고리즘의 의의는 양자 지수적 우위의 가능성을 최초로 엄밀하게 증명한 데 있다.

---

정리

Deutsch-Jozsa 알고리즘은 양자 중첩으로 $2^n$개 입력을 동시에 평가하고, 위상 킥백으로 함수 정보를 위상에 인코딩한 뒤, 간섭으로 원하는 답만 보강·상쇄하는 세 단계 구조를 갖는다. 이 흐름은 양자 알고리즘을 이해하는 핵심 골격이다.