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

개념 소개

함수 $f:\{0,1{\}}^n\to \{0,1\}$가 다음 두 가지 중 하나라는 사전 보장(promise)이 있다고 하자.

• 상수 함수(constant): 모든 입력 $x$에 대해 $f(x)=0$, 또는 모두 $f(x)=1$.
• 균형 함수(balanced): 정확히 $2^{n-1}$개의 입력에서 $f(x)=0$, 나머지에서 $f(x)=1$.

고전적으로 이 둘을 확실히 구분하려면 최악의 경우 $2^{n-1}+1$번의 질의가 필요하다. 앞선 $2^{n-1}$번이 모두 동일한 값을 돌려준다 해도, 그것이 상수 함수인지 아닌지는 한 번을 더 확인해야 단정 지을 수 있기 때문이다.

Deutsch-Jozsa 알고리즘은 이 문제를 단 한 번의 오라클 호출로 결정론적으로 해결한다.

---

핵심 원리

양자 오라클과 위상 반동

함수 $f$는 유니터리 오라클 $U_f$로 구현된다.

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

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

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

가 된다. $f(x)$의 정보가 전역 위상이 아닌 상대 위상으로 인코딩되는 이 현상을 **위상 반동(phase kickback)**이라 한다. 보조 큐비트는 상태가 바뀌지 않으므로 이후 계산에서 분리된다.

알고리즘 회로

1. 입력 레지스터 $n$개를 $|0{⟩}^{\otimes n}$으로, 보조 큐비트를 $|1⟩$로 초기화.
2. 전체 큐비트에 아다마르 변환 $H^{\otimes (n+1)}$ 적용.
3. 오라클 $U_f$ 적용.
4. 입력 레지스터에 다시 $H^{\otimes n}$ 적용.
5. 입력 레지스터 $n$개를 측정.

수학적 분석

2단계 이후 상태는

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

3단계(오라클) 후, 위상 반동에 의해

$$\frac{1}{\sqrt{2^n}}\sum _x(-1{)}^{f(x)}|x⟩\otimes |-⟩$$

4단계의 $H^{\otimes n}$ 적용 후 $|0{⟩}^{\otimes n}$ 상태를 관측할 진폭은

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

• 상수 함수이면 $(-1{)}^{f(x)}$가 모두 $+1$ 또는 $-1$이므로 합이 $\pm 2^n$, 즉 $|{\alpha }_{0^n}{|}^2=1$ → 측정 결과가 반드시 $|0{⟩}^{\otimes n}$.
• 균형 함수이면 양의 항과 음의 항이 정확히 상쇄되어 합이 $0$, 즉 $|{\alpha }_{0^n}{|}^2=0$ → $|0{⟩}^{\otimes n}$이 절대 관측되지 않음.

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

---

예시·응용

n=1: 도이치 알고리즘

$n=1$인 특수 경우를 도이치(Deutsch) 알고리즘이라 한다. 가능한 일비트 함수 네 가지 중 $f(0)=f(1)=0$과 $f(0)=f(1)=1$은 상수 함수, $f(0)=0,f(1)=1$과 $f(0)=1,f(1)=0$은 균형 함수다.

Qiskit 구현 예시

from qiskit import QuantumCircuit

def deutsch_jozsa_circuit(n, oracle_type='balanced'):
    """
    oracle_type: 'constant_0', 'constant_1', 'balanced'
    """
    qc = QuantumCircuit(n + 1, n)

    # 보조 큐비트 |1⟩ 준비
    qc.x(n)

    # 전체 아다마르 (중첩 + |-⟩ 생성)
    qc.h(range(n + 1))

    # 오라클
    if oracle_type == 'constant_1':
        qc.x(n)          # 전체 위상 -1
    elif oracle_type == 'balanced':
        for i in range(n):
            qc.cx(i, n)  # 간단한 균형 오라클

    # 입력 레지스터에 아다마르
    qc.h(range(n))

    # 측정
    qc.measure(range(n), range(n))
    return qc

qc = deutsch_jozsa_circuit(3, oracle_type='balanced')
print(qc.draw(output='text'))
# 측정 결과: 000이 아닌 값 → 균형 함수 확인

의의와 한계

이 알고리즘이 해결하는 문제 자체는 실용성이 낮다. 그러나 중첩으로 모든 입력을 동시에 탐색하고, 위상 반동으로 함수 정보를 인코딩한 뒤, 간섭으로 유용한 결과만 증폭하는 3단계 구조는 Bernstein-Vazirani, Simon, Shor, Grover 알고리즘 전반에 걸쳐 반복된다.

---

정리

Deutsch-Jozsa 알고리즘은 양자 계산의 세 가지 핵심 자원인 중첩·위상·간섭이 어떻게 맞물리는지를 가장 단순하고 명확하게 보여준다. 고전 컴퓨터가 $O(2^n)$ 질의를 필요로 하는 문제를 단 한 번의 오라클 호출로 결정론적으로 해결하며, 이는 양자 알고리즘이 고전 알고리즘보다 지수적으로 빠를 수 있다는 첫 번째 엄밀한 증거가 된다.