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

개념 소개

다음 문제를 생각해 보자. 함수 $f:\{0,1{\}}^n\to \{0,1\}$가 주어질 때, 이 함수가 상수 함수(constant, 모든 입력에 대해 0 또는 1만 출력)인지 균형 함수(balanced, 정확히 절반의 입력에서 0, 나머지 절반에서 1 출력)인지 판별하라. 단, 두 경우 중 하나임은 사전에 보장된다.

고전 컴퓨터로는 최악의 경우 $2^{n-1}+1$번 평가해야 확실한 답을 얻는다. 반면 Deutsch-Jozsa 알고리즘은 단 한 번의 양자 오라클 호출로 이를 해결한다. $n=1$인 특수 경우는 David Deutsch가 먼저 제시한 Deutsch 알고리즘이며, Richard Jozsa와 함께 일반적인 $n$비트 버전으로 확장되었다.

---

핵심 원리

위상 반동(Phase Kickback)

알고리즘은 $n$개의 입력 큐비트와 1개의 보조(ancilla) 큐비트를 사용한다. 양자 오라클 $U_f$는 다음과 같이 정의된다.

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

보조 큐비트를 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$로 준비하면,

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

함수 값 $f(x)$가 보조 큐비트가 아니라 입력 큐비트의 전역 위상에 새겨진다. 이것이 위상 반동이다.

알고리즘 순서

1단계 초기화: $|0{⟩}^{\otimes n}|1⟩$

2단계 전체 큐비트에 아다마르(H) 게이트 적용:

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

3단계 오라클 $U_f$ 적용 → 위상 반동:

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

4단계 입력 레지스터에만 $H^{\otimes n}$ 재적용

5단계 입력 레지스터 측정 → $|00\cdots 0⟩$이면 상수, 그 외이면 균형

간섭이 판별하는 이유

$H^{\otimes n}$의 기저 변환 공식은 다음과 같다.

$$H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}\sum _{z\in \{0,1{\}}^n}(-1{)}^{x\cdot z}|z⟩$$

두 번째 아다마르 후 $|0{⟩}^{\otimes n}$ 상태의 진폭은

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

• 상수 함수: 모든 항의 부호가 동일하므로 합산 = $\pm 1$ → $|0\cdots 0⟩$ 측정 확률 = 1
• 균형 함수: $+1$ 항과 $-1$ 항이 정확히 절반씩이므로 합산 = 0 → $|0\cdots 0⟩$ 측정 확률 = 0

즉 양자 간섭이 두 경우를 완벽하게 분리한다.

---

예시·응용

n = 1 (Deutsch 알고리즘)

가능한 함수는 네 가지다. $f(x)=0$, $f(x)=1$은 상수 함수, $f(x)=x$, $f(x)=1\oplus x$는 균형 함수다. 고전 방식으로는 $f(0)$과 $f(1)$을 모두 평가해야 하지만, 양자 알고리즘은 한 번으로 충분하다.

Qiskit 구조 예시

from qiskit import QuantumCircuit

def deutsch_jozsa_circuit(oracle_gate, n):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)                   # 보조 큐비트 |1⟩ 초기화
    qc.h(range(n + 1))        # 전체 H 게이트
    qc.append(oracle_gate, range(n + 1))  # 오라클
    qc.h(range(n))            # 입력 레지스터 H 게이트
    qc.measure(range(n), range(n))
    return qc

# 측정 결과가 '000...0' → 상수 함수
# 하나라도 1이 있으면 → 균형 함수

의의와 한계

이 알고리즘은 쿼리 복잡도 측면에서 양자 우위를 수학적으로 엄밀히 증명한 첫 사례 중 하나다. 그러나 함수가 상수 또는 균형 중 하나라는 사전 보장이 필요하며, 그 조건이 없는 일반적 판별 문제에는 직접 적용되지 않는다. 핵심 기법인 위상 반동과 간섭을 통한 분류는 Simon 알고리즘, Bernstein-Vazirani 알고리즘, Shor 알고리즘으로 이어지는 중요한 출발점이다.

---

정리

Deutsch-Jozsa 알고리즘은 아다마르 변환이 만드는 균등 중첩, 위상 반동으로 함수 값을 위상에 인코딩하는 과정, 그리고 두 번째 아다마르에 의한 양자 간섭을 하나의 흐름으로 엮어낸다. 지수적 고전 쿼리를 단 하나의 양자 쿼리로 대체한다는 사실은 오늘날에도 양자컴퓨팅의 본질적 가능성을 설명할 때 가장 먼저 소개되는 결과다.