Deutsch-Jozsa 알고리즘: 단 한 번의 평가로 함수 판별

개념 소개

어떤 블랙박스 함수 $f:\{0,1{\}}^n\to \{0,1\}$가 주어졌다. 이 함수는 반드시 두 경우 중 하나라고 약속(promise)되어 있다.

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

고전 컴퓨터는 최악의 경우 $2^{n-1}+1$번의 평가를 해야 확실한 답을 얻을 수 있다. $n=100$이라면 $2^{99}+1$번이 필요하다. Deutsch-Jozsa 알고리즘은 이를 단 한 번의 오라클 호출로 해결한다.

핵심 원리

오라클과 위상 킥백

양자 오라클 $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=0}^{2^n-1}|x⟩\otimes |-⟩$$

3단계 — 오라클 적용: 위상 킥백으로

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

4단계 — 하다마르 역변환: 입력 레지스터에 다시 $H^{\otimes n}$ 적용

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

여기서 $x\cdot z=x_1{z}_1\oplus \cdots \oplus x_n{z}_n$ (GF(2) 위의 비트 내적).

5단계 — 측정: $|0{⟩}^{\otimes n}$에 해당하는 진폭은

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

• $f$가 상수 함수: 모든 항의 부호가 같아 합 $=\pm 1$ → 반드시 $|0^n⟩$ 측정
• $f$가 균형 함수: 양·음 항이 정확히 상쇄되어 합 $=0$ → 절대 $|0^n⟩$ 측정 불가

측정 결과가 $0\cdots 0$이면 상수, 그렇지 않으면 균형 함수로 확정 판별된다.

예시·응용

n=1: Deutsch 알고리즘

$n=1$ 경우는 1985년 Deutsch가 처음 제안한 원형이다.

함수	$f(0)$	$f(1)$	종류
$f_1$	0	0	상수
$f_2$	1	1	상수
$f_3$	0	1	균형
$f_4$	1	0	균형

한 번의 오라클 호출 후 입력 큐비트를 측정하면, $|0⟩$ → 상수, $|1⟩$ → 균형이 나온다.

Qiskit 구현 (n=2, 균형 오라클)

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

def deutsch_jozsa_balanced(n=2):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)              # 보조 큐비트 |1⟩
    qc.h(range(n + 1))   # 전체 하다마르
    qc.barrier()
    # 균형 오라클: f(x) = x_0 (첫 비트에 CNOT)
    qc.cx(0, n)
    qc.barrier()
    qc.h(range(n))       # 입력 레지스터 하다마르
    qc.measure(range(n), range(n))
    return qc

qc = deutsch_jozsa_balanced(n=2)
sim = AerSimulator()
counts = sim.run(transpile(qc, sim), shots=1024).result().get_counts()
print(counts)  # '00'이 등장하지 않음 → 균형 함수 확인

의의와 한계

이 알고리즘은 실용적인 문제를 푼다기보다, 약속 조건(promise problem) 아래에서 양자 컴퓨팅의 지수적 질의 우위를 최초로 엄밀히 증명한 사례로 의미가 있다. 이후 Bernstein-Vazirani 알고리즘(숨겨진 문자열 탐색), Simon 알고리즘(숨겨진 주기 탐색)으로 이어지는 양자 질의 복잡도 이론의 출발점이 되었다.

정리

Deutsch-Jozsa 알고리즘의 성공은 두 가지 요소의 조합에서 비롯된다. 첫째, 위상 킥백을 통해 함수의 전역 정보(상수 vs. 균형)를 중첩 상태의 위상에 동시 인코딩한다. 둘째, 하다마르 역변환으로 위상 차이를 측정 가능한 진폭 차이로 변환하여 단 한 번의 측정으로 판별을 완료한다. 이 흐름—중첩 생성 → 오라클 위상 각인 → 간섭으로 읽어내기—은 이후 거의 모든 양자 알고리즘의 공통 설계 철학이 된다.