Deutsch-Jozsa 알고리즘 — 단 한 번의 오라클 호출로 판별하기

개념 소개

문제 설정: 함수 $f:\{0,1{\}}^n\to \{0,1\}$이 주어진다. 이 함수는 다음 둘 중 하나임이 보장된다.

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

고전 알고리즘이 최악의 경우 판별하려면 $2^{n-1}+1$번의 질의가 필요하다. 반면 Deutsch-Jozsa 알고리즘은 단 한 번의 오라클 호출로 확정적 답을 낸다.

핵심 아이디어는 두 가지다. 첫째, 모든 입력을 동시에 중첩 상태로 오라클에 넘긴다. 둘째, 위상 반발(phase kickback)로 함수 정보를 위상에 인코딩하고, Hadamard 변환을 통한 간섭으로 이를 읽어낸다.

핵심 원리

회로 구성

알고리즘은 $n+1$개 큐비트를 사용한다. 처음 $n$개는 입력 레지스터($|0{⟩}^{\otimes n}$), 마지막 1개는 보조 큐비트($|1⟩$)로 초기화한다.

단계 1 — 초기 상태: $$|{\psi }_0⟩=|0{⟩}^{\otimes n}|1⟩$$

단계 2 — Hadamard 전체 적용: $$|{\psi }_1⟩=\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}|x⟩\otimes \underset{|-⟩}{\underbrace{\frac{|0⟩-|1⟩}{\sqrt{2}}}}$$

단계 3 — 오라클 적용과 위상 반발:

오라클 $U_f$는 $|x⟩|y⟩\mapsto |x⟩|y\oplus f(x)⟩$로 정의된다. 보조 큐비트가 $|-⟩$일 때 이를 적용하면,

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

함수값이 전역 위상이 아닌 각 $|x⟩$ 항의 상대 위상으로 인코딩된다: $$|{\psi }_2⟩=\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}|x⟩\otimes |-⟩$$

단계 4 — 입력 레지스터에 Hadamard 재적용:

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

여기서 $x\cdot z=x_1{z}_1\oplus \cdots \oplus x_n{z}_n$은 비트 내적이다.

단계 5 — 측정:

$|z⟩=|0{⟩}^{\otimes n}$에서의 진폭은,

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

• $f$가 상수 함수이면 $|{\alpha }_0|=1$ → 측정 결과는 반드시 $|00\cdots 0⟩$
• $f$가 균형 함수이면 양수·음수 항이 정확히 상쇄되어 ${\alpha }_0=0$ → $|00\cdots 0⟩$은 절대 나오지 않음

즉, 측정값이 전부 0이면 상수 함수, 하나라도 1이 있으면 균형 함수다.

예시·응용

Qiskit 구현 예시 (n=2)

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

def deutsch_jozsa(n, balanced=True):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)                    # 보조 큐비트 |1⟩
    qc.h(range(n + 1))         # 전체 Hadamard
    qc.barrier()

    if balanced:
        for i in range(n):     # 균형 오라클 예시
            qc.cx(i, n)

    qc.barrier()
    qc.h(range(n))             # 입력 레지스터 Hadamard
    qc.measure(range(n), range(n))
    return qc

sim = AerSimulator()
for label, bal in [('상수', False), ('균형', True)]:
    qc = deutsch_jozsa(2, balanced=bal)
    counts = sim.run(transpile(qc, sim), shots=1).result().get_counts()
    print(f"{label} 함수 → {counts}")
# 상수 함수 → {'00': 1}
# 균형 함수 → {'11': 1}  (또는 '01', '10' 등 0 아닌 값)

이론적 의의

이 알고리즘은 실용적 문제를 직접 해결하기보다 양자 컴퓨터가 고전 컴퓨터보다 지수적으로 빠를 수 있음을 처음으로 명확히 증명한 이정표다. 이후 Simon 알고리즘, Shor 알고리즘, Grover 알고리즘 등 더 강력한 양자 알고리즘의 설계 원리로 이어진다.

정리

구분	고전 알고리즘	Deutsch-Jozsa
최악 질의 수	$2^{n-1}+1$	1
결과 유형	확정적	확정적
오류율	없음	없음

오라클 한 번으로 지수적 이점이 가능한 이유는 양자 병렬성(중첩으로 모든 입력을 동시 처리)과 간섭(Hadamard 변환이 상수·균형 정보를 측정 결과로 분리)이 결합하기 때문이다.