사이먼 알고리즘

사이먼 알고리즘은 사이먼 문제로 알려진 문제를 푸는 양자 쿼리 알고리즘입니다. 이는 도이치-조자 문제나 번스타인-바지라니 문제와 비슷한 성격을 가진 약속(promise) 문제이지만, 세부 내용은 다릅니다.

사이먼 알고리즘은 양자 알고리즘이 고전(확률적 알고리즘 포함) 알고리즘에 비해 지수적 우위를 제공한다는 점에서 중요하며, 이 알고리즘에서 사용된 기법은 피터 쇼어가 정수 인수분해를 위한 효율적인 양자 알고리즘을 발견하는 데 영감을 주었습니다.

사이먼 문제

사이먼 문제의 입력 함수는 다음과 같은 형태를 취합니다.

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

여기서 $n$과 $m$은 양의 정수입니다. 단순화를 위해 $m = n$인 경우로 한정할 수도 있지만, 이 가정을 통해 얻을 수 있는 것은 거의 없습니다. 사이먼 알고리즘과 그 분석은 어느 쪽이든 기본적으로 동일합니다.

사이먼 문제

입력: 함수 $f:\Sigma^n \rightarrow \Sigma^m$
약속: 모든 $x,y\in\Sigma^n$에 대해 $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$를 만족하는 문자열 $s\in\Sigma^n$이 존재한다
출력: 문자열 $s$

약속의 내용을 곧 더 자세히 살펴보겠지만, 먼저 이 약속이 $f$에 매우 특별한 구조를 요구한다는 점을 명확히 해두겠습니다. 따라서 대부분의 함수는 이 약속을 만족하지 않습니다. 또한 이 문제가 실용적인 중요성을 갖기 위해 만들어진 것이 아니라는 점도 인정해야 합니다. 오히려 이 문제는 양자 컴퓨터에는 쉽고 고전 컴퓨터에는 어렵도록 인위적으로 설계된 문제입니다.

두 가지 주요 경우가 있습니다. 첫 번째 경우는 $s$가 전부 0으로 이루어진 문자열 $0^n$인 경우이고, 두 번째 경우는 $s$가 전부 0으로 이루어진 문자열이 아닌 경우입니다.

• 경우 1: $s=0^n.$ $s$가 전부 0인 문자열이면, 약속의 동치 조건을 단순화하여 $[f(x) = f(y)] \Leftrightarrow [x = y]$로 나타낼 수 있습니다. 이는 $f$가 단사 함수(일대일 함수)임과 동치입니다.

• 경우 2: $s\neq 0^n.$ $s$가 전부 0인 문자열이 아닌 경우, 이 문자열에 대해 약속이 만족되면 $f$는 이대일(two-to-one) 함수가 됩니다. 즉, $f$의 모든 가능한 출력 문자열에 대해 정확히 두 개의 입력 문자열이 $f$를 그 출력 문자열로 만듭니다. 나아가 이 두 입력 문자열은 어떤 문자열 $w$에 대해 $w$와 $w \oplus s$의 형태를 취해야 합니다.

약속이 만족되는 경우 작동하는 문자열 $s$는 오직 하나뿐임을 인식하는 것이 중요합니다. 따라서 약속을 만족하는 함수에는 항상 유일한 정답이 존재합니다.

다음은 문자열 $s = 011$에 대해 약속을 만족하는 $f:\Sigma^3 \rightarrow \Sigma^5$ 형태의 함수 예시입니다.

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

입력 문자열은 $8$개이고 출력 문자열은 $4$개이며, 각각 두 번씩 나타납니다. 따라서 이는 이대일 함수입니다. 또한, 동일한 출력 문자열을 생성하는 서로 다른 두 입력 문자열에 대해, 그 두 입력 문자열의 비트 XOR이 $011$과 같음을 알 수 있습니다. 이는 둘 중 하나가 다른 하나를 $s$와 XOR한 값과 같다는 말과 동치입니다.

실제 출력 문자열에서 중요한 것은 서로 다른 입력 문자열 선택에 대해 출력이 같은지 다른지 여부뿐임에 주목하세요. 예를 들어, 위의 예시에서 $f$의 출력으로 나타나는 문자열은 $(10011,$ $00101,$ $00001,$ $11010)$ 네 개입니다. 이 네 문자열을 모두 서로 다른 다른 문자열로 교체해도, 올바른 답 $s = 011$은 변하지 않습니다.

