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

개념 소개

어떤 블랙박스 함수 $f:\{0,1{\}}^n\to \{0,1\}$이 주어졌다고 하자. 이 함수는 다음 두 경우 중 하나임이 보장된다.

• 상수 함수(constant): 모든 입력에 대해 출력이 동일 (전부 0 또는 전부 1)
• 균형 함수(balanced): 정확히 절반의 입력에서 0, 나머지 절반에서 1을 출력

고전 컴퓨터로 이를 확정 판별하려면 최악의 경우 $2^{n-1}+1$번 질의해야 한다. 앞선 $2^{n-1}$번이 모두 동일한 값을 돌려줄 때 비로소 '혹시 균형일 수도 있지 않나'를 배제하기 위해 한 번이 더 필요하기 때문이다. Deutsch-Jozsa 알고리즘은 양자 컴퓨터로 단 1번의 오라클 호출만으로 이 판별을 확정적으로 완료한다.

---

핵심 원리

양자 오라클

함수 $f$를 가역 유니터리로 구현한 오라클 $U_f$를 다음과 같이 정의한다.

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

$|x⟩$은 $n$큐비트 입력 레지스터, $|y⟩$은 1큐비트 보조(ancilla) 레지스터, $\oplus$는 XOR이다.

위상 반동 (Phase Kickback)

보조 큐비트를 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태로 준비하면 오라클 적용 후:

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

$f(x)$의 값이 진폭의 위상으로 인코딩된다. 이 기법을 위상 반동이라 한다.

알고리즘 절차

단계	연산	상태
초기화	—	$
Hadamard	$H^{\otimes n}\otimes H$	$\dfrac{1}{\sqrt{2^n}}\displaystyle\sum_x
오라클	$U_f$	$\dfrac{1}{\sqrt{2^n}}\displaystyle\sum_x (-1)^{f(x)}
역 Hadamard	$H^{\otimes n}$	간섭 후 측정 준비
측정	—	결과 판독

역 Hadamard 변환 후 $|0{⟩}^{\otimes n}$이 측정될 확률은:

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

• $f$가 상수 함수이면 $(-1{)}^{f(x)}$가 모두 같은 부호 → 합의 절댓값 $=2^n$ → $P(0^n)=1$
• $f$가 균형 함수이면 양·음 위상이 정확히 상쇄 → 합 $=0$ → $P(0^n)=0$

따라서 측정값이 $0^n$이면 상수, 그 외이면 균형으로 단번에 확정된다.

---

예시·응용

Qiskit 구현 ($n=2$)

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def deutsch_jozsa(oracle_type='balanced', n=2):
    qc = QuantumCircuit(n + 1, n)
    # 보조 큐비트를 |1> 로 설정
    qc.x(n)
    # 전체 Hadamard → 균등 중첩 + |-> 생성
    qc.h(range(n + 1))
    qc.barrier()
    # 오라클: balanced = 각 입력 큐비트를 보조에 CNOT
    if oracle_type == 'balanced':
        for i in range(n):
            qc.cx(i, n)
    # constant_1: 보조 큐비트에 X 추가 (전역 위상 차이만)
    elif oracle_type == 'constant_1':
        qc.x(n)
    qc.barrier()
    # 역 Hadamard
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

sim = AerSimulator()
for otype in ['constant_0', 'balanced']:
    qc = deutsch_jozsa(otype, n=2)
    result = sim.run(qc, shots=1024).result()
    print(f"{otype}: {result.get_counts()}")
# constant_0 → {'00': 1024}
# balanced   → {'11': 1024} 또는 00 이외의 값

balanced 오라클에서는 항상 00 이외의 비트열이 측정되고, constant_0 오라클에서는 항상 00이 측정된다.

알고리즘의 역사적 의의

Deutsch-Jozsa 알고리즘이 실용 문제를 직접 해결하지는 않지만, 다음 의미에서 중요하다.

1. 양자 간섭이 계산 이점의 핵심 메커니즘임을 최초로 명시적으로 보인 사례다.
2. 위상 반동 기법은 이후 Bernstein-Vazirani, Simon, Grover, Shor 알고리즘으로 이어지는 설계 원형이다.
3. '오라클 복잡도' 관점에서 양자 지수 우위가 존재함을 수학적으로 증명한 첫 번째 사례다.

---

정리

Deutsch-Jozsa 알고리즘은 세 가지 요소의 결합으로 동작한다. 첫째, $H^{\otimes n}$으로 모든 입력을 동시에 균등 중첩 상태로 만든다. 둘째, 오라클이 위상 반동을 통해 $f(x)$ 정보를 위상으로 인코딩한다. 셋째, 다시 $H^{\otimes n}$을 적용해 보강·상쇄 간섭을 일으켜 단 한 번의 측정으로 결론을 추출한다. 이 '중첩 → 위상 인코딩 → 간섭 → 측정'의 구조는 양자 알고리즘 설계의 근본 패턴으로, 이후 알고리즘들이 공통으로 계승한다.