위상 추정 문제

이 레슨 섹션은 위상 추정 문제를 설명합니다. 먼저 선형대수의 스펙트럼 정리에 대해 간략히 논의하고, 그 다음 위상 추정 문제 자체의 설명으로 넘어갑니다.

스펙트럼 정리

스펙트럼 정리는 선형대수의 중요한 사실로, *정규 행렬(normal matrices)*이라고 불리는 특정 유형의 행렬이 간단하고 유용한 방식으로 표현될 수 있다는 것을 말합니다. 이 레슨에서는 유니터리 행렬에 대해서만 이 정리가 필요하지만, 이후 이 시리즈에서 에르미트 행렬에도 적용할 것입니다.

정규 행렬

복소수 항을 가진 정사각 행렬 $M$이 그 켤레 전치와 가환(commute)일 때, 즉 $M M^{\dagger} = M^{\dagger} M$일 때, $M$은 정규 행렬이라고 합니다.

모든 유니터리 행렬 $U$는 정규인데, 왜냐하면

$$U U^{\dagger} = \mathbb{I} = U^{\dagger} U.$$

이기 때문입니다.

자신의 켤레 전치와 같은 행렬인 에르미트 행렬은 정규 행렬의 또 다른 중요한 부류입니다. $H$가 에르미트 행렬이면,

$$H H^{\dagger} = H^2 = H^{\dagger} H,$$

이므로 $H$는 정규입니다.

모든 정사각 행렬이 정규인 것은 아닙니다. 예를 들어, 이 행렬은 정규가 아닙니다.

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

(이것은 고려하기에 매우 유용한 간단하지만 훌륭한 행렬의 예입니다.) 이것이 정규가 아닌 이유는

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$

인 반면,

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}.$$

이기 때문입니다.

정리 설명

이제 스펙트럼 정리의 내용을 보겠습니다.

Theorem

스펙트럼 정리: $M$을 정규 $N\times N$ 복소 행렬이라고 합시다. $N$차원 복소 벡터의 정규직교 기저 $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$과 복소수 $\lambda_1,\ldots,\lambda_N$이 존재하여 다음이 성립합니다.

$$M = \lambda_1 \vert \psi_1\rangle\langle \psi_1\vert + \cdots + \lambda_N \vert \psi_N\rangle\langle \psi_N\vert.$$

행렬을 다음과 같은 형태로 표현한 것을

$$M = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert \tag{1}$$

흔히 스펙트럼 분해라고 부릅니다. $M$이 $(1)$ 형태로 표현된 정규 행렬이면, 방정식

$$M \vert \psi_j \rangle = \lambda_j \vert \psi_j \rangle$$

은 모든 $j = 1,\ldots,N$에 대해 성립해야 함을 주목하세요. 이는 $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$이 정규직교라는 사실의 결과입니다.

$$M \vert \psi_j \rangle = \left(\sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\right)\vert \psi_j\rangle = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\psi_j \rangle = \lambda_j \vert\psi_j \rangle$$

즉, 각 수 $\lambda_j$는 $M$의 고윳값이고 $\vert\psi_j\rangle$은 그 고윳값에 대응하는 고유벡터입니다.

• 예시 1. 다음을 고려합시다.

  $$\mathbb{I} = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix},$$

  이것은 정규입니다. 정리는 $\mathbb{I}$를 $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ 및 $\vert\psi_2\rangle$의 어떤 선택에 대해 $(1)$ 형태로 쓸 수 있음을 함의합니다. 작동하는 선택이 여러 가지 있는데, 다음을 포함합니다.

  $$\lambda_1 = 1, \hspace{5pt} \lambda_2 = 1, \hspace{5pt} \vert\psi_1\rangle = \vert 0\rangle, \hspace{5pt} \vert\psi_2\rangle = \vert 1\rangle.$$

  정리는 복소수 $\lambda_1,\ldots,\lambda_N$이 서로 다르다고 말하지 않는다는 점을 주목하세요. 즉, 같은 복소수가 반복될 수 있는데, 이 예에서는 필수적입니다. 이 선택들이 작동하는 이유는

  $$\mathbb{I} = \vert 0\rangle\langle 0\vert + \vert 1\rangle\langle 1\vert.$$

  이기 때문입니다. 사실, $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$을 임의의 정규직교 기저로 선택할 수 있으며 방정식이 참이 됩니다. 예를 들어,

  $$\mathbb{I} = \vert +\rangle\langle +\vert + \vert -\rangle\langle -\vert.$$

