Deutsch-Jozsa 알고리즘 — 단 한 번의 오라클 평가

개념 소개

$f:\{0,1{\}}^n\to \{0,1\}$인 함수가 블랙박스(오라클)로 주어진다고 하자. 이 함수는 다음 두 유형 중 하나임이 보장된다.

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

고전 결정론적 알고리즘은 최악의 경우 $2^{n-1}+1$번 오라클을 호출해야 한다. 앞서 $2^{n-1}$번을 모두 같은 값으로 받아도, 마지막 한 번을 더 호출하기 전까지는 상수 함수인지 확신할 수 없기 때문이다. Deutsch-Jozsa 알고리즘은 이를 단 한 번의 오라클 호출로 해결한다.

---

핵심 원리

알고리즘은 $n$개의 데이터 큐비트와 1개의 보조(ancilla) 큐비트를 사용한다.

초기 상태

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

1단계: 전체 아다마르 변환

모든 큐비트에 아다마르 게이트 $H$를 적용한다.

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

데이터 큐비트는 가능한 모든 입력의 균등 중첩이 되고, 보조 큐비트는 $|-⟩$ 상태가 된다.

2단계: 오라클 $U_f$ 적용 (위상 반전)

오라클은 위상 반전(phase kickback) 방식으로 동작한다.

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

함수값 $f(x)$가 진폭의 위상으로 인코딩된다.

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

3단계: 데이터 큐비트에 아다마르 재적용

아다마르 변환의 일반식 $H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}{\sum }_z(-1{)}^{x\cdot z}|z⟩$을 이용하면, 최종 상태에서 $|0{⟩}^{\otimes n}$의 진폭은 다음과 같다.

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

• $f$가 상수 함수이면: 모든 항의 부호가 같아 $|{\alpha }_0{|}^2=1$
• $f$가 균형 함수이면: 양수 항과 음수 항이 정확히 상쇄되어 $|{\alpha }_0{|}^2=0$

4단계: 측정

데이터 큐비트를 계산 기저로 측정한다. 모두 $|0⟩$이면 상수 함수, 그렇지 않으면 균형 함수다.

---

예시·응용

Qiskit 구현 예시

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

def deutsch_jozsa_circuit(oracle, n):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)               # 보조 큐비트 |1⟩ 초기화
    qc.h(range(n + 1))    # 전체 아다마르
    qc.compose(oracle, inplace=True)  # 오라클
    qc.h(range(n))        # 데이터 큐비트 아다마르 재적용
    qc.measure(range(n), range(n))
    return qc

# 균형 오라클 예시: f(x) = x_0 (CNOT 하나)
n = 3
balanced_oracle = QuantumCircuit(n + 1)
balanced_oracle.cx(0, n)

qc = deutsch_jozsa_circuit(balanced_oracle, n)
sim = AerSimulator()
counts = sim.run(transpile(qc, sim), shots=1).result().get_counts()
print(counts)  # 예: {'001': 1}  → 000이 아니므로 균형 함수

고전 vs 양자 오라클 호출 횟수

알고리즘	최선	최악
고전 결정론적	2회	$2^{n-1}+1$회
고전 확률론적	O(1)	O(1) (오류 허용 시)
Deutsch-Jozsa	1회	1회

이론적 의의

이 알고리즘의 실용적 응용은 제한적이나, 양자 병렬성(모든 입력을 동시에 탐색)과 간섭(불필요한 정보의 소거)이 결합될 때 고전 대비 지수적 이점이 생긴다는 것을 최초로 형식적으로 증명했다. 이후 Simon 알고리즘, Shor 알고리즘 등 실용적 양자 알고리즘의 구조적 토대가 됐다.

---

정리

Deutsch-Jozsa 알고리즘의 핵심 흐름은 세 단계로 요약된다: 아다마르 변환으로 모든 입력을 중첩 상태에 올리고, 오라클이 함수값을 위상으로 인코딩하며, 다시 아다마르 변환을 적용해 간섭으로 함수의 전역 성질을 한 번에 읽어낸다. 위상 반전 → 간섭 → 측정이라는 이 패턴은 이후 등장하는 수많은 양자 알고리즘에서 반복적으로 나타나는 핵심 구조다.