Deutsch-Jozsa 알고리즘 — 단 한 번의 평가로 판별하기

개념 소개

함수 $f:\{0,1{\}}^n\to \{0,1\}$이 다음 두 가지 중 하나라고 보장되어 있다고 가정한다.

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

고전 결정론적 알고리즘은 최악의 경우 $2^{n-1}+1$번 함수를 평가해야 두 경우를 구별할 수 있다. Deutsch-Jozsa 알고리즘은 오라클을 단 한 번 호출하는 것으로 이를 확정적으로 해결한다.

일상적 비유로는, 동전이 모두 앞면(상수)인지 정확히 절반이 뒷면(균형)인지를 동전을 하나씩 뒤집어 확인하는 대신, 전체를 동시에 비추는 특수한 거울로 한 번에 확인하는 것과 유사하다.

---

핵심 원리

회로 구성

알고리즘은 $n$개의 입력 큐비트와 1개의 보조(ancilla) 큐비트로 구성된다.

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

1단계 — Hadamard 변환:
모든 큐비트에 $H$를 적용하면,

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

여기서 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$이다.

2단계 — 양자 오라클 $U_f$ 적용:
오라클은 $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$로 정의된다. 보조 큐비트가 $|-⟩$ 상태일 때 이른바 **위상 킥백(phase kickback)**이 발생한다.

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

3단계 — 입력 큐비트에 다시 Hadamard 적용:
$H^{\otimes n}$을 적용하면,

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

4단계 — 측정:
$z=0^n$ (모두 0) 상태의 진폭은 $\frac{1}{2^n}{\sum }_x(-1{)}^{f(x)}$이다.

• $f$가 상수 함수이면 모든 항의 부호가 같으므로 합의 절댓값이 1 → $|0{⟩}^{\otimes n}$ 측정 확률 = 1
• $f$가 균형 함수이면 양수·음수 항이 정확히 상쇄되어 합 = 0 → $|0{⟩}^{\otimes n}$ 측정 확률 = 0

따라서 입력 큐비트를 측정하여 전부 0이면 상수, 하나라도 1이면 균형으로 판별한다.

---

예시·응용

$n=1$인 경우 (Deutsch 알고리즘)

$f:\{0,1\}\to \{0,1\}$의 네 가지 경우 — $f\equiv 0$, $f\equiv 1$(상수), $f(x)=x$, $f(x)=1-x$(균형) — 를 단 1번의 오라클 호출로 구별한다. 이것이 Deutsch의 원래 1985년 아이디어이며, Deutsch-Jozsa는 이를 $n$비트로 일반화한 것이다.

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

from qiskit import QuantumCircuit

def deutsch_jozsa_balanced(n=3):
    qc = QuantumCircuit(n + 1, n)
    # 초기화
    qc.x(n)                  # 보조 큐비트 |1>
    qc.h(range(n + 1))       # 모든 큐비트에 Hadamard
    # 균형 오라클 예시: 첫 번째 입력 큐비트를 보조에 CNOT
    for i in range(n):
        qc.cx(i, n)
    qc.h(range(n))            # 입력 큐비트에 다시 Hadamard
    qc.measure(range(n), range(n))
    return qc

qc = deutsch_jozsa_balanced()
print(qc.draw())
# 측정 결과: 000이 아닌 값 → 균형 함수로 판별

의의와 한계

Deutsch-Jozsa 알고리즘은 실용적 문제를 직접 해결하기보다, 양자 병렬성과 간섭이 결합하면 지수적 속도 향상이 가능함을 최초로 증명한 '개념 증명'으로서의 가치가 크다. Simon 알고리즘, Shor 알고리즘 등 이후 양자 알고리즘들의 이론적 토대가 된다.

---

정리

Deutsch-Jozsa 알고리즘의 핵심은 두 단계의 Hadamard 변환 사이에 오라클을 배치하는 구조다. 첫 번째 Hadamard로 모든 입력의 중첩을 생성하고, 오라클의 위상 킥백으로 함수 정보를 위상에 인코딩한 뒤, 두 번째 Hadamard로 간섭을 통해 정보를 진폭에 집약시킨다. 측정은 단 한 번으로 충분하며, 오류 없이 확정적 결과를 낸다는 점에서 확률적 양자 알고리즘과도 구별된다.