계산의 쿼리 모델

수학적인 용어로 계산을 모델링할 때, 우리는 일반적으로 다음 그림과 같은 프로세스를 염두에 둡니다. 정보가 입력으로 제공되고, 계산이 이루어지며, 출력이 생성됩니다.

오늘날 우리가 사용하는 컴퓨터는 지속적으로 입력을 받고 출력을 생성하며, 본질적으로 우리와 다른 컴퓨터 모두와 상호작용하는데, 이는 그림에 반영된 방식과는 다릅니다. 하지만 이 그림의 의도는 컴퓨터의 지속적인 작동을 표현하는 것이 아닙니다. 오히려, 이는 개별적인 계산 작업에 초점을 맞춘 계산의 간단한 추상화를 만들기 위한 것입니다. 예를 들어, 입력은 숫자, 벡터, 행렬, 그래프, 분자에 대한 설명, 또는 더 복잡한 것을 인코딩할 수 있으며, 출력은 우리가 염두에 둔 계산 작업의 해결책을 인코딩합니다.

핵심은 입력이 계산에 제공되며, 일반적으로 이진 문자열의 형태이고, 그 어떤 부분도 숨겨져 있지 않다는 점입니다.

모델에 대한 설명

계산의 쿼리 모델(query model) 에서는, 위에서 제시한 보다 표준적인 모델과 달리 전체 입력이 계산에 제공되지 않습니다. 대신, 입력은 함수(function) 의 형태로 제공되며, 계산은 쿼리(query) 를 수행함으로써 그것에 접근합니다. 또는, 쿼리 모델에서의 계산을 입력의 비트(또는 비트의 구간)에 대한 임의 접근 을 갖는 것으로 볼 수도 있습니다.

쿼리 모델의 맥락에서는 입력을 오라클(oracle) 또는 블랙박스(black box) 가 제공한다고 자주 표현합니다. 두 용어 모두 입력의 완전한 설명이 계산으로부터 숨겨져 있고, 접근할 수 있는 유일한 방법은 질문을 던지는 것이라는 점을 암시합니다. 마치 델포이의 오라클에게 입력에 대해 자문을 구하는 것과 같습니다. 그녀는 자신이 아는 모든 것을 말해주지 않으며, 구체적인 질문에만 답할 뿐입니다. 블랙박스 라는 용어는 특히 입력이 함수로 표현된다고 생각할 때 이해가 됩니다. 우리는 함수 내부를 들여다보고 그것이 어떻게 작동하는지 이해할 수 없으며, 단지 우리가 선택한 인수에 대해 평가할 수 있을 뿐입니다.

이번 수업에서는 다른 기호를 포함하는 문자열이 아니라 이진 문자열만을 다룰 것이므로, 편의상 앞으로 이진 알파벳을 나타내기 위해 $\Sigma = \{0,1\}$ 라고 표기하겠습니다. 우리는 다양한 계산 문제들을 다룰 것이며, 몇 가지 간단한 예시는 곧 설명하겠지만, 그 모든 문제에서 입력은 다음과 같은 형태의 함수로 표현될 것입니다.

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

여기서 $n$ 과 $m$ 은 양의 정수입니다. 물론 $f$ 대신 다른 이름을 선택할 수도 있지만, 이번 수업 전반에 걸쳐 $f$ 를 그대로 사용하겠습니다.

계산이 쿼리 를 수행한다는 것은 어떤 문자열 $x \in \Sigma^n$ 이 선택되고, 그러면 문자열 $f(x)\in\Sigma^m$ 이 오라클에 의해 계산에 제공된다는 것을 의미합니다. 이것이 양자 알고리즘에서 정확히 어떻게 작동하는지는 곧 논의할 것입니다. 이것은 쿼리가 중첩 상태에서 수행될 수 있도록 하는 유니타리 양자 연산으로 수행이 가능해야 하는데, 우선은 직관적으로 높은 수준에서 생각해 볼 수 있습니다.

마지막으로, 쿼리 알고리즘의 효율성을 측정하는 방식은 간단합니다. 우리는 알고리즘이 필요로 하는 쿼리의 수(number of queries) 를 셉니다. 이는 계산을 수행하는 데 필요한 시간과 관련이 있지만 정확히 같지는 않습니다. 왜냐하면 쿼리 이외의 연산에 드는 시간은 무시하고, 또한 각 쿼리가 단위 비용을 갖는 것처럼 취급하기 때문입니다. 원한다면 쿼리 이외의 연산들을 고려할 수도 있지만(그리고 때로는 그렇게 하지만), 쿼리의 수에만 주목하는 것이 간단함을 유지하는 데 도움이 됩니다.

