Deutsch-Jozsa 알고리즘: 단 한 번의 양자 질의로 답을 구하다

개념 소개

어떤 함수 $f:\{0,1{\}}^n\to \{0,1\}$ 가 주어졌을 때, 이 함수가 상수 함수(constant, 모든 입력에 대해 출력이 0 혹은 1로 동일)인지 균형 함수(balanced, 출력 0과 1이 정확히 절반씩)인지 판별하는 문제를 생각해 보자.

고전 결정론적 알고리즘으로는 최악의 경우 $2^{n-1}+1$번 함수를 평가해야 한다. 입력 개수가 $n=100$이면, 우주의 나이로도 처리하기 어려운 횟수다. 반면 Deutsch-Jozsa 알고리즘은 단 한 번의 오라클 질의로 확실한 답을 낸다. 이것이 알고리즘의 핵심 선언이다.

함수를 직접 계산할 수 없고 오라클(oracle)을 통해서만 질의할 수 있다는 블랙박스 모형이 전제된다. 오라클은 다음과 같은 유니타리 변환으로 표현된다.

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

---

핵심 원리

위상 반전(Phase Kickback)

보조 큐비트(ancilla)를 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태로 준비하면, 오라클이 입력 레지스터에 위상 형태로 $f(x)$를 기록한다.

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

이를 위상 반전이라 한다. 보조 큐비트는 변하지 않으므로 이후 무시할 수 있다.

회로 구성과 상태 변화

1단계 — 초기 상태를 준비한다.

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

2단계 — 모든 큐비트에 Hadamard를 적용한다.

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

3단계 — 오라클을 적용(위상 반전 이용)한다.

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

4단계 — 입력 레지스터에 다시 Hadamard를 적용한다.

$$|{\psi }_3⟩=\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⟩$$

5단계 — $|0{⟩}^{\otimes n}$ 에 대한 진폭을 분석한다.

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

• $f$가 상수 함수이면: 모든 항의 부호가 같아 합산값은 $\pm 1$ → 측정 시 반드시 $|0{⟩}^{\otimes n}$
• $f$가 균형 함수이면: 양의 항과 음의 항이 정확히 상쇄되어 합산값은 $0$ → 측정 시 절대 $|0{⟩}^{\otimes n}$이 나오지 않음

결론적으로, 첫 번째 레지스터를 측정해 $|00\cdots 0⟩$이 나오면 상수 함수, 그렇지 않으면 균형 함수다.

---

예시·응용

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

$n=1$이면 함수는 $f:\{0,1\}\to \{0,1\}$이며, 상수는 $f(0)=f(1)$, 균형은 $f(0)\ne f(1)$이다.

회로 출력이 $|0⟩$이면 상수, $|1⟩$이면 균형으로 판별된다. 고전적으로는 반드시 두 번 평가가 필요하다.

Qiskit 구현 예시 ($n=2$, 균형 함수)

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

def deutsch_jozsa_balanced(n=2):
    qc = QuantumCircuit(n + 1, n)
    # 초기 준비
    qc.x(n)          # 보조 큐비트 |1⟩
    qc.h(range(n+1)) # 모든 큐비트에 Hadamard
    # 균형 오라클: CNOT(x_0 → ancilla), CNOT(x_1 → ancilla)
    for i in range(n):
        qc.cx(i, n)
    # 최종 Hadamard
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

qc = deutsch_jozsa_balanced()
sim = AerSimulator()
result = sim.run(transpile(qc, sim), shots=1024).result()
print(result.get_counts())  # {'11': 1024} 또는 비제로 — 균형 함수 확인

알고리즘의 의의와 한계

이 알고리즘은 오라클 복잡도에서 지수적 양자 이점을 증명한 첫 사례로, Shor 알고리즘과 Grover 알고리즘의 개념적 선구자 역할을 했다. 다만 실용적 활용보다는 양자 알고리즘 설계 원리 교육에 주된 가치가 있다. 실제 문제에서 함수가 상수 또는 균형 중 하나임이 보장되는 상황은 드물기 때문이다.

---

정리

Deutsch-Jozsa 알고리즘은 세 가지 양자역학적 원리를 정교하게 조합한다. Hadamard를 통한 중첩으로 모든 입력을 동시에 탐색하고, 위상 반전으로 $f(x)$의 정보를 위상 형태로 인코딩하며, 두 번째 Hadamard의 간섭을 통해 원하는 답에 진폭을 집중시킨다. 이 세 단계의 흐름은 이후 등장하는 양자 알고리즘 대부분이 따르는 설계 철학을 명확히 보여준다.