비구조적 탐색

요약

Grover 알고리즘이 해결하는 문제에 대한 설명부터 시작하겠습니다. 평소처럼, 이 논의 전체에서 $\Sigma = \{0,1\}$이 이진 알파벳을 나타내도록 하겠습니다.

이제

$$f:\Sigma^n \rightarrow \Sigma$$

가 길이 $n$인 이진 문자열에서 비트로의 함수라고 합시다. 이 함수를 효율적으로 계산할 수 있다고 가정하지만, 그 외에는 임의적이며 우리의 필요에 맞는 특별한 구조나 구체적인 구현에 의존할 수 없습니다.

Grover 알고리즘이 하는 일은 $f(x) = 1$인 문자열 $x\in\Sigma^n$을 탐색하는 것입니다. 이러한 문자열을 탐색 문제의 *해(solution)*라고 부르겠습니다. 해가 여러 개 있다면, 그중 어느 하나라도 올바른 출력으로 간주되며, 해가 없다면 올바른 답으로 해가 없음을 알려야 합니다.

이 작업은 비구조적 탐색 문제로 설명되는데, 이는 $f$가 쉬워지도록 만드는 특정한 구조를 가지고 있다고 가정할 수 없기 때문입니다. 정렬된 목록이나 탐색을 용이하게 하도록 특별히 설계된 어떤 데이터 구조 내에서 탐색하는 것이 아니라, 본질적으로 건초더미 속에서 바늘을 찾는 것과 같습니다.

직관적으로 말하자면, $f$를 계산하는 매우 복잡한 Boolean Circuit이 있고, 원한다면 선택한 입력 문자열에 대해 이 Circuit을 쉽게 실행할 수 있다고 상상할 수 있습니다. 그러나 Circuit이 너무 복잡하기 때문에, (선택한 입력 문자열에서 Circuit을 평가할 수 있는 능력을 넘어서는) Circuit을 살펴봄으로써 이해할 가능성은 없습니다.

이 탐색 작업을 고전적으로 수행하는 한 가지 방법은 단순히 모든 문자열 $x\in\Sigma^n$을 순회하면서 각각에 대해 $f$를 평가하여 해인지 아닌지 확인하는 것입니다. 이후로는 편의상

$$N = 2^n$$

이라고 쓰겠습니다. $\Sigma^n$에는 $N$개의 문자열이 있으므로, 모두 순회하려면 $f$를 $N$번 평가해야 합니다. 선택한 입력에서 $f$를 평가하는 것에 국한되어 있다는 가정하에, 성공을 보장하고자 한다면 결정론적 알고리즘으로 할 수 있는 최선은 이것입니다. 확률적 알고리즘을 사용하면 $f$의 입력 문자열을 무작위로 선택하여 시간을 절약하기를 바랄 수 있지만, 이 방법이 높은 확률로 성공하기를 원한다면 여전히 $f$에 대한 $O(N)$번의 평가가 필요합니다.

Grover 알고리즘은 $f$에 대한 $O(\sqrt{N})$번의 평가만으로 높은 확률로 이 탐색 문제를 해결합니다. 명확히 하자면, 이러한 함수 평가는 Deutsch 알고리즘, Deutsch-Jozsa 알고리즘, Simon 알고리즘을 포함하여 양자 쿼리 알고리즘 레슨에서 논의된 쿼리 알고리즘과 유사하게 중첩 상태에서 이루어져야 합니다. 이러한 알고리즘과는 달리, Grover 알고리즘은 반복적 접근 방식을 취합니다. 즉, 입력 문자열의 중첩 상태에서 $f$를 평가하고, 이러한 평가 사이에 간섭 패턴을 만드는 효과가 있는 다른 연산을 끼워 넣어, $O(\sqrt{N})$번의 반복 후에 (해가 존재한다면) 높은 확률로 해를 찾게 됩니다.

형식적 문제 설명

Grover 알고리즘이 해결하는 문제를 계산의 쿼리 모델을 사용하여 형식화하겠습니다. 즉, 함수 $f:\Sigma^n\rightarrow\Sigma$에 평소와 같이 정의된 쿼리 Gate를 통해 접근할 수 있다고 가정합니다.

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

모든 $x\in\Sigma^n$과 $a\in\Sigma$에 대해서 말입니다. 이것은 표준 기저 상태에서의 $U_f$의 동작이며, 일반적인 동작은 선형성에 의해 결정됩니다.

양자 알고리즘 기초 레슨에서 논의된 바와 같이, $f$를 계산하는 Boolean Circuit이 있다면, 해당 Boolean Circuit의 설명을 ($\vert 0\rangle$ 상태로 계산을 시작하고 끝내는 몇 개의 작업공간 Qubit을 사용하여) $U_f$를 구현하는 양자 Circuit으로 변환할 수 있습니다. 따라서 Grover 알고리즘이 해결하는 문제를 형식화하기 위해 쿼리 모델을 사용하고 있지만, 이 모델에 국한되지 않습니다. 즉, Boolean Circuit이 있는 모든 함수 $f$에 대해 Grover 알고리즘을 실행할 수 있습니다.

다음은 문제에 대한 정확한 설명이며, 해를 찾고 있기 때문에 Search라는 이름이 붙었습니다. 여기서 해란 $f$가 $1$로 평가되도록 하는 문자열 $x$를 의미합니다.

Search

입력: 함수 $f:\Sigma^n\rightarrow\Sigma$
출력: $f(x) = 1$을 만족하는 문자열 $x\in\Sigma^n$, 또는 그러한 문자열 $x$가 존재하지 않는 경우 "해 없음"

이것이 약속 문제(promise problem)가 아님을 주목하세요. 함수 $f$는 임의적입니다. 그러나 정확히 하나의 해가 있다는 것이 보장되는, 문제의 다음과 같은 약속 변형을 고려하는 것이 유용할 것입니다. 이 문제는 양자 쿼리 알고리즘 레슨에서 약속 문제의 예로 등장했습니다.

Unique search

입력: $f:\Sigma^n \rightarrow \Sigma$ 형태의 함수
약속: $f(z) = 1$인 문자열 $z\in\Sigma^n$이 정확히 하나 존재하며, $z$가 아닌 모든 문자열 $x$에 대해 $f(x) = 0$
출력: 문자열 $z$

또한 같은 레슨에서 언급된 Or 문제가 Search와 밀접하게 관련되어 있음을 주목하세요. 그 문제의 목표는 해를 실제로 찾는 것이 아니라, 단순히 해가 존재하는지 여부를 결정하는 것입니다.