Grover 알고리즘에 대한 설명

이 섹션에서는 Grover 알고리즘을 설명합니다. 먼저 위상 쿼리 Gate와 그것을 어떻게 구성하는지 논의한 다음, Grover 알고리즘 자체의 설명으로 넘어갑니다. 마지막으로 이 알고리즘이 탐색에 자연스럽게 어떻게 적용되는지 간단히 논의합니다.

위상 쿼리 Gate

Grover 알고리즘은 위상 쿼리 Gate로 알려진 연산을 사용합니다. 주어진 함수 $f$에 대해 앞서 설명한 일반적인 방식으로 정의되는 보통의 쿼리 Gate $U_f$와 달리, 함수 $f$에 대한 위상 쿼리 Gate는 다음과 같이 정의됩니다.

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

모든 문자열 $x\in\Sigma^n$에 대해서 말입니다.

연산 $Z_f$는 다음 다이어그램이 시사하는 것처럼 하나의 쿼리 Gate $U_f$를 사용하여 구현할 수 있습니다.

이 구현은 위상 킥백(phase kickback) 현상을 활용하며, $\vert -\rangle$ 상태로 초기화된 하나의 작업공간 Qubit이 준비되어 있어야 합니다. 이 Qubit은 구현이 완료된 후에도 $\vert - \rangle$ 상태를 유지하며, (예를 들어 이후의 $Z_f$ Gate를 구현하기 위해) 재사용하거나 그냥 버릴 수 있습니다.

연산 $Z_f$ 외에도, 각 문자열 $x\in\Sigma^n$에 대해 다음과 같이 정의되는 $n$-비트 OR 함수에 대한 위상 쿼리 Gate도 사용할 것입니다.

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

명시적으로, $n$-비트 OR 함수에 대한 위상 쿼리 Gate는 다음과 같이 작동합니다.

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}$$

명확히 하자면, 이것은 $Z_{\mathrm{OR}}$이 표준 기저 상태에 어떻게 작용하는지를 나타내며, 임의의 상태에 대한 동작은 선형성에 의해 이 식으로부터 결정됩니다.

연산 $Z_{\mathrm{OR}}$은, OR 함수에 대한 Boolean Circuit으로부터 시작하여 양자 알고리즘 기초 레슨에서 설명한 절차를 사용하여 $U_{\mathrm{OR}}$ 연산($n$-비트 OR 함수에 대한 표준 쿼리 Gate)을 구성하고, 마지막으로 위에서 설명한 위상 킥백 현상을 사용하여 $Z_{\mathrm{OR}}$ 연산을 구성함으로써 양자 Circuit으로 구현할 수 있습니다. 연산 $Z_{\mathrm{OR}}$은 함수 $f$에 의존하지 않으며, 따라서 쿼리 Gate가 없는 양자 Circuit으로 구현될 수 있음을 주목하세요.

알고리즘에 대한 설명

이제 두 연산 $Z_f$와 $Z_{\mathrm{OR}}$을 가지고 있으므로, Grover 알고리즘을 설명할 수 있습니다.

알고리즘은 수행하는 반복(iteration) 횟수(따라서 함수 $f$에 대해 필요한 쿼리 횟수)인 수 $t$를 참조합니다. 이 수 $t$는 우리가 설명하는 Grover 알고리즘에서 지정되지 않으며, 레슨의 뒷부분에서 어떻게 선택할 수 있는지 논의할 것입니다.

Grover 알고리즘

1. $n$개 Qubit 레지스터 $\mathsf{Q}$를 모두 영인 상태 $\vert 0^n \rangle$으로 초기화한 다음 $\mathsf{Q}$의 각 Qubit에 Hadamard 연산을 적용합니다.
2. 레지스터 $\mathsf{Q}$에 유니터리 연산 $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$를 $t$번 적용합니다.
3. $\mathsf{Q}$의 Qubit들을 표준 기저 측정으로 측정하고 얻어진 문자열을 출력합니다.

2단계에서 반복되는 연산 $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$를 이 레슨의 나머지 전체에서 Grover 연산이라고 부를 것입니다. 다음은 $n=7$일 때 Grover 연산의 양자 Circuit 표현입니다.

이 다이어그램에서 $Z_f$ 연산은 $Z_{\mathrm{OR}}$보다 크게 그려져 있는데, 이는 더 비용이 많이 드는 연산일 가능성이 높다는 것을 암시하는 비공식적인 시각적 단서입니다. 특히 쿼리 모델 내에서 작업할 때 $Z_f$는 하나의 쿼리를 필요로 하지만 $Z_{\mathrm{OR}}$은 쿼리를 필요로 하지 않습니다. 대신 함수 $f$에 대한 Boolean Circuit을 가지고 있고 이를 $Z_f$에 대한 양자 Circuit으로 변환한다면, 결과 양자 Circuit이 $Z_{\mathrm{OR}}$에 대한 것보다 더 크고 복잡할 것이라고 합리적으로 예상할 수 있습니다.

다음은 $n=7$이고 $t=3$일 때 전체 알고리즘에 대한 양자 Circuit의 다이어그램입니다. 더 큰 $t$ 값에 대해서는 측정 바로 앞에 Grover 연산의 추가 인스턴스를 단순히 삽입할 수 있습니다.

탐색에의 응용

Grover 알고리즘은 Search 문제에 다음과 같이 적용될 수 있습니다.

• 2단계에서 수 $t$를 선택합니다. (이에 대해서는 레슨의 뒷부분에서 논의합니다.)
• 우리가 선택한 $t$ 값을 사용하여 함수 $f$에 대해 Grover 알고리즘을 실행하여 문자열 $x\in\Sigma^n$을 얻습니다.
• 문자열 $x$에 대해 함수 $f$를 쿼리하여 그것이 유효한 해인지 확인합니다.
  • 만약 $f(x) = 1$이면, 해를 찾았으므로 중단하고 $x$를 출력할 수 있습니다.
  • 그렇지 않고 $f(x) = 0$이면, 다른 $t$ 값을 선택하여 절차를 다시 실행하거나, 포기하고 "해 없음"을 출력할 수 있습니다.

Grover 알고리즘이 어떻게 작동하는지 분석하고 나면, $t = O(\sqrt{N})$을 택함으로써 (해가 존재한다면) 높은 확률로 탐색 문제의 해를 얻는다는 것을 보게 될 것입니다.