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

개념 소개

함수 $f:\{0,1{\}}^n\to \{0,1\}$가 다음 두 경우 중 하나라는 보증이 주어진다고 하자.

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

고전 결정론적 알고리즘으로 판별하려면 최악의 경우 $2^{n-1}+1$번의 질의가 필요하다. 앞선 $2^{n-1}$번이 모두 같은 값을 반환해도, 그것이 상수인지 균형인지 확신할 수 없기 때문이다. Deutsch-Jozsa 알고리즘은 이 문제를 단 1회 오라클 호출로 결정론적으로 해결한다.

핵심 원리

알고리즘은 **위상 반동(phase kickback)**과 Hadamard 변환을 결합한다.

1단계 — 초기 상태 준비

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

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

모든 큐비트에 Hadamard 변환 $H$를 적용하면:

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

2단계 — 오라클 적용

오라클 $U_f$는 $|x⟩|y⟩\mapsto |x⟩|y\oplus f(x)⟩$으로 정의된다. 보조 큐비트가 $(|0⟩-|1⟩)/\sqrt{2}$ 상태일 때 위상 반동이 발생하여 $f(x)$의 정보가 위상으로 이전된다.

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

3단계 — 역 Hadamard와 측정

입력 레지스터에 다시 $H^{\otimes n}$을 적용하면:

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

$|0{⟩}^{\otimes n}$ 성분의 진폭은 $z=0$일 때:

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

• $f$가 상수 함수이면 합은 $\pm 1$ → $|0\cdots 0⟩$ 측정 확률 1
• $f$가 균형 함수이면 합은 0 → $|0\cdots 0⟩$ 측정 확률 0

측정 결과가 모두 0이면 상수, 하나라도 1이면 균형으로 단 1회 평가만으로 판별된다.

알고리즘	최선	최악
고전 결정론적	$O(1)$	$O(2^{n-1}+1)$
Deutsch-Jozsa	$O(1)$	$O(1)$

예시·응용

n = 1: Deutsch 알고리즘

$n=1$인 특수 경우가 David Deutsch가 1985년에 제안한 원래 알고리즘이다. 이를 Deutsch-Jozsa가 $n$큐비트로 일반화하였다.

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

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def deutsch_jozsa_balanced(n):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)               # 보조 큐비트 |1⟩ 초기화
    qc.h(range(n + 1))    # 전체 Hadamard
    for i in range(n):    # 균형 오라클: CNOT 연쇄
        qc.cx(i, n)
    qc.h(range(n))        # 입력 레지스터 역 Hadamard
    qc.measure(range(n), range(n))
    return qc

qc = deutsch_jozsa_balanced(n=2)
sim = AerSimulator()
result = sim.run(qc, shots=1024).result()
print(result.get_counts())
# 균형 함수 → "00"이 출력되지 않음

상수 오라클(항등 혹은 비트 반전 없음)로 바꾸면 결과는 항상 "00"만 나타난다. 이 단일 실행이 고전적 수백 번의 질의를 대체한다.

이론적 의의

Deutsch-Jozsa 알고리즘은 직접적인 실용 응용보다 양자 우월성의 최초 수학적 증명으로서 중요하다. 이후 Simon 알고리즘, Shor 알고리즘, Grover 알고리즘의 이론적 토대가 되었으며, 질의 복잡도(query complexity) 분야에서 양자-고전 분리의 표준 사례로 인용된다.

정리

Deutsch-Jozsa 알고리즘은 중첩으로 모든 입력을 동시에 평가하고, 위상 반동으로 함수 정보를 위상에 인코딩하며, Hadamard 간섭으로 단일 측정에 그 정보를 집중시킨다. 비록 현실 응용 문제를 직접 해결하지는 않지만, "양자 컴퓨터는 특정 문제에서 고전 대비 지수적 질의 이점을 가진다"는 사실을 처음으로 엄밀하게 보인 이정표적 알고리즘이다.