양자 컴퓨터에서의 고전적 계산

이제 양자 컴퓨터에서 고전적 알고리즘을 구현하는 것에 주의를 돌려 보겠습니다. 고전적 Boolean Circuit으로 수행할 수 있는 모든 계산은 유사한 점근적 계산 비용으로 양자 Circuit에서도 수행할 수 있음을 보게 될 것입니다. 또한 이는 곧 설명할 "깔끔한(clean)" 방식으로 수행될 수 있으며, 이는 이러한 계산을 더 큰 양자 계산 내부의 서브루틴으로 사용하기 위한 중요한 요구 조건이 됩니다.

양자 Circuit으로 Boolean Circuit 시뮬레이션하기

Boolean Circuit은 AND, OR, NOT, FANOUT Gate로 구성됩니다. Boolean Circuit을 양자 Circuit으로 시뮬레이션하기 위해, 먼저 이 네 가지 Gate 각각을 어떻게 양자 Gate로 시뮬레이션할 수 있는지 살펴봐요. 이것이 끝나면, 주어진 Boolean Circuit을 양자 Circuit으로 변환하는 것은 한 번에 하나의 Gate를 시뮬레이션하는 단순한 문제가 됩니다. 이를 위해서는 NOT Gate, controlled-NOT Gate, Toffoli Gate만 있으면 되며, 이들은 모두 유니터리일 뿐 아니라 결정론적 연산입니다.

Toffoli Gate

Toffoli Gate는 controlled-controlled-NOT Gate로 달리 표현할 수도 있으며, 표준 기저 상태에 대한 작용은 다음 그림과 같습니다.

Qiskit의 정렬 규약을 사용하고 있음을 염두에 두면(즉, Qubit이 위에서 아래로 유의성이 증가하는 순서로 정렬됨), 이 Gate의 행렬 표현은 다음과 같습니다.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Toffoli Gate를 생각하는 또 다른 방법은, 이것이 본질적으로 AND 함수에 대한 질의(query) Gate라는 점입니다. 이는 이전 강의에서 이진 문자열 입력과 출력을 갖는 임의 함수의 유니터리 질의 Gate 구현에 대해 본 패턴을 따른다는 의미입니다.

Toffoli Gate는 이 강의에서 앞서 논의한 기본 Gate 집합에 포함되지 않지만, 다음과 같이 $H,$ $T,$ $T^{\dagger},$ 그리고 CNOT Gate로부터 Toffoli Gate를 구성할 수 있습니다.

Toffoli, controlled-NOT, NOT Gate로 Boolean Gate 시뮬레이션하기

몇 개의 NOT Gate와 함께 사용되는 단일 Toffoli Gate는 AND 및 OR Gate를 구현할 수 있으며, FANOUT Gate는 다음 그림이 보여주는 것처럼 controlled-NOT Gate를 사용해 쉽게 구현할 수 있습니다.

세 경우 모두, AND, OR, FANOUT Gate가 작용하는 Qubit들은 왼쪽에서 입력으로 들어오며, 각각에 대해 0 상태로 초기화된 작업(workspace) Qubit이 하나 필요합니다. 이러한 작업 Qubit들은 Gate 구현을 나타내는 상자 안에 표시되어, 새로 추가된 것이며 따라서 이 구현의 비용의 일부임을 시사합니다.

AND와 OR Gate의 경우 출력 Qubit 외에 두 개의 Qubit이 더 남습니다. 예를 들어 AND Gate 시뮬레이션을 나타내는 그림의 상자 내부에서, 상위 두 Qubit은 $\vert a\rangle$과 $\vert b\rangle$ 상태로 남습니다. 이 Qubit들은 더 이상 필요하지 않고 출력의 일부가 아니기 때문에 상자 안에 남아있는 것으로 그려져 있습니다. 지금은 무시해도 되지만, 잠시 후에 다시 주의를 돌려보겠습니다.

나머지 Boolean Gate인 NOT Gate는 기본 양자 Gate 집합에 포함되어 있으므로, 이에 대한 시뮬레이션은 필요하지 않습니다.

Boolean Circuit의 Gate 단위 시뮬레이션

이제 AND, OR, NOT, FANOUT Gate로 구성되고 $n$개의 입력 비트와 $m$개의 출력 비트를 갖는 일반적인 Boolean Circuit을 $C$라 부른다고 가정해 봅시다. $t = \operatorname{size}(C)$를 $C$의 Gate 수라 하고, $C$가 계산하는 함수에 $f$라는 이름을 붙이면, 이는 다음과 같은 형식을 가집니다.

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

