Grover Algorithm
Grover 알고리즘은 데이터베이스에서 특정조건을 만족하는 항목을 찾는 양자 알고리즘이다. 데이터베이스가 구조화되어있는 경우 고전적 알고리즘으로 비교적 빠른 찾기가 가능하다. 그러나 구조화되지 않은 데이타베이스에서 원하는 항목을 찾는 경우 데이타베이스의 항목의 수가 N이라 할때 피요한 찾기의 수는 평균적으로 N/2가 되고 더이상 단축할 수가 없다. Grover알고리즘은 root-N의 찾기로 N개의 항목에서 원하는 항목을 찾을수 있다. 수학적으로 데이터베이스는 {1,2,,,,N} 의 정의역을 갖는 함수 f(x)의 표로 구성된다. 본 논의에서는 일단 함수f(x)는 일대일 함수라 한정한다. 우리의 목적은 주어진 값 a에 대해 f(x)=a를 만족하는 x를 찾는 것이다.
Oracle
oracle은 주어진 input에 대해 0 또는 1의 output을 주는 일종의 blackbox이다. oracle은 입력된 항목 x가 f(x)=a 를 만족하면 1을 출력하고 그렇지 않으면 0을 출력한다.즉 다음과같다.
여기서 w(혹은|W>)는 찾고자 하는 항목을 나타낸다. 즉f(w)=a이다. oracle의 출력결과를 통해 입력항목이 찾고자 하는 항목인지의 여부를 가릴 수 있다.
Grover Iteration
연산을 시작하기 앞서 상태벡터를 초기화해주는 것이 필요한데 보통은 |00,,,00>으로 초기화되고 본 논의에서도 이를 따른다. Grover 알고리즘은 크게 세가지 연산으로 수행된다.첫번째 필요한 연산이 Hadamard연산으로 초기화된 상태벡터를 다음과 같이 변환한다.
Grover 알고리즘에서는 oralce의 출력이 약간 수정되어 다음과 같은 입력에 대한 출력을 갖는다.
이 연산은 찾고자 하는 항목에 해당하는 비트의 phase를 바꾸어주므로 phase rotation transformation이라 불리우며 두번째 연산과정이다. 이 연산의 한 특징은 주어진 상태벡터의 |W>방향 성분을 |W>에 수직한 평면에 대해 반전시키는 작용을 한다는 것이다.
마지막으로 다음과 같은 연산을 생각하자.
임의의 상태벡터에 |Q>대한 이 연산의 성질을 살펴보자. |Q>를 다음과 같이 고유벡터의 중첩으로 나타낼수 있다.
여기에 연산을 가하면 다음과 같다.
즉 이 연산은 상태벡터를 고유벡터의중첩으로 나타낼 때 각 고유벡터의 계수를 계수의 평균에 대해 반전시키는 작용을 한다. 이런 의미에서 이 연산을 평균에 대한 반전 연산 (inversion about average operation)라 부른다. 이 연산의 한 특징은 상태벡터의 |S>에 수직한 성분을 |S>를 축으로 반전시킨다는 것이다.
Grover Iteration은 다음과 같이 두 연산의 곱으로 주어진다.
각 쎄타를 다음과 같이 정의한다.
이때 Grover Iteration은 상태벡터를 |S>와 |W>로 이루어진 평면상에서 |W>쪽에서 |S>쪽으로 2쎄타만큼 회전시키는 역할을 한다.
Finding 1 out of 4
4개의 항목중에 원하는 한 항목을 찾는 방법을 살펴보자. 이 경우 위에서 정의된 쎄타는 30"가 된다. 결국 |S>에 대해 Grover Iteration을 하면 |S>가 |W>쪽으로 60"회전하게 되어 |W>가 된다. 즉 다음이 성립한다.
이상에서 단 한번의 oracle에 대한 물음으로 원하는 항목을 찾아내게 된다.
Finding N out of 4N
4개의 항목중 하나의 항목을 찾는 과정에 약간의 수정을 거치면 4N개의 항목중 N항목을 찾는 알고리즘이 얻어진다.조건을 만족하는 항목의 집합을 F라 할 때 oracle의 출력은 다음과 같다.
이 oracle에 의해 행해지는 연산을 다음과 같이 수정할 수 있다.
여기서 |Wi>는 찾고자 하는 항목을 나타낸다. 이렇게 수정된 phase rotation transformation을 이용하여 Grover Iteration을 수행하면 다음의 과정을 거쳐 최종 상태벡터는 원하는 항목들만의중첩이 된다.
맺는말
위의 두가지 경우 이외에도 N개의 항목에서 하나의 항목을 찾는 문제,N개의항목에서 r(r이 N보다 매우 작은 경우)개의 항목을 찾는 문제, 데이타베이스가 약간의 구조를 갖는 경우의 찾기 문제등이 연구되었다. 서울대의 지동표교수는 4N개의 항목중 N개 이상의 항목을 찾는 경우 한번의 일반화된 Grover Iteration으로 원하는 항목을 항상 찾을수 있음을 보이기도 했다.4개중에 하나의 항목을 찾는 문제는 2-bit nmr컴퓨터로 실험적으로도 구현되었다.