쿼리 문제의 예시

다음은 몇 가지 간단한 쿼리 문제의 예시입니다.

• OR. 입력 함수는 $f:\Sigma^n \rightarrow \Sigma$ 의 형태를 갖습니다(따라서 이 문제에서는 $m=1$ 입니다). 과제는 $f(x) = 1$ 을 만족하는 문자열 $x\in\Sigma^n$ 이 존재하면 $1$ 을 출력하고, 그런 문자열이 없으면 $0$ 을 출력하는 것입니다. 함수 $f$ 를 임의 접근이 가능한 $2^n$ 개의 비트 시퀀스를 나타내는 것으로 생각하면, 이 문제는 이 비트들의 OR을 계산하는 문제입니다.

• 패리티(Parity). 입력 함수는 다시 $f:\Sigma^n \rightarrow \Sigma$ 의 형태를 갖습니다. 과제는 $f(x) = 1$ 을 만족하는 문자열 $x\in\Sigma^n$ 의 수가 짝수(even) 인지 홀수(odd) 인지를 결정하는 것입니다. 정확히 말하면, 집합 $\{x\in\Sigma^n : f(x) = 1\}$ 의 원소 수가 짝수이면 $0$ 을, 홀수이면 $1$ 을 출력해야 합니다. 함수 $f$ 를 임의 접근이 가능한 $2^n$ 개의 비트 시퀀스를 나타내는 것으로 생각하면, 이 문제는 이 비트들의 패리티(즉, 배타적 OR)를 계산하는 문제입니다.

• 최솟값(Minimum). 입력 함수는 임의의 양의 정수 $n$ 과 $m$ 에 대해 $f:\Sigma^n \rightarrow \Sigma^m$ 의 형태를 갖습니다. 요구되는 출력은 $\Sigma^m$ 의 사전식(즉, 사전 순서) 순서에서 가장 먼저 오는 문자열 $y \in \{f(x) : x\in\Sigma^n\}$ 입니다. 함수 $f$ 를 임의 접근이 가능한, 길이 $m$ 의 이진 표기법 문자열로 인코딩된 $2^n$ 개의 정수 시퀀스를 나타내는 것으로 생각하면, 이 문제는 이 정수들의 최솟값을 계산하는 문제입니다.

또한 입력에 대한 약속(promise) 이 있는 쿼리 문제도 고려합니다. 이것이 의미하는 바는 입력에 대한 일종의 보장을 받으며, 이 보장이 충족되지 않을 때 일어나는 일에 대해서는 책임이 없다는 것입니다. 이런 유형의 문제를 설명하는 또 다른 방법은 일부 입력 함수(약속이 충족되지 않는 것들)를 "상관없음(don't care)" 입력으로 간주한다고 말하는 것입니다. "상관없음" 입력이 주어졌을 때 알고리즘에는 아무런 요구사항도 부과되지 않습니다.

다음은 약속이 있는 문제의 한 예시입니다.

• 유일 탐색(Unique search). 입력 함수는 $f:\Sigma^n \rightarrow \Sigma$ 의 형태를 가지며, $f(z) = 1$ 을 만족하는 문자열 $z\in\Sigma^n$ 이 정확히 하나 존재하고, $x\neq z$ 인 모든 문자열에 대해서는 $f(x) = 0$ 이라는 약속 이 주어집니다. 과제는 이 유일한 문자열 $z$ 를 찾는 것입니다.

방금 설명한 네 가지 예시는 모두 자연스러운 문제입니다. 즉, 설명하기 쉽고, 이들이 발생할 수 있는 다양한 상황이나 맥락을 상상할 수 있다는 의미에서 그렇습니다.

반면, 어떤 쿼리 문제들은 전혀 그런 식으로 "자연스럽지" 않습니다. 사실 쿼리 모델 연구에서는 실제로 누군가가 실용적으로 풀고 싶어 할 것이라고 상상하기 어려운, 매우 복잡하고 매우 인위적인 문제들을 종종 만들어냅니다. 하지만 그렇다고 해서 이 문제들이 흥미롭지 않다는 의미는 아닙니다! 처음에는 인위적이거나 부자연스러워 보일 수 있는 것들이 예기치 못한 단서를 제공하거나 새로운 아이디어에 영감을 줄 수 있습니다. 사이먼(Simon)의 알고리즘에서 영감을 받은, 인수분해를 위한 쇼어(Shor)의 양자 알고리즘이 훌륭한 예시입니다. 또한 극단적인 사례들을 찾는 것도 쿼리 모델 연구의 중요한 부분인데, 이는 양자 컴퓨팅의 잠재적 이점과 한계를 모두 밝히는 데 도움이 될 수 있습니다.

