Deutsch-Jozsa 알고리즘 — 단 한 번의 오라클 평가로 함수 판별

개념 소개

함수 $f:\{0,1{\}}^n\to \{0,1\}$가 다음 두 종류 중 하나임이 보장될 때, 어느 쪽인지 판별하는 문제를 생각한다.

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

고전 결정론적 알고리즘은 최악의 경우 $2^{n-1}+1$번의 함수 평가가 필요하다. 입력이 100비트라면 $2^{99}+1$번을 평가해야 확실한 답을 얻는다. Deutsch-Jozsa 알고리즘은 이를 단 1번으로 해결한다.

---

핵심 원리

오라클과 위상 반전(Phase Kickback)

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

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

보조 큐비트(ancilla)를 $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$로 준비하면 위상 반전이 일어난다.

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

$f(x)=0$이면 위상 변화 없음, $f(x)=1$이면 전역 위상에 $-1$이 붙는다. 오라클의 정보가 보조 큐비트가 아닌 질의 큐비트의 위상으로 옮겨지는 것이 핵심이다.

알고리즘 단계

1단계 – 초기화

$n$개 질의 큐비트를 $|0{⟩}^{\otimes n}$, 보조 큐비트를 $|1⟩$로 설정한다.

2단계 – Hadamard 변환

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

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

3단계 – 오라클 적용

위상 반전에 의해 각 기저 상태에 $(-1{)}^{f(x)}$가 붙는다.

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

4단계 – 두 번째 Hadamard 변환 및 측정

질의 큐비트에 $H^{\otimes n}$을 다시 적용하면, $|0{⟩}^{\otimes n}$ 상태의 진폭은 다음과 같다.

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

• $f$가 상수 함수이면 모든 항의 부호가 동일하므로 $|{\alpha }_{0\cdots 0}|=1$ → 측정 시 반드시 $|0{⟩}^{\otimes n}$
• $f$가 균형 함수이면 양의 항과 음의 항이 정확히 상쇄되어 ${\alpha }_{0\cdots 0}=0$ → $|0{⟩}^{\otimes n}$이 측정될 확률 0

따라서 질의 큐비트를 측정하여 모두 0이면 상수 함수, 하나라도 1이면 균형 함수로 단 한 번에 확정 판별한다.

---

예시·응용

n=2 균형 함수 직접 계산

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

오라클 적용 후 질의 큐비트 상태:

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

두 번째 Hadamard 후 $|00⟩$ 진폭:

$$\frac{1}{4}(1-1-1+1)=0$$

측정 결과는 절대 $|00⟩$이 아니므로 균형 함수로 판별된다.

Qiskit 구현

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

def deutsch_jozsa(n: int, oracle: str = 'balanced') -> QuantumCircuit:
    qc = QuantumCircuit(n + 1, n)

    # 보조 큐비트를 |1⟩로 초기화
    qc.x(n)

    # 전체 Hadamard
    qc.h(range(n + 1))

    # 오라클 구현
    if oracle == 'balanced':
        for i in range(n):
            qc.cx(i, n)          # 각 질의 큐비트 → 보조 큐비트 CNOT
    elif oracle == 'constant_1':
        qc.x(n)                  # 상수 1: 보조 큐비트에 X 게이트
    # constant_0: 아무것도 하지 않음

    # 질의 큐비트에 다시 Hadamard
    qc.h(range(n))

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

qc = deutsch_jozsa(n=3, oracle='balanced')
print(qc.draw('text'))
# 측정 결과가 000 이외이면 → 균형 함수

실용적 의의

Deutsch-Jozsa 알고리즘이 해결하는 문제 자체는 실용성이 높지 않다. 그러나 중첩을 통한 병렬 평가 → 위상에 정보 인코딩 → 간섭으로 정보 추출이라는 구조는 Bernstein-Vazirani 알고리즘, Simon 알고리즘, Grover 탐색 알고리즘 등 이후 양자 알고리즘들의 공통 설계 원형이다.

---

정리

Deutsch-Jozsa 알고리즘은 중첩(superposition)과 양자 간섭(interference), 그리고 위상 반전(phase kickback)이라는 세 가지 원리를 결합해 고전 대비 지수적 질의 복잡도 이점을 달성한다. 결과가 확률적이 아니라 **확정적(deterministic)**이라는 점에서 단순한 통계적 우위와 구분되며, 오라클 기반 양자 알고리즘 이론의 출발점으로서 역사적·교육적 가치가 크다.