Quantum Algorithm #1

1. Deutsch-Jozsa Algorithm

Deutsch-Jozsa 알고리즘은 일변수 함수를 사용하는 Deutsch 알고리즘을 다변수로 일반화시킨 문제이다. 이 알고리즘은 더 이상 유용하게 사용되지는 않고, quantum supremacy를 확인한 최초의 문제로 역사적인 의미가 더 크다. 우선 함수 $f$를 아래와 같이 정의한다.

$$ f(x_{1}, \cdots , x_{n}) \in \{0, 1 \}. $$

만약 여기서 정의역 내의 모든 가능한 원소의 함숫값이 하나의 값으로 결정될 경우를 constant function, 0 또는 1로 정확히 절반으로 나뉠 경우 balanced function이라고 한다. 우리의 목표는 단 한번의 측정을 통해 함수 $f$가 constant인지 balanced인지 확인하는 것이다. 

 

1. 초기 파동함수는 다음과 같다.

 $$ \left| \psi_{0} \right\rangle = \left| 0 \right\rangle ^{\otimes n} \left| 1 \right\rangle. $$

2. 여기에 Hadamard gate를 가하고, binary number로 변형시켜주면 다음과 같다.

$$ \left| \psi_{1} \right\rangle = { 1 \over \sqrt{2^{n+1}} } \underset{x=0}{\overset{2^{n}-1}{\sum}} \left| x \right\rangle ( \left| 0 \right\rangle - \left| 1 \right\rangle ).$$

3. 여기에 oracle $U_{f}$ gate를 가한다.

$$ \left| \psi_{2} \right\rangle = {1 \over \sqrt{2^{n+1}}} \underset{x=0}{\overset{2^{n}-1}{\sum}} \left| x \right\rangle (\left| f(x) \right\rangle - \left| 1 \oplus f(x) \right\rangle ) = {1 \over \sqrt{2^{n+1}}} \underset{x=0}{\overset{2^{n}-1}{\sum}} (-1)^{f(x)} \left| x \right\rangle (\left| 0 \right\rangle - \left| 1  \right\rangle ). $$

4. 여기에 Hadamard gate를 가한다. 이때 n+1번째 qubit은 측정하지 않으므로 무시할 수 있다. 아래에서 $x \cdot y$는 $\underset{i=1}{\overset{n}{\bigoplus}} x_{i}y_{i}$ 를 의미한다.

$$ \left| \psi_{3} \right\rangle = {1 \over 2^{n}} \underset{x=0}{\overset{2^{n}-1}{\sum}} (-1)^{f(x)} \left[ \underset{y=0}{\overset{2^{n}-1}{\sum}} (-1)^{x \cdot y} \left| y \right\rangle \right] = {1 \over 2^{n}} \underset{x=0}{\overset{2^{n}-1}{\sum}} \left[ \underset{y=0}{\overset{2^{n}-1}{\sum}} (-1)^{f(x) + x \cdot y} \left| y \right\rangle \right]. $$

5. 여기서 측정을 하게 되면, $\left| 0 \right\rangle ^{\otimes n}$이 측정될 확률은 아래와 같다.

$$ \left| 0 \right\rangle ^{\otimes n} \rightarrow |{1 \over 2^{n}} \sum (-1)^{f(x)}|^{2}. $$

 

따라서 측정 결과가$ \left| 0 \right\rangle ^{\otimes n} $일 경우, $f$는 constant function이다. 

반대로 측정 결과가 $ \left| 0 \right\rangle ^{\otimes n} $이 아닐 경우, $f$는 balanced function이다. $\Box$

 

2. Quantum Fourier Transformation

Quantum Fourier Transformation$($이하 QFT$)$은 이후에 다룰 Quantum Phase Estimation$($이하 QPE$)$의 tool로 작용하고, QPE는 Shor's Algorithm의 핵심 개념이다. 그럼 QFT를 배워보자. 

QFT는 기존 classical FT와 다른 점이 거의 없다. 약간의 선형대수의 기저 개념이 추가된 정도? 기존 FT의 공식은 어떤 벡터를 다른 벡터로 변환해주고, 그 공식은 다음과 같이 주어진다.

$$ y_{k} = {1 \over \sqrt{N}} \overset{N-1}{\underset{j=0}{\sum}} x_{j} w_{N}^{jk} $$

where $w_{N} = e^{2 \pi i /N}$.

비슷하게 QFT는 quantum state $\left| X \right\rangle = \sum_{j} x_{j} \left| j \right\rangle $에 작용하여 $\left| Y \right\rangle = \sum_{k} y_{k} \left| k \right\rangle$로 변환한다. 이때 변환 공식은 다음과 같다$($기존 공식과 동일하다$)$.

$$ y_{k} = {1 \over \sqrt{N}} \overset{N-1}{\underset{j=0}{\sum}} x_{j} w_{N}^{jk}. $$

이를 ket의 관점에서 해석할 수 있다.

$$ \left| j \right\rangle \mapsto {1 \over \sqrt{N}} \overset{N-1}{\underset{k=0}{\sum}} w_{N}^{jk} \left| k \right\rangle. $$

이를 행렬로 표현하면,

$$ U_{QFT} = {1 \over \sqrt{N}} \overset{N-1}{\underset{j=0}{\sum}} \overset{N-1}{\underset{k=0}{\sum}} w_{N}^{jk}\left| k \right\rangle \left\langle j \right|. $$

 

