Deutsch-Jozsa 알고리즘 — 단 한 번의 오라클 평가

개념 소개

Deutsch-Jozsa 알고리즘은 David Deutsch와 Richard Jozsa가 제안한 알고리즘으로, 양자컴퓨터가 고전 컴퓨터 대비 지수적으로 빠를 수 있음을 보여주는 최초의 명확한 사례다. 문제 자체는 단순하지만, 핵심 양자 기법들이 집약되어 있어 양자 알고리즘 학습의 출발점으로 자주 활용된다.

문제 설정: 함수 $f:\{0,1{\}}^n\to \{0,1\}$가 다음 두 경우 중 하나임이 약속(promise)되어 있다.

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

고전 컴퓨터는 최악의 경우 $2^{n-1}+1$번 질의해야 확정 판별이 가능하다. 양자 알고리즘은 이를 단 1번의 오라클 호출로 완벽하게 해결한다.

---

핵심 원리

알고리즘은 $n+1$개의 큐비트를 사용한다. 앞 $n$개는 입력 레지스터, 마지막 1개는 보조(ancilla) 큐비트다.

1단계: 초기화

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

2단계: 전체 하다마르 변환

모든 큐비트에 $H$ 게이트를 적용한다.

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

입력 레지스터는 $2^n$개 상태의 동등 중첩, 보조 큐비트는 $|-⟩$ 상태가 된다.

3단계: 오라클 $U_f$ 적용 (위상 킥백)

오라클은 보조 큐비트가 $|-⟩$ 상태일 때 위상 킥백에 의해 다음과 같이 작동한다.

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

함수값이 위상으로 인코딩되어 입력 레지스터에 기록된다.

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

4단계: 입력 레지스터에 다시 하다마르 변환

$n$큐비트 하다마르 변환은 $H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}{\sum }_z(-1{)}^{x\cdot z}|z⟩$이며, 여기서 $x\cdot z={⨁}_i{x}_i{z}_i$이다. 최종 상태에서 $|0{⟩}^{\otimes n}$의 진폭은:

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

• f가 상수 함수: 모든 $(-1{)}^{f(x)}$의 부호가 같으므로 합 $=\pm 1$ → $|0{⟩}^{\otimes n}$ 측정 확률 100%
• f가 균형 함수: $+1$과 $-1$이 정확히 상쇄되어 합 $=0$ → $|0{⟩}^{\otimes n}$ 측정 확률 0%

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

---

예시·응용

Qiskit을 이용한 구현 예시

from qiskit import QuantumCircuit

def deutsch_jozsa_circuit(oracle_type='balanced', n=3):
    qc = QuantumCircuit(n + 1, n)

    # 보조 큐비트를 |1> 로 초기화
    qc.x(n)

    # 전체 하다마르 변환
    qc.h(range(n + 1))
    qc.barrier()

    # 오라클 적용
    if oracle_type == 'balanced':
        # 균형 오라클: 각 입력 큐비트를 보조 큐비트에 CNOT
        for i in range(n):
            qc.cx(i, n)
    # constant oracle: 아무 게이트도 없음 (항등 변환)

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

    # 입력 레지스터 측정
    qc.measure(range(n), range(n))
    return qc

qc_balanced = deutsch_jozsa_circuit('balanced', n=3)
print(qc_balanced.draw())

oracle_type='balanced'이면 측정 결과는 반드시 000이 아닌 값, oracle_type='constant'이면 반드시 000이 출력된다.

이론적 의의

Deutsch-Jozsa 알고리즘은 실용적 응용보다 이론적 가치가 핵심이다. 이 알고리즘은 양자 병렬성과 간섭이 결합하면 고전적으로 지수 시간이 필요한 문제를 상수 시간에 해결할 수 있음을 증명했다. 이후 Simon 알고리즘(2의 멱 위수 탐색), Shor 알고리즘(정수 인수분해) 등 더 실용적인 양자 알고리즘들이 유사한 구조—중첩으로 병렬 평가, 간섭으로 정보 추출—를 계승한다.

---

정리

Deutsch-Jozsa 알고리즘은 세 가지 핵심 기법의 결합이다: (1) 하다마르 변환을 통한 모든 입력의 동시 중첩, (2) 위상 킥백을 통한 함수값의 위상 인코딩, (3) 역 하다마르 변환을 통한 간섭으로 정보를 결정론적으로 추출. 오라클 1회 호출에 $2^n$개 입력을 병렬 처리하는 이 구조는, 이후 설계되는 모든 양자 알고리즘의 근본 패러다임으로 이어진다.