Deutsch-Jozsa 알고리즘 — 단 한 번의 오라클 호출로 판별하기

개념 소개

다음 문제를 생각해보자. 어떤 함수 $f:\{0,1{\}}^n\to \{0,1\}$가 있다. 이 함수는 아래 둘 중 하나임이 보장된다.

• 상수 함수(constant function): 모든 입력에 대해 출력이 항상 0 또는 항상 1
• 균형 함수(balanced function): 출력이 0인 입력과 1인 입력이 정확히 절반씩

고전 컴퓨터로 이를 판별하려면 최악의 경우 $2^{n-1}+1$번 함수를 평가해야 한다. 처음 $2^{n-1}$번의 결과가 모두 같더라도, 나머지 절반이 전부 다른 값일 가능성을 배제할 수 없기 때문이다. Deutsch-Jozsa 알고리즘은 이 문제를 단 한 번의 오라클 호출로 확정적으로 해결한다.

---

핵심 원리

위상 킥백(Phase Kickback)

양자 오라클 $U_f$는 다음과 같이 정의된다.

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

보조 큐비트(ancilla)를 $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태로 준비하면, 오라클 적용 결과가 위상으로 변환된다.

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

함수 값이 보조 큐비트에 기록되는 대신, 입력 레지스터의 진폭 위상 부호로 인코딩된다. 이것이 위상 킥백이다.

회로 구성과 수학적 전개

초기 상태 $|0{⟩}^{\otimes n}|1⟩$에서 출발한다.

1단계 — 아다마르 변환: 모든 큐비트에 $H$ 적용

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

2단계 — 오라클 적용: 위상 킥백에 의해

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

3단계 — 두 번째 아다마르 변환: 입력 레지스터에만 $H^{\otimes n}$ 적용 후, $|0{⟩}^{\otimes n}$ 상태의 진폭은

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

• $f$가 상수이면 $(-1{)}^{f(x)}$가 모두 같으므로 $|{\alpha }_0|=1$ → 측정 결과 반드시 $|00\cdots 0⟩$
• $f$가 균형이면 양의 부호와 음의 부호가 정확히 상쇄되어 ${\alpha }_0=0$ → $|00\cdots 0⟩$은 절대 나오지 않음

측정 결과가 모두 0이면 상수 함수, 하나라도 1이면 균형 함수로 확정된다.

---

예시·응용

n=1: 도이치 알고리즘

Deutsch-Jozsa의 원형인 도이치(Deutsch) 알고리즘은 $n=1$ 특수 사례다. 고전적으로는 두 번 평가가 필요한 문제를 한 번에 해결한다.

Qiskit 구현 예시

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def deutsch_jozsa_circuit(n, oracle='constant_0'):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)              # 보조 큐비트 |1⟩ 초기화
    qc.h(range(n + 1))   # 전체 아다마르

    # 오라클 구성
    if oracle == 'constant_1':
        qc.x(n)          # 전역 위상 -1 부여
    elif oracle == 'balanced':
        for i in range(n):
            qc.cx(i, n)  # 입력 큐비트별 CNOT

    qc.h(range(n))       # 입력 레지스터 두 번째 아다마르
    qc.measure(range(n), range(n))
    return qc

sim = AerSimulator()
for oracle_type in ['constant_0', 'constant_1', 'balanced']:
    qc = deutsch_jozsa_circuit(3, oracle=oracle_type)
    counts = sim.run(qc, shots=1).result().get_counts()
    print(f"{oracle_type}: {counts}")
# constant_0 → {'000': 1}
# constant_1 → {'000': 1}
# balanced   → {'000'이 아닌 값}

이론적 의의

Deutsch-Jozsa 알고리즘은 양자 컴퓨터가 고전 컴퓨터보다 지수적으로 빠를 수 있음을 최초로 명시적으로 증명한 사례다. 실용적 응용보다는 양자 우위(quantum advantage)의 개념적 토대를 제공한다. 이후 사이먼(Simon) 알고리즘과 쇼어(Shor) 알고리즘은 이 아이디어를 계승하여 소인수분해 등 현실적으로 중요한 문제에 적용했다.

---

정리

Deutsch-Jozsa 알고리즘의 핵심은 세 가지 양자역학적 자원의 결합이다. 아다마르 변환으로 모든 입력을 동시에 중첩하고, 위상 킥백으로 함수 정보를 위상에 인코딩하며, 양자 간섭으로 균형/상수 여부를 단번에 판독한다. 이 구조는 "$f$를 전부 평가한 뒤 비교"하는 고전적 방식과 본질적으로 다르며, 양자 병렬성이 단순한 비유가 아닌 수학적으로 검증된 계산 자원임을 보여준다.