$U_{QFT}$가 뭔지도 알았으니 본격적으로 ket에 QFT 연산자를 가해보자. 우선 $n$개의 qubit들을 가정하자. 그럼 총 $N=2^{n}$의 상태가 존재할 것이다. 이때 우리는 이진법의 표현을 차용할 것이다. $\left| x \right\rangle = \left|x_{1}x_{2} \cdots x_{n} \right\rangle$.

$ U_{QFT, N} \left| x \right\rangle = {1 \over \sqrt{N}} \overset{N-1}{\underset{y=0}{\sum}} w_{N}^{xy} \left| y \right\rangle $

$ \qquad \qquad \quad = {1 \over \sqrt{N}} \overset{N-1}{\underset{y=0}{\sum}} e^{2 \pi ixy/2^{n}} \left| y \right\rangle $

$ \qquad \qquad \quad = {1 \over \sqrt{N}} \overset{N-1}{\underset{y=0}{\sum}} e^{2 \pi ix(\sum_{k=1}^{n} y_{k}/2^{n})/2^{n}} \left| y_{1} \cdots y_{n} \right\rangle $

$ \qquad \qquad \quad = {1 \over \sqrt{N}} \overset{N-1}{\underset{y=0}{\sum}} \overset{n}{\underset{k=1}{\prod}} e^{2 \pi ixy_{k}/2^{n}} \left| y_{1} \cdots y_{n} \right\rangle $

$ \qquad \qquad \quad = {1 \over \sqrt{N}} \overset{n}{\underset{k=1}{\bigotimes}} \left( \left| 0 \right\rangle + e^{2 \pi ix/2^{k}} \left| 1 \right\rangle \right) $

$ \qquad \qquad \quad = {1 \over \sqrt{N}} \left( \left| 0 \right\rangle + e^{{2 \pi i \over 2^{1}} x} \left| 1 \right\rangle \right) \otimes \left( \left| 0 \right\rangle + e^{{2 \pi i \over 2^{2}} x} \left| 1 \right\rangle \right) \otimes \cdots \otimes \left( \left| 0 \right\rangle + e^{{2 \pi i \over 2^{n}} x} \left| 1 \right\rangle \right). $

 

이러한 상태를 만들기 위해서는 2가지 종류의 게이트가 필요하다. 첫째는 우리가 이미 알고 있던 Hadamard gate이다. 두 번째는 새롭게 정의되는 two-qubit controlled rotation, $CROT_{k}$이다.

$$ H \left| x_{k} \right\rangle = {1 \over \sqrt{2}} \left( \left| 0 \right\rangle + e^{{2 \pi i \over 2} x_{k}} \left| 1 \right\rangle \right). $$

$$ CROT_{k} = \begin{pmatrix} I & O \\ O & UROT_{k} \end{pmatrix} $$

where

$$ UROT_{k} = \begin{pmatrix} 1 & 0 \\ 0 & e^{{2 \pi i \over 2^{k}}} \end{pmatrix}. $$

 

이후 위와 같은 gate operation을 순차적으로 가한다. 차근차근 따라가 보자.

1. Qubit 1에 Hadamard gate를 가한다.

$$ \left| \psi_{1} \right\rangle = H_{1} \left| x_{1} \cdots x_{n} \right\rangle = {1 \over \sqrt{2}} \left[ \left| 0 \right\rangle + exp \left( {2 \pi i \over 2^{1}} x_{1} \right) \left| 1 \right\rangle \right] \otimes \left| x_{2} \cdots x_{n} \right\rangle $$

2. $UROT_{2}$ gate를 가한다.

$$ \left| \psi_{2} \right\rangle = H_{1} \left| x_{1} \cdots x_{n} \right\rangle = {1 \over \sqrt{2}} \left[ \left| 0 \right\rangle + exp \left( {2 \pi i \over 2^{2}} x_{2} + {2 \pi i \over 2^{1}} x_{1} \right) \left| 1 \right\rangle \right] \otimes \left| x_{2} \cdots x_{n} \right\rangle $$

3. $UROT_{n}$까지 가한다.

$$ \left| \psi_{3} \right\rangle = H_{1} \left| x_{1} \cdots x_{n} \right\rangle = {1 \over \sqrt{2}} \left[ \left| 0 \right\rangle + exp \left( {2 \pi i \over 2^{n}} x_{n} + \cdots + {2 \pi i \over 2^{2}} x_{2} + {2 \pi i \over 2^{1}} x_{1} \right) \left| 1 \right\rangle \right] $$$$\otimes \left| x_{2} \cdots x_{n} \right\rangle = {1 \over \sqrt{2}} \left[ \left| 0 \right\rangle + exp \left( {2 \pi i \over 2^{n}} x \right) \left| 1 \right\rangle \right] \otimes \left| x_{2} \cdots x_{n} \right\rangle$$

4. 다른 control에 대해서도 유사한 gate operation을 가한다.

$$ \left| \psi_{4} \right\rangle = {1 \over \sqrt{2}} \left[ \left| 0 \right\rangle + exp \left( {2 \pi i \over 2^{n}} \right) \left| 1 \right\rangle \right] \otimes {1 \over \sqrt{2}} \left[ \left| 0 \right\rangle + exp \left( {2 \pi i \over 2^{n-1}} x \right) \left| 1 \right\rangle \right] \otimes \cdots $$$$\otimes {1 \over \sqrt{2}} \left[ \left| 0 \right\rangle + exp \left( {2 \pi i \over 2^{1}} x \right) \left| 1 \right\rangle \right] $$

이는 $U_{QFT}$를 가해서 얻을 결과와 순서만 다를 뿐 완전히 동일한 결과이다. 이로써 우리는 QFT를 Hadamard, $CROT_{k}$ 단 2개만의 gate들을 조합해 수행할 수 있게 되었다!