Deutsch-Jozsa 알고리즘 — 단 한 번의 평가로 함수의 성질 판별

개념 소개

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

• 상수 함수(constant function): 모든 입력에 대해 항상 $0$ 또는 항상 $1$을 출력한다.
• 균형 함수(balanced function): 가능한 $2^n$개의 입력 중 정확히 절반에서 $0$, 나머지 절반에서 $1$을 출력한다.

고전 컴퓨터로 이를 확실히 판별하려면 최악의 경우 $2^{n-1}+1$번의 함수 평가가 필요하다. $n=64$라면 수십억 번의 쿼리가 불가피하다. Deutsch-Jozsa 알고리즘은 이 문제를 단 한 번의 오라클 쿼리로 결정론적으로 해결한다. 이는 양자 컴퓨터가 특정 문제에서 고전 컴퓨터를 지수적으로 능가할 수 있다는 사실을 명확히 보인 초기 사례 중 하나다.

---

핵심 원리

양자 오라클과 위상 반전

알고리즘은 $n+1$개의 큐비트를 사용한다. 앞의 $n$개는 입력 레지스터, 마지막 1개는 보조(ancilla) 큐비트다. 양자 오라클 $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)$가 보조 큐비트 대신 입력 큐비트의 전역 위상으로 인코딩되는 것이 핵심이다.

알고리즘 전개

1단계. 초기화

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

2단계. 전체 Hadamard 변환

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

3단계. 오라클 적용

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

4단계. 입력 레지스터에 Hadamard 재적용 후 측정

$|0{⟩}^{\otimes n}$ 상태가 측정될 진폭은 다음과 같다.

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

• 상수 함수: 모든 항의 부호가 동일하므로 합이 $\pm 2^n$, 즉 $|{\alpha }_{0\cdots 0}{|}^2=1$. 측정 결과는 반드시 $|0\cdots 0⟩$.
• 균형 함수: 양수 항과 음수 항이 완전히 상쇄되어 합이 $0$. $|0\cdots 0⟩$이 측정될 확률은 $0$.

측정 결과 하나만으로 판별이 완료된다.

---

예시·응용

$n=1$: 원래의 Deutsch 알고리즘

$n=1$일 때는 네 가지 함수가 존재한다.

함수	$f(0)$	$f(1)$	유형
$f_1$	0	0	상수
$f_2$	1	1	상수
$f_3$	0	1	균형
$f_4$	1	0	균형

고전적으로는 두 번 평가해야 구분할 수 있지만, 양자 알고리즘은 한 번으로 충분하다.

Python 구현 (Qiskit)

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def deutsch_jozsa(n, oracle='constant'):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)                    # 보조 큐비트를 |1>로 초기화
    qc.h(range(n + 1))         # 전체 Hadamard
    qc.barrier()
    # 오라클: 균형 함수는 각 입력 큐비트에 CNOT 적용
    if oracle == 'balanced':
        for i in range(n):
            qc.cx(i, n)
    qc.barrier()
    qc.h(range(n))             # 입력 레지스터에 Hadamard 재적용
    qc.measure(range(n), range(n))
    return qc

sim = AerSimulator()
for oracle_type in ['constant', 'balanced']:
    qc = deutsch_jozsa(3, oracle=oracle_type)
    counts = sim.run(qc, shots=1).result().get_counts()
    print(f"{oracle_type}: {counts}")
# constant → {'000': 1}  (반드시 전부 0)
# balanced → {'111': 1}  (0이 아닌 비트스트링)

측정 결과가 $|00\cdots 0⟩$이면 상수 함수, 그 외의 상태이면 균형 함수로 판별한다.

후속 알고리즘과의 연결

Deutsch-Jozsa 알고리즘의 Hadamard → 오라클 → Hadamard 구조는 이후 다음 알고리즘들의 핵심 골격이 된다.

• Bernstein-Vazirani 알고리즘: 숨겨진 비트스트링을 단 한 번의 쿼리로 복원
• Simon 알고리즘: 숨겨진 주기를 지수적으로 빠르게 찾음
• Grover 탐색: 오라클 반복 구조의 기초

---

정리

Deutsch-Jozsa 알고리즘은 양자 중첩이 만드는 대규모 병렬성과 위상 반전이라는 두 가지 양자 자원을 결합한다. 오라클은 함수 정보를 위상에 새기고, 두 번째 Hadamard 변환은 전역 간섭을 통해 그 위상 정보를 진폭—즉 측정 가능한 물리량—으로 변환한다. 고전적 지수 복잡도 문제를 상수 쿼리로 해결하는 이 구조는 양자 알고리즘 설계의 원형으로서, 이후 등장하는 알고리즘들을 이해하는 데 필수적인 출발점이 된다.