Quantum Algorithm #3

5. Grover Algorithm

Grover Algorithm은 인도 컴퓨터공학자 Grover에 의해 제시된 알고리즘으로 $N$개의 박스 속에서 원하는 자료를 찾는 알고리즘이다. 전체적인 회로는 모든 상태를 중첩시키고, 원하는 상태를 뒤집고, 이를 증폭시키는 3개의 과정을 거친다. 차근차근 알아보자.

1. Step 1: State Preparation

총 상태는 $n$개의 qubits가 중첩된 $\left| s \right\rangle$이고, 정답은 하나의 qubit인 $\left| w \right\rangle$ 이고 오답들은 $n-1$개의 qubits가 중첩된 $\left| s' \right\rangle$로 표현할 수 있다. 또, 이를 RLC 위상을 표현하듯이 2차원 평면에 표현할 수 있다. 

2. Step 2: Grover's Oracle

Grover's oracle$(U_{f})$을 이용해 정답이 든 박스의 위상만을 뒤집는다. 이는 아래와 같은 행렬로 표현할 수 있다.

$$ U_{f} = \mathbb{I} - 2 \left| w \right\rangle \left\langle w \right|. $$

$$ \Rightarrow U_{f} \left| s \right\rangle = \left| s \right\rangle - {2 \over \sqrt{N}} \left| w \right\rangle. $$

3. Step 3: Diffusion Operator 

이후 $ U_{s} = 2 \left| s \right\rangle \left\langle  s \right| - \mathbb{I} $를 가한다. 

$$ U_{s}U_{f} \left| s \right\rangle = {{N-4} \over N } \left| s \right\rangle + {2 \over \sqrt{N}} \left| w \right\rangle. $$

우리는 이 결과로부터 우리가 원하는 정답인 $\left| w \right\rangle$의 확률 진폭이 증가된 사실을 확인할 수 있다. 이를 여러 번 반복하면 최종 상태 벡터가 $\left| w \right\rangle$에 더 가까이 갈 것이기 때문에 더욱 높은 확률을 얻을 수 있다. 이러한 반복을 t번 수행했을 때 상태 벡터는 다음과 같다. 

$$ \left| \psi_{t} \right\rangle  = (U_{s}U_{f})^{t} \left| s \right\rangle. $$

다만, 과한 반복을 수행했을 경우 $\left| w \right\rangle$을 지나칠 수 있기 때문에 적절한 반복이 요구된다. 적절한 반복 횟수는 다음과 같이 알려져 있다. 

$$ t_{appropriate} = {\pi \over 4} \sqrt{N}. $$

이게 뭐 중요한가... 자명하지 않을까... 아니면 너무 어렵지 않을까 싶어서 증명 안하려고 했는데 시험에 깜빡 나와버렸다. 당황해서 증명 못했다ㅋㅋㅋ 한 번만 풀어봤어도 증명할수 있었던 건데... 역시 시험은 공부한 만큼 치는게 맞다. 그럼 증명해보자. 별로 안어렵다.

우선 처음에 Hadamard에서 $\theta$만큼의 phase가 생긴다. 그리곤 orcale에서 $-\theta$만큼 뒤집하고, diffuser에서 다시 뒤집혀 $2\theta$가 추가된다. 이제 한 사이클 끝났고 총 $3\theta$ 회전했다. 두 번째 사이클은 $3\theta$가 뒤집혀서 $-3\theta$가 되고, 다시 뒤집히고 $2\theta$가 추가된다. 그래서 답은 $5\theta$이다. 그 다음은 $7\theta$. 이렇게 반복했을 때, 총 $t$회 Grover's move$($Oracle+Diffuser$)$를 반복했을 때, phase는 

$$ \theta_{t} = (2t+1) \theta $$

이다. 우리가 원하는 것은 $\theta_{t} = {\pi \over 2}$를 만족하는 $t$ 이다. 따라서

$$ t = {\pi/2 \over 2 \theta} - {1 \over 2}. $$

이때 $sin(\theta) = 1/\sqrt{N} \Rightarrow \theta \cong 1/\sqrt{N}$이므로,

$$ t \cong {\pi \over 4 }\sqrt{N} - { 1 \over 2 } \cong {\pi \over 4 }\sqrt{N}. $$

이때 $t$는 정수이므로 가우스 기호를 씌워주면 위에서 구한 $t_{appropriate}$를 구할 수 있다. 끝~

---

이제 gate들을 조합해서 회로까지 만들어 유의미한 양자 연산들까지 해보았다. 하지만 배웠던 5개의 연산들은 기초 중에 기초가 되는 연산이기 때문에 더욱 더 많은 공부가 필요해 보인다. 이번 강의를 통해 블로그에 포스팅하지는 않았지만 초전도체를 이용한 양자 연산, 이온 트랩 양자 연산을 배웠고 해당 시스템에서 수행 가능한 게이트 연산들을 기반으로 하여 양자 알고리즘들까지 몇 개 배워보았다. 강의를 듣기 전에는 양자컴퓨터가 뭔지 대중적인 수준에서만 이해하고 있었는데, 가볍게나마 양자컴퓨터가 무엇인지 물리학적으로 전공생의 관점에서 바라볼 수 있었던 것 같다. 

과거의 반도체 산업은 무어의 법칙이 적용되어 기하급수적인 발전을 이뤘다. 하지만 이제는 몇 나노 공정까지 내려갔기 때문에 양자역학적인 효과를 고려하지 않을 수 없다. 이미 양자역학적인 효과는 누설 전류와 같이 반도체에도 적용되고 있다. 이런 측면에서 양자컴퓨터의 붐은 오지 않을까 싶긴 하다. 하지만 나도 잘은 모르지만 아직도 여전히 높은 error 때문에 붐이 올까 싶기도 하다. 차라리 삼진법 컴퓨터가 더 실현가능해 보이긴 한다. 그런데도 양자컴퓨터와 관련된 연구는 최근에도 활발히 이루어지는 것 같다. 양자컴퓨터를 이용해서 머신러닝을 하는 quantum support vector machine도 있고, 양자컴퓨터를 이용해서 기상현상을 예측하는 모델이 qiskit 해커톤에서 우승을 하기도 했다. 이런 걸 보면 양자컴퓨터 시대가 올 것 같기도 하다. 

뭐 양자컴퓨터의 시대가 오든 오지 않든 나는 양자역학 쪽에 이미 발을 들였고, 이제 근 5년 간은 이 선택을 돌이킬 수 없다. 그러니 도 닦는 기분으로 믿고 열심히 앞으로 더 공부해 봐야겠다.