Industry map소프트웨어알고리즘
Definition
주어진 함수가 '상수 함수'인지 '균형 함수'인지를 단 한 번의 양자 질의(query)로 판별하는 알고리즘으로, 고전 알고리즘 대비 지수적 속도 향상을 최초로 엄밀히 증명한 사례이다.
직관적 비유
동전이 $2^n$개 들어있는 가방을 생각해 보자. 모든 동전이 같은 면(전부 앞면 또는 전부 뒷면)이거나, 정확히 절반은 앞면·절반은 뒷면이다. 고전적으로는 최악의 경우 $2^{n-1}+1$개를 꺼내야 확신할 수 있지만, 양자 컴퓨터는 가방 전체를 중첩 상태로 한 번에 '열어보는' 것과 같아 단 한 번의 조작으로 결론을 낸다.
엄밀한 정의
$f:{0,1}^n \to {0,1}$이 상수 함수(constant: 모든 입력에 동일 출력) 또는 균형 함수(balanced: 정확히 절반이 0, 나머지 절반이 1)임이 보장될 때, 다음 절차로 판별한다.
- $n$개의 입력 큐비트를 $|0\rangle^{\otimes n}$, 보조 큐비트를 $|1\rangle$로 초기화한다.
- 모든 큐비트에 Hadamard 변환을 적용해 균일 중첩 상태를 만든다.
- 오라클 $U_f$를 한 번 적용: $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$
- 입력 레지스터에 다시 Hadamard 변환 후 계산 기저 측정.
측정 결과가 $|0\rangle^{\otimes n}$이면 상수 함수, 그 외이면 균형 함수로 판별된다. 고전 결정론적 알고리즘의 질의 복잡도 $O(2^n)$ 대비 단 1회 오라클 호출로 해결된다.
중요성 및 응용
- 양자 우위의 첫 엄밀한 증명: 1992년 Deutsch와 Jozsa가 제시, 양자 계산이 특정 문제에서 고전 계산보다 지수적으로 빠름을 수학적으로 확립했다.
- 양자 알고리즘 설계의 교과서: Hadamard 변환을 이용한 위상 킥백(phase kickback) 기법과 간섭 효과를 배우는 핵심 예제로 활용된다.
- Bernstein-Vazirani, Simon 알고리즘의 직접적인 전신으로, Shor·Grover 알고리즘으로 이어지는 아이디어 계보의 출발점이다.