쿼리 Gate

회로로 계산을 설명할 때, 쿼리는 쿼리 Gate(query gates) 라고 불리는 특수한 Gate에 의해 수행됩니다.

고전 불리언 회로에 대해 쿼리 Gate를 정의하는 가장 간단한 방법은 다음 그림이 제시하는 것처럼, 이 Gate들이 입력 함수 $f$ 를 직접 계산하도록 단순히 허용하는 것입니다.

쿼리 문제를 위해 불리언 회로가 만들어지면, 입력 함수 $f$ 는 이러한 Gate들을 통해 접근되며, 회로가 수행하는 쿼리의 수는 단순히 회로에 등장하는 쿼리 Gate의 수입니다. 불리언 회로 자체의 입력 와이어는 고정된 값으로 초기화되며, 이는 (문제의 입력이 아니라) 알고리즘의 일부로 간주되어야 합니다.

예를 들어, 다음은 $f:\Sigma\rightarrow\Sigma$ 형태의 함수에 대해 위에서 설명한 패리티 문제를 푸는, 고전 쿼리 Gate를 가진 불리언 회로입니다.

이 알고리즘은 쿼리 Gate가 두 개이기 때문에 두 번의 쿼리를 수행합니다. 작동 방식은 함수 $f$ 를 두 가지 가능한 입력인 $0$ 과 $1$ 에 대해 쿼리하고, 그 결과를 XOR을 계산하는 불리언 회로에 입력하는 것입니다. (이 특정 회로는 Basics of quantum information 강좌의 Quantum circuits 수업에서 불리언 회로의 예시로 등장한 바 있습니다.)

양자 회로의 경우, 이러한 쿼리 Gate 정의는 작동하지 않습니다. 왜냐하면 이러한 Gate들은 함수 $f$ 의 일부 선택에 대해 비유니타리가 되기 때문입니다. 따라서 그 대신에 우리가 하는 일은, 다음 그림이 제시하는 것처럼 표준 기저 상태에 대해 작동하는 유니타리 쿼리 Gate(unitary query gates) 를 정의하는 것입니다.

여기서 우리의 가정은 $x\in\Sigma^n$ 과 $y\in\Sigma^m$ 이 임의의 문자열이라는 것입니다. $y\oplus f(x)$ 표기는 두 문자열의 비트별 배타적 OR(bitwise exclusive-OR) 을 나타내며, 이 경우 길이가 $m$ 입니다. 예를 들어, $001 \oplus 101 = 100$ 입니다.

직관적으로 말하자면, (임의의 선택된 함수 $f$ 에 대해) Gate $U_f$ 가 하는 일은 위쪽 입력 문자열 $x$ 를 그대로 출력하고, 함수 값 $f(x)$ 를 아래쪽 입력 문자열 $y$ 에 XOR하는 것이며, 이는 모든 함수 $f$ 의 선택에 대해 유니타리 연산입니다. 사실 이는 결정론적 연산이며, 자기 자신이 역연산이기도 합니다. 이는 행렬로서 $U_f$ 가 항상 순열 행렬(permutation matrix), 즉 각 행과 각 열에 단 하나의 $1$ 을 가지고 다른 모든 항목은 $0$ 인 행렬임을 의미합니다. 순열 행렬을 벡터에 적용하면 단순히 벡터의 항목들을 뒤섞는 것이므로(그래서 순열 행렬 이라는 용어가 쓰입니다), 그 벡터의 유클리드 노름을 바꾸지 않습니다. 이는 순열 행렬이 항상 유니타리임을 보여줍니다.

강조할 점은, 쿼리 알고리즘이 수행하는 쿼리의 수를 단순히 세어 쿼리 알고리즘을 분석할 때, 우리는 고전과 양자 버전 모두에 대해 쿼리 Gate를 물리적으로 구성하는 데 드는 어려움을 완전히 무시하고 있다는 것입니다. 직관적으로 말하자면, 쿼리 Gate의 구성은 해답을 찾는 일의 일부가 아니라 입력을 준비하는 일의 일부입니다.

이것이 불합리해 보일 수 있지만, 우리는 실용적인 컴퓨팅을 기술하거나 필요한 자원을 완전히 설명하려는 것이 아니라는 점을 명심해야 합니다. 오히려, 우리는 양자 컴퓨팅의 잠재적 이점을 밝히는 데 도움이 되는 이론적 모델을 정의하는 것입니다. 이 점에 대해서는 다음 수업에서 입력이 이진 문자열로 회로에 명시적으로 주어지는 보다 표준적인 계산 모델로 주의를 돌릴 때 더 할 말이 있을 것입니다.