Deutsch-Jozsa 알고리즘 — 단 한 번의 양자 평가

개념 소개

$n$비트 입력을 받아 0 또는 1을 반환하는 블랙박스 함수 $f:\{0,1{\}}^n\to \{0,1\}$가 주어진다고 하자. 단, 이 함수는 반드시 아래 두 가지 중 하나임이 보장된다.

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

고전 컴퓨터는 최악의 경우 $2^{n-1}+1$번 함수를 평가해야 확신할 수 있다. Deutsch-Jozsa 알고리즘은 이를 단 1번의 오라클 호출로 해결한다. 이처럼 약속이 전제된 문제를 **약속 문제(promise problem)**라 부른다.

핵심 원리

양자 오라클과 위상 반동

오라클은 유니터리 변환 $U_f$로 구현된다.

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

출력 큐비트를 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$로 초기화하면 위상 반동(phase kickback) 현상에 의해

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

가 된다. 즉, $f(x)$의 값이 출력 큐비트 대신 입력 레지스터의 위상에 각인된다.

알고리즘 4단계

초기 상태: $|0{⟩}^{\otimes n}|1⟩$

1단계 — 전체 큐비트에 아다마르 변환:

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

2단계 — 오라클 $U_f$ 적용:

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

3단계 — 입력 레지스터 $n$개 큐비트에 $H^{\otimes n}$ 재적용.

$H^{\otimes n}$의 정의에 의해 기저 $|0{⟩}^{\otimes n}$의 진폭은

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

이다. $f$가 상수이면 이 합의 절댓값은 1이고, 균형이면 양·음 항이 정확히 상쇄되어 0이 된다.

4단계 — 측정: 결과가 $|0{⟩}^{\otimes n}$이면 상수, 하나라도 1이 포함되면 균형 함수.

예시·응용

n = 1: Deutsch 알고리즘 (Qiskit 예시)

from qiskit import QuantumCircuit

def deutsch_circuit(balanced=False):
    qc = QuantumCircuit(2, 1)
    qc.x(1)          # 보조 큐비트를 |1⟩로 초기화
    qc.h([0, 1])     # 아다마르 변환
    if balanced:
        qc.cx(0, 1)  # 균형 오라클: f(x) = x
    # 상수 오라클(f=0)은 항등 연산
    qc.h(0)          # 입력 큐비트에 H 재적용
    qc.measure(0, 0)
    return qc

측정 결과 0 → 상수 함수, 1 → 균형 함수.

의의와 후속 알고리즘

이 알고리즘은 실용적 계산 문제보다 양자 병렬성과 간섭의 원리적 우위를 처음으로 수학적으로 증명한다. 오라클 기반 설계 방식은 Grover 탐색 알고리즘(제곱근 가속)으로, 아다마르 변환 패턴은 양자 푸리에 변환을 거쳐 Shor 알고리즘으로 이어진다. 다만 실제 응용에서는 함수가 상수 또는 균형 중 하나라는 보장이 주어지지 않으므로, 이 알고리즘 자체의 직접적 실용성은 제한적이다.

정리

Deutsch-Jozsa 알고리즘의 흐름은 준비 → 오라클 → 간섭 → 측정으로 요약된다. 아다마르 변환이 모든 입력 상태를 균등 중첩으로 만들고, 단 한 번의 오라클 호출이 위상을 통해 전역적 함수 정보를 인코딩하며, 두 번째 아다마르 변환이 측정 가능한 신호로 변환한다. 이 세 요소의 결합이 고전적으로 지수 복잡도인 문제를 $O(1)$ 쿼리로 해결하게 하며, 양자 알고리즘 설계 원리를 가장 깔끔하게 보여주는 교과서적 사례로 남아 있다.