Deutsch-Jozsa 알고리즘은 오라클 함수가 constant인지 balanced인지 한 번의 질의로 구분합니다. 양자 간섭이 어떻게 답을 확정적으로 밀어주는지 보여주는 첫 예제입니다.

문제 설정

함수 $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의 핵심입니다.