Deutsch-Jozsa 알고리즘 — 단 한 번의 평가로 함수의 본질을 밝히다

개념 소개

$n$비트 입력을 받아 0 또는 1을 출력하는 함수 $f:\{0,1{\}}^n\to \{0,1\}$가 있다고 하자. 이 함수가 상수 함수(constant) — 모든 입력에 대해 같은 값 출력 — 인지, 균형 함수(balanced) — 절반은 0, 절반은 1 출력 — 인지 판별하는 문제다.

고전 결정론적 알고리즘은 최악의 경우 $2^{n-1}+1$번의 함수 호출이 필요하다. 반면 Deutsch-Jozsa 알고리즘은 단 1번의 오라클 호출로 확실한 답을 낸다. 이것이 최초로 엄밀히 증명된 양자-고전 지수적 격차다.

---

핵심 원리

회로 구성

총 $n+1$개의 큐비트를 사용한다. 상위 $n$개는 입력 레지스터, 나머지 1개는 보조(ancilla) 큐비트다.

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

1단계 — Hadamard 적용

모든 큐비트에 Hadamard 게이트를 적용하면 입력 레지스터는 균등 중첩이 되고, 보조 큐비트는 $\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태가 된다.

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

2단계 — 오라클(위상 되차기)

양자 오라클 $U_f$는 $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$로 정의된다. 보조 큐비트가 $\frac{|0⟩-|1⟩}{\sqrt{2}}$일 때 오라클을 적용하면 위상 되차기가 발생한다.

$$U_f|x⟩\frac{|0⟩-|1⟩}{\sqrt{2}}=(-1{)}^{f(x)}|x⟩\frac{|0⟩-|1⟩}{\sqrt{2}}$$

오라클 적용 후 입력 레지스터는 다음과 같다.

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

3단계 — 두 번째 Hadamard 및 측정

입력 레지스터에 다시 Hadamard를 적용하면 $|0{⟩}^{\otimes n}$ 상태의 진폭은 아래와 같다.

$$⟨0^n|{\psi }_3⟩=\frac{1}{2^n}\sum _x(-1{)}^{f(x)}$$

• $f$가 상수 함수이면 모든 항의 부호가 같으므로 진폭의 절댓값은 1 → $|0{⟩}^{\otimes n}$ 측정 확률 100%
• $f$가 균형 함수이면 부호가 절반씩 상쇄되어 진폭은 0 → $|0{⟩}^{\otimes n}$ 측정 확률 0%

따라서 측정 결과가 모두 0이면 상수, 그렇지 않으면 균형으로 결론 내릴 수 있다.

---

예시·응용

1큐비트 Deutsch 알고리즘 ($n=1$)

4가지 가능한 함수 중 $f(x)=x$ (균형)를 예로 들면, 오라클 적용 후 입력 큐비트의 위상이 뒤집혀 두 번째 Hadamard 이후 $|1⟩$이 측정된다.

Qiskit 구현 예시

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def deutsch_jozsa(n, oracle_type="balanced"):
    qc = QuantumCircuit(n + 1, n)
    # 초기화
    qc.x(n)          # 보조 큐비트 |1>
    qc.h(range(n + 1))
    # 오라클 (균형: 첫 번째 입력 큐비트와 보조 큐비트 CNOT)
    if oracle_type == "balanced":
        qc.cx(0, n)
    # 두 번째 Hadamard
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

qc = deutsch_jozsa(n=3, oracle_type="balanced")
result = AerSimulator().run(qc, shots=1).result()
print(result.get_counts())  # {'001': 1} 또는 비-000 결과 → 균형 함수

의의와 한계

이 알고리즘은 실제 응용보다 개념 증명으로서의 가치가 크다. 현실 문제에서 함수가 반드시 상수 또는 균형 중 하나라고 보장되지 않기 때문이다. 그러나 Bernstein-Vazirani, Simon 알고리즘 등 더 강력한 알고리즘들의 이론적 토대가 되었다.

---

정리

Deutsch-Jozsa 알고리즘의 핵심은 중첩으로 모든 입력을 동시에 평가하고, 위상 되차기로 함수 정보를 위상에 인코딩하며, 간섭으로 전역 정보를 읽어내는 세 단계의 협력이다. 이 구조는 이후 대부분의 양자 알고리즘 설계에서 반복적으로 등장하는 기본 패턴이다.