• 예시 2. Hadamard 연산을 고려해 봅시다.

  $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$

  이것은 유니터리 행렬이므로 정규입니다. 스펙트럼 정리는 $H$를 $(1)$ 형태로 쓸 수 있음을 함의하며, 특히

  $$H = \vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert$$

  여기서

  $$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle.$$

  입니다.

  더 명시적으로,

  $$\begin{aligned} \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle, \\[3mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle. \end{aligned}$$

  필요한 계산을 수행함으로써 이 분해가 올바르다는 것을 확인할 수 있습니다.

  $$\vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert = \begin{pmatrix} \frac{2 + \sqrt{2}}{4} & \frac{\sqrt{2}}{4}\\[2mm] \frac{\sqrt{2}}{4} & \frac{2 - \sqrt{2}}{4} \end{pmatrix} - \begin{pmatrix} \frac{2 - \sqrt{2}}{4} & -\frac{\sqrt{2}}{4}\\[2mm] -\frac{\sqrt{2}}{4} & \frac{2 + \sqrt{2}}{4} \end{pmatrix} = H.$$

위 첫 번째 예가 보여주듯이 고유벡터 선택에는 어느 정도 자유도가 있을 수 있습니다. 그러나 고윳값의 선택에는 순서를 제외하고는 전혀 자유도가 없습니다. 주어진 행렬 $M$의 선택에 대해 항상 같은 $N$개의 복소수 $\lambda_1,\ldots,\lambda_N$(같은 복소수의 반복을 포함할 수 있음)이 방정식 $(1)$에 나타납니다.

이제 유니터리 행렬에 초점을 맞춰 봅시다. 복소수 $\lambda$와 영이 아닌 벡터 $\vert\psi\rangle$이 다음 방정식을 만족한다고 가정합시다.

$$U\vert\psi\rangle = \lambda\vert\psi\rangle. \tag{2}$$

즉, $\lambda$는 $U$의 고윳값이고 $\vert\psi\rangle$은 이 고윳값에 대응하는 고유벡터입니다.

유니터리 행렬은 유클리드 노름을 보존하므로, $(2)$로부터 다음을 결론 내립니다.

$$\bigl\| \vert\psi\rangle \bigr\| = \bigl\| U \vert\psi\rangle \bigr\| = \bigl\| \lambda \vert\psi\rangle \bigr\| = \vert \lambda \vert \bigl\| \vert\psi\rangle \bigr\|$$

$\vert\psi\rangle$이 영이 아니라는 조건은 $\bigl\| \vert\psi\rangle \bigr\|\neq 0$을 함의하므로, 양변에서 이를 상쇄하여 다음을 얻습니다.

$$\vert \lambda \vert = 1.$$

이는 유니터리 행렬의 고윳값이 항상 절댓값이 1이어야 함을 드러내며, 따라서 *단위원(unit circle)*에 위치합니다.

$$\mathbb{T} = \{\alpha\in\mathbb{C} : \vert\alpha\vert = 1\}$$

(기호 $\mathbb{T}$는 복소 단위원에 대한 흔한 이름입니다. $S^1$이라는 이름도 흔합니다.)

위상 추정 문제 설명

위상 추정 문제에서 우리는 $n$개의 Qubit에 작용하는 유니터리 양자 Circuit과 함께 $n$개 Qubit의 양자 상태 $\vert \psi\rangle$을 받습니다. $\vert \psi\rangle$이 Circuit의 작용을 기술하는 유니터리 행렬 $U$의 고유벡터임을 약속받으며, 우리의 목표는 $\vert \psi\rangle$이 대응하는 고윳값 $\lambda$를 계산하거나 근사하는 것입니다. 더 정확하게는, $\lambda$가 복소 단위원에 있으므로, 다음과 같이 쓸 수 있습니다.

$$\lambda = e^{2\pi i \theta}$$

$0\leq\theta<1$을 만족하는 유일한 실수 $\theta$에 대해서 말입니다. 문제의 목표는 이 실수 $\theta$를 계산하거나 근사하는 것입니다.

위상 추정 문제

입력: $n$-Qubit 연산 $U$에 대한 유니터리 양자 Circuit과 $n$-Qubit 양자 상태 $\vert\psi\rangle$
약속: $\vert\psi\rangle$은 $U$의 고유벡터
출력: $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$을 만족하는 수 $\theta\in[0,1)$에 대한 근사값

이 문제 설명에 대한 몇 가지 언급은 다음과 같습니다.

1. 위상 추정 문제는 입력에 양자 상태가 포함된다는 점에서 이 강좌에서 지금까지 본 다른 문제와 다릅니다. 일반적으로 우리는 고전 입력과 출력을 갖는 문제에 초점을 맞추지만, 이와 같은 양자 상태 입력을 고려하는 것을 막는 것은 없습니다. 실제적 관련성의 측면에서, 위상 추정 문제는 일반적으로 더 큰 계산 내부의 하위 문제로 만나게 되며, 레슨 뒷부분에서 정수 인수분해의 맥락에서 보게 될 것입니다.

2. 위의 위상 추정 문제 설명은 무엇이 $\theta$의 근사를 구성하는지에 대해 구체적이지 않지만, 우리의 필요와 관심에 따라 더 정확한 문제 설명을 공식화할 수 있습니다. 정수 인수분해의 맥락에서는 $\theta$에 대해 매우 정확한 근사를 요구할 것이지만, 다른 경우에는 매우 거친 근사에 만족할 수도 있습니다. 우리가 요구하는 정밀도가 해법의 계산 비용에 어떻게 영향을 미치는지 곧 논의할 것입니다.

3. 위상 추정 문제에서 $\theta = 0$부터 $\theta = 1$로 이동할 때, 단위원을 한 바퀴 돌아 $e^{2\pi i \cdot 0} = 1$에서 시작하여 반시계 방향으로 $e^{2\pi i \cdot 1} = 1$까지 이동한다는 점을 주목하세요. 즉, $\theta = 1$에 도달하면 $\theta = 0$에서 시작한 곳으로 돌아옵니다. 따라서 근사의 정확도를 고려할 때 $1$ 근처의 $\theta$ 선택은 $0$ 근처에 있는 것으로 간주되어야 합니다. 예를 들어, 근사값 $\theta = 0.999$는 $\theta = 0$에서 $1/1000$ 이내에 있는 것으로 간주되어야 합니다.