도이치-조사 알고리즘

직관적 비유

동전이 $2^n$개 들어있는 가방을 생각해 보자. 모든 동전이 같은 면(전부 앞면 또는 전부 뒷면)이거나, 정확히 절반은 앞면·절반은 뒷면이다. 고전적으로는 최악의 경우 $2^{n-1}+1$개를 꺼내야 확신할 수 있지만, 양자 컴퓨터는 가방 전체를 중첩 상태로 한 번에 '열어보는' 것과 같아 단 한 번의 조작으로 결론을 낸다.

엄밀한 정의

$f:{0,1}^n \to {0,1}$이 상수 함수(constant: 모든 입력에 동일 출력) 또는 균형 함수(balanced: 정확히 절반이 0, 나머지 절반이 1)임이 보장될 때, 다음 절차로 판별한다.

1. $n$개의 입력 큐비트를 $|0\rangle^{\otimes n}$, 보조 큐비트를 $|1\rangle$로 초기화한다.
2. 모든 큐비트에 Hadamard 변환을 적용해 균일 중첩 상태를 만든다.
3. 오라클 $U_f$를 한 번 적용: $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$
4. 입력 레지스터에 다시 Hadamard 변환 후 계산 기저 측정.

측정 결과가 $|0\rangle^{\otimes n}$이면 상수 함수, 그 외이면 균형 함수로 판별된다. 고전 결정론적 알고리즘의 질의 복잡도 $O(2^n)$ 대비 단 1회 오라클 호출로 해결된다.

중요성 및 응용

• 양자 우위의 첫 엄밀한 증명: 1992년 Deutsch와 Jozsa가 제시, 양자 계산이 특정 문제에서 고전 계산보다 지수적으로 빠름을 수학적으로 확립했다.
• 양자 알고리즘 설계의 교과서: Hadamard 변환을 이용한 위상 킥백(phase kickback) 기법과 간섭 효과를 배우는 핵심 예제로 활용된다.
• Bernstein-Vazirani, Simon 알고리즘의 직접적인 전신으로, Shor·Grover 알고리즘으로 이어지는 아이디어 계보의 출발점이다.