[양자컴퓨팅] Grover's Algorithm 정리

여러가지 데이터에서 특정한 조건을 만족하는 항목을 찾을 때 우리는 하나하나 열어보면서 열어본 항목이 우리가 원하는 답인지를 비교해야한다. 즉 순차적으로 탐색하였을 경우에 시간복잡도는 O(N)이다. 고전컴퓨터의 이러한 탐색에서 벗어나 시간복잡도를 O(√N)로 낮추면서 원하는 답을 얻어내는 알고리즘인 그로버 알고리즘이 등장한다. 그로버알고리즘이 어떤식으로 search를 하는지 알아보자. 

 

😊그로버 알고리즘의 원리

1. Phase Inversion

큐빗이 두개일때 중첩상태를 그림으로 나타내면 다음과 같다. 00, 01, 10, 11이 나올수 있는 확률이 1/4로 동일하게 관측된다.

 

이 상태에서 우리가 찾고자하는 항목이 01에 있다고 한다면 우리는 01이 나오는 확률을 축에 반대로 표시한다. 이것을 Phase inversion이라 한다. 결국에 양자상태는 01에 대해서만 (-)로 나타내어진다.

 

 

2. Inversion about the Mean

phase inversion이 끝났다면 네개의 양자상태가 관측될 수 있는 확률의 평균을 구한다.(빨간 선) 

 

평균값에 대해서 다시 inversion을 취해주면 01에 대해서만 높은 확률로 관측되게 된다. 이 과정을 반복하다보면 우리가 원하는 답인 01에 대해서 1에 가까운 확률이 존재하게 되고 나머지는 거의 0에 수렴하는 값이 나오게 되는데, 바로 이것이 그로버 알고리즘의 원리이다. 

 

 

😊 Quantum Circuit으로 표현한 그로버 알고리즘

 

결론적으로 그로버알고리즘을 회로로 나타내면 위의 그림과 같다. n개의 큐빗을 0으로 놓고 마지막 큐빗을 1로 정한 상태에서 회로에 넣는다. 0을 H gate에 넣어서 모든 중첩상태에 대해서 동등한 확률을 갖는 state로 만든다. 그 다음에 phase inversion을 통해서 우리가 원하는 값의 phase를 180도로 변경한다. Phase inversion단계가 끝나면 첫번째 state를 가지고 평균에 대해서 역을 구하는 단계로 이어진다. 이 과정을 반복해서 첫번째 값을 측정하면 우리가 원하는 답을 찾을 수 있다.