알고리즘 설명

다음은 사이먼 알고리즘을 나타내는 양자 Circuit 다이어그램입니다.

명확히 말하면, 위쪽에는 Hadamard Gate가 작용하는 $n$개의 Qubit이 있고, 아래쪽에는 쿼리 게이트로 직접 들어가는 $m$개의 Qubit이 있습니다. 이전에 이 레슨에서 다룬 알고리즘들과 매우 유사해 보이지만, 이번에는 위상 반동(phase kickback)이 없습니다. 아래쪽 $m$개의 Qubit은 모두 $\vert 0\rangle$ 상태로 쿼리 게이트에 들어갑니다.

이 Circuit을 사용하여 사이먼 문제를 풀기 위해서는 실제로 Circuit을 여러 번 독립적으로 실행한 후 고전적 후처리 단계가 필요합니다. 이에 대해서는 Circuit의 동작 분석 이후에 설명하겠습니다.

분석

사이먼 알고리즘의 분석은 도이치-조자 알고리즘과 비슷한 방식으로 시작됩니다. 위쪽 $n$개의 Qubit에 첫 번째 Hadamard Gate 레이어가 수행되면, 상태는 다음과 같이 됩니다.

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

$U_f$가 수행되면, 함수 $f$의 출력이 아래쪽 $m$개 Qubit의 전부 0인 상태에 XOR되어 상태가 다음과 같이 됩니다.

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

두 번째 Hadamard Gate 레이어가 수행되면, 이전과 동일한 Hadamard Gate 레이어 작용 공식을 사용하여 다음 상태를 얻습니다.

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

이 시점에서 분석은 이 레슨의 이전 알고리즘들과 달라집니다.

우리는 측정 결과가 각각의 가능한 문자열 $y\in\Sigma^n$이 될 확률에 관심이 있습니다. 양자 정보 기초 강좌의 복합 시스템 레슨에서 설명한 측정 분석 규칙을 통해, 문자열 $y$를 얻을 확률 $p(y)$는 다음과 같음을 알 수 있습니다.

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

이 확률들을 더 잘 이해하기 위해, 약간의 추가 표기법과 용어가 필요합니다. 먼저, 함수 $f$의 *치역(range)*은 모든 출력 문자열을 포함하는 집합입니다.

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

다음으로, 각 문자열 $z\in\operatorname{range}(f)$에 대해, 함수가 이 출력 문자열 $z$로 평가되도록 하는 모든 입력 문자열의 집합을 $f^{-1}(\{z\})$로 나타낼 수 있습니다.

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

집합 $f^{-1}(\{z\})$는 $f$ 아래에서 $\{z\}$의 *원상(preimage)*으로 알려져 있습니다. $\{z\}$ 대신 임의의 집합에 대해서도 $f$ 아래에서의 원상을 유사한 방식으로 정의할 수 있습니다. 원상은 $f$가 그 집합으로 매핑하는 모든 원소의 집합입니다. (이 표기법은 $f$의 역함수와 혼동하지 않도록 주의해야 합니다. 역함수는 존재하지 않을 수도 있습니다. 왼쪽의 인수가 원소 $z$가 아닌 집합 $\{z\}$라는 사실이 이러한 혼동을 피할 수 있게 해주는 단서입니다.)

이 표기법을 사용하면, 위의 확률 표현식에서 합산을 분리하여 다음을 얻을 수 있습니다.

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

$x\in\Sigma^n$의 모든 문자열은 두 합산에서 정확히 한 번씩 나타납니다. 이는 기본적으로 함수 $f$를 평가할 때 어떤 출력 문자열 $z = f(x)$를 생성하는지에 따라 이 문자열들을 별도의 버킷에 넣고, 각 버킷에 대해 별도로 합산하는 것과 같습니다.

이제 유클리드 노름의 제곱을 계산하면 다음을 얻습니다.

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

이 확률들을 더 단순화하기 위해, 임의의 $z\in\operatorname{range}(f)$ 선택에 대한 값을 살펴보겠습니다.

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