여기서 $\Sigma = \{0,1\}$입니다.

이제 $C$의 AND, OR, FANOUT Gate를 하나씩 차례로 지나가면서 위에서 설명한 대응 시뮬레이션(필요한 작업 Qubit 추가 포함)으로 각각을 대체하면 어떤 일이 일어나는지 생각해 봅시다. 결과로 나오는 Circuit을 $R$이라 부르고, $R$의 Qubit들을 정렬하여 $C$의 $n$개 입력 비트가 $R$의 상위 $n$개 Qubit에 대응하고 작업 Qubit은 하단에 오도록 합니다.

여기서 $k$는 필요한 작업 Qubit의 수 — $C$의 각 AND, OR, FANOUT Gate마다 하나씩 — 이고, $g$는 다음 형식의 함수 $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$으로, $R$이 실행된 후 Gate 시뮬레이션에 의해 생성된 나머지 Qubit들의 상태를 기술합니다. 그림에서 출력 $f(x)$에 해당하는 Qubit은 상단에 있고, $g(x)$를 저장하는 나머지 Qubit들은 하단에 있습니다. 원한다면 SWAP Gate를 사용해 Qubit을 재배치하여 이를 강제로 만들 수 있으며, SWAP Gate는 다음과 같이 세 개의 controlled-NOT Gate로 구현할 수 있습니다:

다음 절에서 보게 되겠지만, 이와 같이 출력 Qubit을 재배치하는 것이 꼭 필수적인 것은 아니지만, 원한다면 충분히 쉽게 할 수 있습니다.

나머지 Qubit들의 고전적 상태를 기술하는 함수 $g$는 Circuit $C$에 의해 결정되지만, 실제로 그것에 대해 너무 걱정할 필요는 없습니다. 계산이 끝났을 때 이 Qubit들이 구체적으로 어떤 상태에 있는지는 신경 쓰지 않기 때문입니다. 문자 $g$는 $f$ 다음에 오므로 이 함수의 이름으로 합리적이지만, $g$라는 이름을 선택한 더 좋은 이유가 있습니다 — 그것은 *garbage(쓰레기)*의 약자이기 때문입니다.

쓰레기 정리하기

주어진 Boolean Circuit $C$가 계산하는 함수 $f$를 양자 Circuit으로 평가하는 데만 관심이 있다면, 방금 설명한 Gate별 시뮬레이션 이상으로 진행할 필요가 없습니다. 이는 함수의 출력 외에도 한 무더기의 쓰레기가 남게 된다는 뜻입니다.

그러나 더 큰 양자 계산 내에서 고전적 계산을 서브루틴으로 수행하려는 경우에는 이것으로는 충분하지 않습니다. 왜냐하면 그 쓰레기 Qubit들이 문제를 일으키기 때문입니다. 간섭(interference) 현상은 양자 알고리즘에서 매우 중요한데, 쓰레기 Qubit은 양자 알고리즘이 작동하는 데 필요한 간섭 패턴을 망칠 수 있습니다.

다행히도, 말하자면 쓰레기를 정리하는 것은 어렵지 않습니다. 핵심은 $R$이 양자 Circuit이라는 사실을 이용하는 것입니다. 각 Gate를 그 역으로 바꾸고 역순으로 적용하기만 하면 역방향으로 실행할 수 있으며, 이를 통해 연산 $R^{\dagger}$에 대한 양자 Circuit을 얻을 수 있습니다. Toffoli Gate, CNOT Gate, NOT Gate는 실제로 자기 자신이 역이므로, $R$을 역방향으로 실행하는 것은 단지 Gate들을 역순으로 적용하는 문제일 뿐입니다 — 하지만 더 일반적으로는 모든 양자 Circuit이 방금 설명한 것처럼 역으로 돌려질 수 있습니다.

구체적으로, 우리가 할 수 있는 것은 $m$개의 Qubit을 추가하고(함수 $f$가 $m$개의 출력 비트를 가진다는 점을 상기), CNOT Gate를 사용해 $R$의 출력을 이 Qubit들로 복사한 다음, $R$을 역으로 돌려 쓰레기를 정리하는 것입니다. 다음 그림은 결과로 얻어지는 Circuit과 표준 기저 상태에 대한 그 작용을 보여줍니다.

전체 Circuit에 상자를 두르고 $Q$라고 부르면, 다음과 같은 모습이 됩니다.

$C$가 $t$개의 Gate를 가진다고 할 때, Circuit $Q$는 $O(t)$개의 Gate를 가지게 됩니다.

