문제 설정
함수 f:\{0,1\}^n\to\{0,1\}가 주어졌다고 합니다. 단, promise가 있습니다.
- constant: 모든 입력에서 같은 값
- balanced: 정확히 절반은 0, 절반은 1
고전적으로는 최악의 경우 2^{n-1}+1번 질의해야 확정할 수 있습니다.
오라클
$$
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
$$상태 변화
입력 레지스터를 균등중첩으로 만듭니다.
$$
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)}
$$판정
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}
$$의미
이 알고리즘은 실용적 문제라기보다 양자 알고리즘의 문법을 보여줍니다. 오라클 값을 phase로 옮기고, Hadamard로 모든 경로의 진폭을 한 점에서 합치게 합니다. constructive/destructive amplitude의 가장 깨끗한 예입니다.
2비트 예제로 직접 보기
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라고 판정합니다.
주의점
- promise problem입니다. 함수가 constant도 balanced도 아니면 알고리즘 보장이 깨집니다.
- 속도향상은 query complexity 기준입니다. 오라클 구현 비용은 따로 봐야 합니다.
- 출력 큐비트를 |-\rangle로 준비해야 phase kickback이 일어납니다.
전체 회로를 한 줄로 쓰기
입력 레지스터는 |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 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 함수는 꼭 단순한 한 비트 선택일 필요가 없습니다. 예를 들어 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가 없으면 왜 약해지는가
예를 들어 n=3에서 함수값 1이 딱 2개뿐인 함수는 constant도 balanced도 아닙니다. 이때 |000\rangle 진폭은 아래입니다.
$$
{1\over8}(6-2)={1\over2}
$$따라서 000이 확률 1/4로 나올 수 있습니다. 한 번 측정해서 000이 나왔다고 constant라고 말할 수 없습니다. 이 지점이 promise problem의 핵심입니다.