만약 $s = 0^n$인 경우, $f$는 단사 함수이므로 모든 $z\in\operatorname{range}(f)$에 대해 $f^{-1}(\{z\})$에는 항상 단 하나의 원소 $x$만 있습니다. 이 경우 식 $(1)$의 값은 $1$입니다.

반면에 $s\neq 0^n$인 경우, 집합 $f^{-1}(\{z\})$에는 정확히 두 개의 문자열이 있습니다. 더 정확히 말하면, $w\in f^{-1}(\{z\})$를 이 두 문자열 중 하나로 선택하면, 다른 문자열은 사이먼 문제의 약속에 의해 반드시 $w \oplus s$가 됩니다. 이 관찰을 이용하면 $(1)$을 다음과 같이 단순화할 수 있습니다.

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

따라서 값 $(1)$은 두 경우 모두에서 특정 $z\in\operatorname{range}(f)$의 선택과 무관하게 동일함을 알 수 있습니다.

이제 앞서와 같은 두 경우를 각각 살펴봄으로써 분석을 마무리할 수 있습니다.

• 경우 1: $s = 0^n.$ 이 경우 함수 $f$는 단사 함수이므로 $z\in\operatorname{range}(f)$인 문자열이 $2^n$개 있으며, 다음을 얻습니다.

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  즉, 측정 결과는 균등하게 무작위로 선택된 문자열 $y\in\Sigma^n$이 됩니다.

• 경우 2: $s \neq 0^n.$ 이 경우 $f$는 이대일 함수이므로 $\operatorname{range}(f)$에는 $2^{n-1}$개의 원소가 있습니다. 위의 공식을 사용하면 각 $y\in\Sigma^n$을 측정할 확률은 다음과 같습니다.

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  즉, $2^{n-1}$개의 문자열을 포함하는 집합 $\{y\in\Sigma^n : y \cdot s = 0\}$에서 균등하게 무작위로 선택된 문자열을 얻습니다. ($s\neq 0^n$이므로, 길이 $n$의 이진 문자열 중 정확히 절반이 $s$와의 이진 내적이 $1$이고 나머지 절반이 $0$임을 도이치-조자 알고리즘의 번스타인-바지라니 문제 분석에서 이미 확인했습니다.)

고전적 후처리

이제 사이먼 알고리즘의 양자 Circuit을 실행했을 때 가능한 측정 결과들의 확률을 알게 되었습니다. 이것만으로 $s$를 결정하기에 충분할까요?

답은 "예"입니다. 단, 과정을 여러 번 반복하고 일정 확률로 실패할 수 있다는 점을 받아들여야 합니다. Circuit을 충분히 많이 실행하면 이 확률을 매우 작게 만들 수 있습니다. 핵심 아이디어는 Circuit의 각 실행이 $s$에 관한 통계적 증거를 제공하며, Circuit을 충분히 여러 번 실행하면 이 증거를 사용하여 매우 높은 확률로 $s$를 찾을 수 있다는 것입니다.

Circuit을 $k = n + 10$으로 $k$번 독립적으로 실행한다고 가정해 보겠습니다. 이 특정 반복 횟수에는 특별한 의미가 있는 것은 아닙니다. 허용하는 실패 확률에 따라 $k$를 더 크게(또는 더 작게) 선택할 수 있으며, 이는 나중에 살펴볼 것입니다. $k = n + 10$을 선택하면 $s$를 복원할 확률이 $99.9$% 이상이 됩니다.

Circuit을 $k$번 실행하면 문자열 $y^1,...,y^{k} \in \Sigma^n$을 얻습니다. 명확히 말하면, 여기서 위첨자는 이 문자열들의 이름의 일부이며 지수나 비트 인덱스가 아닙니다.

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

이제 이 문자열들의 비트를 이진 값 원소로 하여 $k$개의 행과 $n$개의 열을 가진 행렬 $M$을 구성합니다.

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

현재 우리는 $s$가 무엇인지 모릅니다. 우리의 목표는 이 문자열을 찾는 것입니다. 그러나 잠시 $s$를 안다고 가정하고, 문자열 $s = s_{n-1} \cdots s_0$의 비트로부터 다음과 같이 열 벡터 $v$를 구성해 보겠습니다.

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

