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

개념 소개

어떤 함수 $f:\{0,1{\}}^n\to \{0,1\}$가 주어지고, 이 함수는 다음 두 유형 중 하나임이 보장된다.

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

목표는 블랙박스(오라클)로만 접근 가능한 이 함수의 유형을 판별하는 것이다. 고전 결정론적 알고리즘은 최선을 다해도 최악의 경우 $2^{n-1}+1$번 질의해야 확실한 답을 얻을 수 있다. 예컨대 $n=3$이면 5번, $n=10$이면 513번이 필요하다. Deutsch-Jozsa 알고리즘은 이를 단 1번의 오라클 호출로 해결한다.

---

핵심 원리

양자 오라클과 위상 킥백

양자 오라클은 유니터리 연산 $U_f$로 구현된다.

$$U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$$

보조 큐비트(ancilla)를 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태로 준비하면 위상 킥백(phase kickback) 현상에 의해

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

가 성립한다. 함수값 $f(x)$가 보조 큐비트를 변경하는 대신 전체 위상으로 인코딩되는 것이 핵심이다.

알고리즘 절차

1. 초기화: 입력 레지스터 $n$개를 $|0{⟩}^{\otimes n}$, 보조 큐비트를 $|1⟩$로 설정한다.
2. 첫 번째 하다마르 변환: 모든 큐비트에 하다마르 게이트 $H$를 적용한다.

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

3. 오라클 적용: $U_f$를 한 번 호출한다. 입력 레지스터의 상태는

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

4. 두 번째 하다마르 변환: 입력 레지스터에 다시 $H^{\otimes n}$을 적용한다.

$$\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={⨁}_i{x}_i{z}_i$는 비트별 내적이다.

5. 측정: 입력 레지스터를 측정한다.
   • $|0{⟩}^{\otimes n}$이 나오면 → 상수 함수
   • 그 외의 결과가 나오면 → 균형 함수

왜 작동하는가

$|0{⟩}^{\otimes n}$ 상태의 진폭은 $z=0$을 대입하면 $\frac{1}{2^n}\sum _x(-1{)}^{f(x)}$이다.

• $f$가 상수 함수: 모든 항의 부호가 같으므로 합의 절댓값이 1 → 측정 확률 1
• $f$가 균형 함수: 양수항과 음수항이 정확히 상쇄되어 합이 0 → 측정 확률 0

**간섭(interference)**이 두 경우를 완벽하게 구분해 준다.

---

예시·응용

$n=1$ 사례 (Deutsch 알고리즘)

가장 단순한 경우로, 상수 함수($f(x)=0$ 또는 $f(x)=1$)와 균형 함수($f(x)=x$ 또는 $f(x)=1-x$)를 구분한다.

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

def deutsch_circuit(balanced=True):
    qc = QuantumCircuit(2, 1)
    # 초기화: 보조 큐비트 |1>
    qc.x(1)
    # 첫 번째 하다마르
    qc.h([0, 1])
    # 오라클 (balanced: CNOT, constant: 아무것도 안 함)
    if balanced:
        qc.cx(0, 1)
    # 두 번째 하다마르
    qc.h(0)
    qc.measure(0, 0)
    return qc

sim = AerSimulator()
for label, bal in [("constant", False), ("balanced", True)]:
    qc = deutsch_circuit(balanced=bal)
    job = sim.run(transpile(qc, sim), shots=1024)
    print(f"{label}: {job.result().get_counts()}")
# constant: {'0': 1024}
# balanced: {'1': 1024}

측정 결과가 0이면 상수, 1이면 균형으로 결정론적으로 판별된다.

이론적 의의

Deutsch-Jozsa 알고리즘은 실제 산업 응용보다 양자 우위(quantum advantage)를 최초로 엄밀하게 증명한 원형으로서 가치가 있다. 이후 Bernstein-Vazirani 알고리즘, Simon 알고리즘, 나아가 Shor·Grover 알고리즘의 이론적 토대를 제공한다. 또한 양자 회로 설계에서 오라클 추상화, 위상 킥백, 하다마르 기반 간섭이라는 세 가지 기법을 체계적으로 활용하는 방법을 가르쳐 준다.

---

정리

Deutsch-Jozsa 알고리즘은 세 가지 양자역학적 자원을 정교하게 결합한다. ① 중첩: 모든 $2^n$개 입력을 단일 상태로 동시 표현, ② 위상 킥백: 함수값을 계산 기저가 아닌 위상에 저장, ③ 간섭: 두 번째 하다마르 변환에서 상수/균형의 신호를 증폭·상쇄. 고전 복잡도 $O(2^n)$ 대비 양자 복잡도는 $O(1)$로, 지수적 격차를 가장 명쾌하게 보여주는 알고리즘이다.