$k$개의 추가 작업 Qubit을 무시한다면, 우리가 가진 것은 함수 $f$에 대한 질의 Gate와 정확히 동일하게 작동하는 Circuit $Q$입니다. 어떤 문자열 $x$에 대해 함수 $f$를 단순히 계산하고 싶다면, $y = 0^m$으로 설정하면 결과값 $f(x)$가 하단의 $m$개 Qubit에 나타납니다 — 또는 원한다면 하단의 $m$개 Qubit에 다른 상태를 공급할 수도 있습니다 (Deutsch 또는 Deutsch-Jozsa 알고리즘에서처럼 위상 킥백(phase kickback)을 활용하기 위해서 등).

이는 모든 질의 알고리즘에 대해, 입력 함수를 계산하는 Boolean Circuit이 있으면 각 질의 Gate를 그것의 Circuit 구현으로 대체할 수 있으며, 질의 알고리즘이 올바르게 작동함을 의미합니다.

이 과정이 작동하려면 작업 Qubit이 필요하지만, 결합된 Circuit이 실행되고 나면 초기 상태로 되돌아간다는 점에 주목하세요. 이로써 이 Qubit들은 다른 용도의 작업 Qubit으로 다시 사용될 수 있습니다. 필요한 작업 Qubit 수를 줄이는 알려진 전략도 있지만(대신 Circuit이 더 커지는 비용이 따릅니다), 여기서는 그러한 전략을 논의하지 않겠습니다.

가역 함수 구현하기

방금 설명한 구성은 쓰레기가 없는 방식으로 임의의 Boolean Circuit을 양자 Circuit으로 시뮬레이션할 수 있게 해줍니다. $C$가 함수 $f:\Sigma^n \rightarrow \Sigma^m$을 구현하는 Boolean Circuit이라면, 표준 기저 상태에 대해 다음과 같이 동작하는 양자 Circuit $Q$를 얻습니다.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

수 $k$는 전체적으로 필요한 작업 Qubit의 수를 나타냅니다. 이 강좌의 목적을 위해서는 이것으로 충분하지만, 함수 $f$ 자체가 가역일 때는 이 방법론을 한 단계 더 진전시킬 수 있습니다.

정확히 말하자면, 함수 $f$가 $f:\Sigma^n \rightarrow \Sigma^n$ 형태를 취하고, 모든 $x\in\Sigma^n$에 대해 $f^{-1}(f(x)) = x$를 만족하는 함수 $f^{-1}$가 존재한다고 가정해 봅시다(이러한 함수가 존재할 때는 반드시 유일합니다). 이는 모든 $x\in\Sigma^n$에 대해 $\vert x \rangle$을 $\vert f(x) \rangle$로 변환하는 연산이 유니터리임을 의미하므로, 다음에 의해 정의되는 유니터리 연산을 구현하는 양자 Circuit을 만들 수 있기를 희망할 수 있습니다.

$$U \vert x \rangle = \vert f(x) \rangle$$

모든 $x\in\Sigma^n$에 대하여 말이죠.

명확히 말씀드리면, 이것이 유니터리 연산이라는 사실은 $f$가 가역이라는 점에 의존합니다 — $f$가 가역이 아니면 유니터리가 아닙니다. 작업 Qubit을 무시하면, $U$는 Circuit $Q$가 구현하는 연산과 다릅니다. 왜냐하면 우리는 입력의 사본을 남겨두고 임의 문자열에 XOR하는 것이 아니라, $x$를 $f(x)$로 대체하기 때문입니다.

질문은: $f$가 가역일 때, 우리가 이것을 할 수 있을까요?

답은 그렇다입니다. 단, 작업 Qubit을 사용할 수 있고, $f$를 계산하는 Boolean Circuit 외에 $f^{-1}$을 계산하는 것도 가지고 있다는 조건 하에서 말입니다. 따라서 이것은 우리가 이미 방법을 모르는 함수를 계산적으로 역산하는 지름길은 아닙니다! 다음 그림은 위에서 설명한 방법을 통해 함수 $f$와 $f^{-1}$에 대해 개별적으로 얻어지는 두 양자 Circuit $Q_f$와 $Q_{f^{-1}},$ 그리고 $n$개의 swap Gate를 합성함으로써 이것이 어떻게 이루어질 수 있는지 보여주며, 여기서 $k$는 $Q_f$와 $Q_{f^{-1}}$에 필요한 작업 Qubit 수의 최댓값입니다.