행렬-벡터 곱 $M v$를 모듈로 $2$로 수행하면, 즉 일반적인 방식으로 곱셈을 수행한 후 결과의 각 원소를 $2$로 나눈 나머지를 취하면, 전부 0인 벡터를 얻습니다.

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

즉, 방금 설명한 대로 열 벡터 $v$로 처리하면, 문자열 $s$는 항상 모듈로 $2$ 산술에서 행렬 $M$의 *영공간(null space)*의 원소가 됩니다. 이는 $s = 0^n$인 경우와 $s\neq 0^n$인 경우 모두에서 사실입니다. 더 정확히 말하면, 전부 0인 벡터는 항상 $M$의 영공간에 있으며, $s\neq 0^n$인 경우에는 $s$의 비트로 이루어진 벡터도 영공간에 포함됩니다.

남은 질문은 $0^n$과 $s$에 해당하는 벡터 외에 $M$의 영공간에 다른 벡터가 있을 수 있는지 여부입니다. $k$가 증가할수록 이는 점점 더 가능성이 낮아지며, $k = n + 10$을 선택하면 $99.9$% 이상의 확률로 $M$의 영공간에는 $0^n$과 $s$에 해당하는 벡터 외에 다른 벡터가 포함되지 않습니다. 더 일반적으로, $k = n + 10$을 $k = n + r$ ($r$은 임의의 양의 정수)로 대체하면, $0^n$과 $s$에 해당하는 벡터만이 $M$의 영공간에 있을 확률은 최소 $1 - 2^{-r}$입니다.

선형 대수학을 사용하면 모듈로 $2$에서 $M$의 영공간에 대한 설명을 효율적으로 계산할 수 있습니다. 구체적으로, 가우스 소거법을 사용하면 이를 수행할 수 있으며, 이 방법은 모듈로 $2$ 산술에서도 실수나 복소수에서와 동일한 방식으로 작동합니다. 높은 확률로 발생하는 경우처럼 $0^n$과 $s$에 해당하는 벡터만이 $M$의 영공간에 있는 한, 이 계산의 결과로부터 $s$를 추론할 수 있습니다.

고전적 어려움

고전 쿼리 알고리즘이 사이먼 문제를 풀기 위해 몇 번의 쿼리가 필요할까요? 일반적으로 답은 매우 많습니다.

이 문제의 고전적 어려움에 대해 다양한 정밀한 설명이 가능하며, 그 중 하나를 소개합니다. 임의의 확률적 쿼리 알고리즘이 $n$에 대해 지수적인 쿼리 횟수인 $2^{n/2 - 1} - 1$회 미만의 쿼리를 수행한다면, 그 알고리즘은 최소 $1/2$의 확률로 사이먼 문제를 풀지 못합니다.

이러한 불가능성 결과를 증명하는 것이 때로는 매우 어려울 수 있지만, 이 경우는 기본적인 확률적 분석을 통해 증명하기가 그리 어렵지 않습니다. 그러나 여기서는 그 이면의 기본적인 직관만 간략히 살펴보겠습니다.

우리는 숨겨진 문자열 $s$를 찾으려 하지만, 동일한 출력 값을 가지는 두 문자열에 대해 함수를 쿼리하지 않는 한, $s$에 대해 매우 제한된 정보만 얻을 수 있습니다. 직관적으로 말하면, 우리가 알게 되는 것은 숨겨진 문자열 $s$가 쿼리한 서로 다른 두 문자열의 XOR이 아니라는 것뿐입니다. 그리고 $2^{n/2 - 1} - 1$개 미만의 문자열을 쿼리한다면, 충분한 쌍의 문자열이 없기 때문에 여전히 배제하지 못한 $s$의 후보가 많이 남아 있습니다. 이것은 공식적인 증명이 아니라 기본적인 아이디어만을 나타냅니다.

요약하면, 사이먼 알고리즘은 쿼리 모델 내에서 양자 알고리즘이 고전 알고리즘에 비해 놀라운 우위를 제공함을 보여줍니다. 특히, 사이먼 알고리즘은 함수의 입력 비트 수 $n$에 대해 선형인 쿼리 횟수로 사이먼 문제를 풀지만, 확률적 알고리즘을 포함한 모든 고전 알고리즘은 합리적인 성공 확률로 사이먼 문제를 풀기 위해 $n$에 대해 지수적인 쿼리 횟수가 필요합니다.