Deutsch-Jozsa 알고리즘 — 단 한 번의 평가로 충분한 이유

개념 소개

어떤 함수 $f:\{0,1{\}}^n\to \{0,1\}$ 가 있다고 하자. 이 함수는 다음 두 경우 중 하나임이 보장된다.

• 상수 함수(constant function): 모든 입력에 대해 $f(x)=0$ 이거나 $f(x)=1$
• 균형 함수(balanced function): 입력의 정확히 절반은 0, 나머지 절반은 1을 출력

문제는 단순하다. $f$가 상수인지 균형인지 판별하라.

고전적으로는 최악의 경우 $2^{n-1}+1$번 질의해야 확정적으로 답을 얻는다. 앞에서 $2^{n-1}$번을 질의해 모두 같은 값이 나왔다고 해도, 단 한 번이 남아 있는 한 확신할 수 없기 때문이다. 반면 양자 회로는 단 한 번의 오라클 호출로 항상 정확한 답을 낸다.

---

핵심 원리

초기 상태 준비

$n$개의 입력 큐비트를 $|0{⟩}^{\otimes n}$으로, 보조(ancilla) 큐비트를 $|1⟩$로 초기화한다. 이후 모든 큐비트에 아다마르 변환을 적용한다.

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

오라클 적용과 위상 되차기

오라클 $U_f$는 $|x⟩|y⟩\mapsto |x⟩|y\oplus f(x)⟩$로 정의된다. 보조 큐비트가 $\frac{|0⟩-|1⟩}{\sqrt{2}}$ 상태일 때 오라클을 적용하면, $f(x)$의 값이 입력 레지스터의 위상으로 전달된다(위상 되차기).

$$U_f\left(|x⟩\otimes \frac{|0⟩-|1⟩}{\sqrt{2}}\right)=(-1{)}^{f(x)}|x⟩\otimes \frac{|0⟩-|1⟩}{\sqrt{2}}$$

오라클 적용 후 입력 레지스터 상태는 다음과 같다.

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

최종 아다마르 변환과 측정

입력 레지스터에 다시 $H^{\otimes n}$을 적용하면, $|0{⟩}^{\otimes n}$ 상태가 측정될 확률은

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

• $f$가 상수 함수이면: 모든 $(-1{)}^{f(x)}$가 같은 부호이므로 합이 $\pm 2^n$, 확률 = 1
• $f$가 균형 함수이면: 양수와 음수 항이 정확히 상쇄되어 합 = 0, 확률 = 0

따라서 측정에서 $|0{⟩}^{\otimes n}$이 나오면 상수 함수, 그 외라면 균형 함수로 결론 짓는다.

---

예시·응용

Qiskit를 활용한 1-큐비트 예시 (Deutsch 알고리즘)

$n=1$인 경우를 코드로 확인한다.

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

def deutsch_circuit(balanced: bool) -> QuantumCircuit:
    qc = QuantumCircuit(2, 1)       # q0: 입력, q1: 보조
    qc.x(1)                         # 보조 큐비트 |1>
    qc.h([0, 1])                    # 아다마르
    if balanced:
        qc.cx(0, 1)                 # 균형 오라클: CNOT
    # 상수 오라클은 아무것도 하지 않음 (f=0)
    qc.h(0)                         # 최종 아다마르
    qc.measure(0, 0)
    return qc

# balanced=True → 측정 결과 1 (균형), False → 0 (상수)

실제 의의

Deutsch-Jozsa 알고리즘 자체의 실용적 가치는 제한적이다. 그러나 이 알고리즘은 양자 병렬성과 위상 간섭이 결합할 때 고전 알고리즘 대비 지수적 이점이 발생함을 최초로 엄밀하게 증명했다. 이후 Simon 알고리즘, Shor 알고리즘, Grover 알고리즘의 설계 철학이 이 아이디어에서 출발한다.

---

정리

Deutsch-Jozsa 알고리즘의 핵심은 중첩으로 모든 입력을 동시에 오라클에 제시하고, 위상 되차기로 함수 정보를 위상에 기록한 뒤, 아다마르 간섭으로 결과를 읽어 내는 세 단계의 유기적 조합이다. 고전적으로 $O(2^n)$ 질의가 필요한 문제를 $O(1)$ 질의로 해결함으로써, 양자 계산의 가능성을 이론적으로 확립한 이정표 알고리즘이다.