Deutsch-Jozsa 알고리즘은 오라클 함수가 constant인지 balanced인지 한 번의 질의로 구분합니다. 양자 간섭이 어떻게 답을 확정적으로 밀어주는지 보여주는 첫 예제입니다.
## 문제 설정 {#problem}
함수 $f:\{0,1\}^n\to\{0,1\}$가 주어졌다고 합니다. 단, promise가 있습니다.
- constant: 모든 입력에서 같은 값
- balanced: 정확히 절반은 0, 절반은 1
고전적으로는 최악의 경우 $2^{n-1}+1$번 질의해야 확정할 수 있습니다.
## 오라클 {#oracle}
$$
U_f|x,y\rangle=|x,y\oplus f(x)\rangle
$$
출력 큐비트를 $|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}$로 준비하면 phase oracle처럼 작동합니다.
$$
U_f|x\rangle|-\rangle
=(-1)^{f(x)}|x\rangle|-\rangle
$$
## 상태 변화 {#state}
입력 레지스터를 균등중첩으로 만듭니다.
$$
H^{\otimes n}|0^n\rangle
=
{1\over\sqrt{2^n}}\sum_x |x\rangle
$$
오라클 뒤에는 함수값이 위상으로 새겨집니다.
$$
{1\over\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle
$$
다시 Hadamard를 걸면 $|0^n\rangle$의 진폭은 아래와 같습니다.
$$
{1\over 2^n}\sum_x (-1)^{f(x)}
$$
## 판정 {#decision}
constant이면 합이 $\pm 2^n$이므로 $|0^n\rangle$가 확정적으로 나옵니다. balanced이면 +와 -가 절반씩 상쇄되어 $|0^n\rangle$ 진폭이 0입니다.
$$
\Pr(0^n)=
\begin{cases}
1 & \text{constant}\\
0 & \text{balanced}
\end{cases}
$$
## 의미 {#meaning}
이 알고리즘은 실용적 문제라기보다 양자 알고리즘의 문법을 보여줍니다. 오라클 값을 phase로 옮기고, Hadamard로 모든 경로의 진폭을 한 점에서 합치게 합니다. constructive/destructive amplitude의 가장 깨끗한 예입니다.
## 2비트 예제로 직접 보기 {#worked-n2}
$n=2$이고 balanced 함수 $f(x)=x_1$를 생각합니다. 입력 균등중첩은 아래입니다.
$$
{1\over2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)
$$
오라클은 $x_1=1$인 항의 부호를 뒤집습니다.
$$
{1\over2}(|00\rangle+|01\rangle-|10\rangle-|11\rangle)
$$
마지막 Hadamard 후 $|00\rangle$ 진폭은 네 항의 부호 합입니다.
$$
{1\over4}(1+1-1-1)=0
$$
따라서 측정 결과가 $00$이면 constant, 아니면 balanced라고 판정합니다.
## 주의점 {#pitfalls}
- promise problem입니다. 함수가 constant도 balanced도 아니면 알고리즘 보장이 깨집니다.
- 속도향상은 query complexity 기준입니다. 오라클 구현 비용은 따로 봐야 합니다.
- 출력 큐비트를 $|-\rangle$로 준비해야 phase kickback이 일어납니다.
## 전체 회로를 한 줄로 쓰기 {#full-circuit}
입력 레지스터는 $|0^n\rangle$, 출력 큐비트는 $|1\rangle$에서 시작합니다. 첫 Hadamard 층을 통과하면 출력 큐비트는 phase kickback에 적합한 $|-\rangle$가 됩니다.
$$
|0^n\rangle|1\rangle
\xrightarrow{H^{\otimes n}\otimes H}
{1\over\sqrt{2^n}}\sum_x |x\rangle|-\rangle
\xrightarrow{U_f}
{1\over\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle|-\rangle
\xrightarrow{H^{\otimes n}\otimes I}
\sum_z \alpha_z |z\rangle|-\rangle
$$
여기서 마지막 진폭은 아래처럼 계산됩니다.
$$
\alpha_z
=
{1\over 2^n}\sum_x (-1)^{f(x)}(-1)^{x\cdot z}
$$
판정에는 사실 $z=0^n$만 보면 충분합니다. $z=0^n$이면 $x\cdot z=0$이므로 함수값의 부호 합만 남습니다.
## constant 0과 constant 1의 차이 {#constant-cases}
constant 0이면 모든 phase가 $+1$입니다. 따라서 마지막 Hadamard는 균등중첩을 다시 $|0^n\rangle$로 접습니다.
$$
{1\over\sqrt{2^n}}\sum_x |x\rangle
\xrightarrow{H^{\otimes n}}
|0^n\rangle
$$
constant 1이면 모든 phase가 $-1$입니다. 전체 상태에 global phase $-1$만 붙은 것이므로 측정 결과는 똑같이 $0^n$입니다.
$$
-{1\over\sqrt{2^n}}\sum_x |x\rangle
\xrightarrow{H^{\otimes n}}
-|0^n\rangle
$$
즉 Deutsch-Jozsa는 constant 0인지 constant 1인지는 구분하지 않습니다. 이 알고리즘의 목표는 constant와 balanced의 구분입니다.
## balanced 함수 예시를 더 보기 {#balanced-examples}
balanced 함수는 꼭 단순한 한 비트 선택일 필요가 없습니다. 예를 들어 $n=3$에서 아래 함수는 balanced입니다.
$$
f(x_1,x_2,x_3)=x_1\oplus x_2
$$
입력 8개 중 $x_1\oplus x_2=1$인 경우가 4개, 0인 경우가 4개입니다. $|000\rangle$ 진폭은 아래처럼 사라집니다.
$$
{1\over8}\sum_x (-1)^{x_1\oplus x_2}
=
{1\over8}(4-4)=0
$$
하지만 $|110\rangle$ 같은 다른 상태의 진폭은 살아날 수 있습니다. 실제로 이 함수는 Bernstein-Vazirani 형태의 선형 함수이므로 마지막 결과가 $110$으로 모입니다. Deutsch-Jozsa 입장에서는 그 값이 무엇인지는 중요하지 않고, $000$이 안 나왔다는 사실만 사용합니다.
## promise가 없으면 왜 약해지는가 {#promise-warning}
예를 들어 $n=3$에서 함수값 1이 딱 2개뿐인 함수는 constant도 balanced도 아닙니다. 이때 $|000\rangle$ 진폭은 아래입니다.
$$
{1\over8}(6-2)={1\over2}
$$
따라서 $000$이 확률 $1/4$로 나올 수 있습니다. 한 번 측정해서 $000$이 나왔다고 constant라고 말할 수 없습니다. 이 지점이 promise problem의 핵심입니다.