위상 추정 절차

다음으로, 위상 추정 문제를 푸는 양자 알고리즘인 위상 추정 절차에 대해 살펴보겠습니다.

먼저 낮은 정밀도의 워밍업으로 시작하여 이 방법의 기본 직관을 설명합니다. 그런 다음 위상 추정 절차에 사용되는 중요한 양자 연산인 양자 푸리에 변환과 그 양자 Circuit 구현에 대해 다룰 것입니다. 양자 푸리에 변환을 이해한 뒤에는 위상 추정 절차를 완전한 일반성으로 기술하고 그 성능을 분석합니다.

워밍업: 낮은 정밀도로 위상 근사하기

낮은 정밀도의 위상 추정 절차 예시를 몇 가지 살펴보는 것으로 시작하겠습니다. 이를 통해 나중에 다룰 일반적인 절차의 직관을 이해할 수 있습니다.

위상 킥백 활용하기

위상 추정 문제에 대한 간단한 접근법 중 하나는 위상 킥백 현상을 기반으로 하며, 이를 통해 우리가 구하고자 하는 값 $\theta$에 관한 정보를 얻을 수 있습니다. 이 방법은 본질적으로 나중에 다룰 일반 위상 추정 절차의 단일 qubit 버전에 해당합니다.

위상 추정 문제의 입력 중 일부로, 연산 $U$에 대한 유니터리 양자 Circuit이 주어집니다. 이 Circuit의 설명을 이용하면 제어(Controlled)-$U$ 연산에 대한 Circuit을 만들 수 있습니다. 아래 그림에서 왼쪽은 양자 Gate로 본 연산 $U$이고, 오른쪽은 Controlled-$U$ 연산입니다.

Controlled-$U$ 연산에 대한 양자 Circuit을 만들려면 $U$의 Circuit에 제어 Qubit을 하나 추가한 뒤, $U$의 Circuit에 있는 모든 Gate를 해당 Gate의 제어 버전으로 교체하면 됩니다. 즉, 새로 추가한 하나의 제어 Qubit이 $U$ Circuit의 모든 Gate를 실질적으로 제어하게 됩니다. 이를 위해서는 Circuit에 있는 모든 Gate의 제어 버전이 필요하지만, 게이트 집합에 포함되어 있지 않은 경우에도 이러한 제어 연산에 대한 Circuit은 항상 구성할 수 있습니다.

이제 다음 Circuit을 생각해 보겠습니다. 여기서 맨 위 Qubit을 제외한 모든 Qubit의 입력 상태 $\vert\psi\rangle$는 $U$의 고유 벡터인 양자 상태입니다.

이 Circuit의 측정 결과 확률은 고유 벡터 $\vert\psi\rangle$에 대응하는 $U$의 고유값에 따라 달라집니다. 정확히 어떻게 달라지는지 Circuit을 자세히 분석해 봅시다.

Circuit의 초기 상태는 다음과 같습니다.

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

첫 번째 Hadamard Gate가 이 상태를 다음과 같이 변환합니다.

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

다음으로 Controlled-$U$ 연산이 수행되어 다음 상태가 됩니다.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

$\vert\psi\rangle$가 고유값 $\lambda = e^{2\pi i\theta}$를 갖는 $U$의 고유 벡터라는 가정을 이용하면, 이 상태를 다음과 같이 다시 쓸 수 있습니다.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

여기서 위상 킥백 현상을 관찰할 수 있습니다. 쿼리 Gate를 사용하지 않기 때문에 Deutsch 알고리즘이나 Deutsch-Jozsa 알고리즘에서와는 약간 다르게 나타나지만, 아이디어는 유사합니다.

마지막으로 두 번째 Hadamard Gate가 수행됩니다. 약간의 정리를 거치면 다음 상태를 얻습니다.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

따라서 측정 결과로 $0$과 $1$이 나타날 확률은 다음과 같습니다.

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

아래는 두 가능한 결과 $0$과 $1$의 확률을 $\theta$의 함수로 나타낸 그래프입니다.

두 확률의 합은 항상 $1$입니다. $\theta = 0$일 때 측정 결과는 항상 $0$이고, $\theta = 1/2$일 때는 항상 $1$임을 알 수 있습니다. 따라서 측정 결과가 $\theta$의 정확한 값을 알려주지는 않지만, 어느 정도의 정보를 제공합니다. 만약 $\theta = 0$ 또는 $\theta = 1/2$ 중 하나라는 것이 사전에 보장된다면, 오류 없이 어느 쪽인지를 이 Circuit으로 알아낼 수 있습니다.

직관적으로, Circuit의 측정 결과를 $\theta$에 대한 "1비트 정확도" 추정값으로 생각할 수 있습니다. 다시 말해, $\theta$를 이진 표기로 나타내고 1비트로 반올림하면 다음과 같은 수가 됩니다.

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

측정 결과는 비트 $a$에 대한 추정값으로 볼 수 있습니다. $\theta$가 $0$도 $1/2$도 아닌 경우, 추정이 틀릴 확률이 0이 아닙니다. 하지만 $0$ 또는 $1/2$에 가까워질수록 오류 확률은 점점 작아집니다.

이 절차에서 두 Hadamard Gate가 어떤 역할을 하는지 생각해 보는 것은 자연스럽습니다.

• 첫 번째 Hadamard Gate는 제어 Qubit을 $\vert 0\rangle$과 $\vert 1\rangle$의 균일한 중첩 상태로 만들어, 위상 킥백이 $\vert 0\rangle$ 상태가 아닌 $\vert 1\rangle$ 상태에 대해 발생하도록 합니다. 이를 통해 측정 결과에 영향을 미치는 상대적인 위상 차이가 생깁니다. 이 과정 없이 위상 킥백이 전역적인 위상을 만들어낸다면, 측정 결과의 확률에 아무런 영향을 주지 못합니다.

• 두 번째 Hadamard Gate는 간섭 현상을 통해 $\theta$에 관한 정보를 얻을 수 있게 해줍니다. 두 번째 Hadamard Gate 이전에 맨 위 Qubit의 상태는 다음과 같습니다.

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  이 상태를 측정하면 $0$과 $1$ 각각을 확률 $1/2$로 얻게 되어, $\theta$에 대한 정보를 전혀 얻을 수 없습니다. 그러나 두 번째 Hadamard Gate를 수행하면 $\theta$가 출력 확률에 영향을 미치게 됩니다.

위상 두 배로 만들기

위의 Circuit은 위상 킥백 현상을 이용해 $\theta$를 1비트 정확도로 근사합니다. 일부 상황에서는 1비트 정확도로 충분할 수 있지만, 소인수분해를 위해서는 훨씬 높은 정확도가 필요합니다. $\theta$에 대해 더 많은 정보를 어떻게 얻을 수 있을지가 자연스러운 의문입니다.

매우 간단한 방법 중 하나는 Circuit에서 Controlled-$U$ 연산을 두 개의 복사본으로 교체하는 것입니다. 다음 Circuit과 같습니다.

Controlled-$U$ 연산을 두 번 적용하는 것은 Controlled-$U^2$ 연산과 동일합니다. $\vert\psi\rangle$가 고유값 $\lambda = e^{2\pi i \theta}$를 갖는 $U$의 고유 벡터라면, 이 상태는 $U^2$의 고유 벡터이기도 하며, 이 경우 고유값은 $\lambda^2 = e^{2\pi i (2\theta)}$입니다.

따라서 이 버전의 Circuit을 실행하면, $\theta$가 $2\theta$로 대체된 동일한 계산을 수행하는 것과 같습니다. 아래는 $\theta$가 $0$에서 $1$까지 변할 때의 출력 확률을 나타낸 그래프입니다.

이 방법은 실제로 $\theta$에 대한 추가 정보를 제공할 수 있습니다. $\theta$의 이진 표현이 다음과 같다면

$$\theta = 0.a_1 a_2 a_3\cdots$$

$\theta$를 두 배로 하면 소수점이 오른쪽으로 한 자리 이동하는 효과가 있습니다.

$$2\theta = a_1. a_2 a_3\cdots$$

그리고 단위 원 위에서 이동할 때 $\theta = 1$과 $\theta = 0$을 동일시하므로, 비트 $a_1$은 확률에 영향을 미치지 않으며, $\theta$를 2비트로 반올림했을 때 소수점 이하 두 번째 비트에 대한 추정값을 얻게 됩니다. 예를 들어, $\theta$가 $0$ 또는 $1/4$ 중 하나라는 것이 사전에 알려진 경우, 측정 결과를 완전히 신뢰하여 어느 쪽인지 알 수 있습니다.

하지만 이 추정을 원래의 (두 배가 아닌) 위상 킥백 Circuit에서 얻은 정보와 어떻게 결합하여 $\theta$에 대해 가능한 한 정확한 정보를 얻을 수 있는지는 즉시 명확하지 않습니다. 한 걸음 물러서서 어떻게 진행할지 생각해 봅시다.

2-Qubit 위상 추정

위의 두 가지 방법을 별도로 고려하는 대신, 다음과 같이 하나의 Circuit으로 결합해 봅시다.

제어 연산 이후의 Hadamard Gate는 제거되었으며 측정도 아직 없습니다. $\theta$에 대해 최대한 많은 정보를 얻기 위한 옵션을 고려하면서 Circuit에 추가해 나갈 것입니다.

$\vert\psi\rangle$가 $U$의 고유 벡터인 경우 이 Circuit을 실행하면, 아래 Qubit들의 상태는 Circuit 전체에 걸쳐 $\vert\psi\rangle$로 유지되고, 위상은 위쪽 두 Qubit의 상태로 "킥백"됩니다. 다음 그림을 통해 Circuit을 자세히 분석해 봅시다.

상태 $\vert\pi_1\rangle$은 다음과 같이 쓸 수 있습니다.

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

첫 번째 Controlled-$U$ 연산이 수행되면, $a_0$ (맨 위 qubit)가 $1$일 때만 고유값 $\lambda = e^{2\pi i\theta}$가 위상으로 킥백됩니다. $a_0$가 $0$일 때는 킥백이 발생하지 않습니다. 따라서 결과 상태를 다음과 같이 표현할 수 있습니다.

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

두 번째와 세 번째 Controlled-$U$ Gate도 유사하게 동작하지만, $a_0$ 대신 $a_1$에 대해, 그리고 $\theta$ 대신 $2\theta$로 대체됩니다. 결과 상태는 다음과 같습니다.

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

이진 문자열 $a_1 a_0$를 이진 표기로 정수 $x \in \{0,1,2,3\}$을 나타내는 것으로 보면, 즉 $x = 2 a_1 + a_0$로 정의하면, 이 상태를 다음과 같이 쓸 수 있습니다.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

우리의 목표는 이 상태에서 $\theta$에 관한 정보를 최대한 추출하는 것입니다.

이 시점에서 $\theta = \frac{y}{4}$ ($y\in\{0,1,2,3\}$인 정수)가 보장된 특별한 경우를 고려해 봅시다. 다시 말해, $\theta\in \{0, 1/4, 1/2, 3/4\}$이므로, 이 수를 이진 표기로 .$00,$ .$01,$ .$10,$ .$11$과 같이 2비트로 정확하게 표현할 수 있습니다. 일반적으로 $\theta$가 이 네 값 중 하나가 아닐 수도 있지만, 이 특별한 경우를 생각해 보면 일반적으로 $\theta$에 관한 정보를 가장 효과적으로 추출하는 방법을 파악하는 데 도움이 됩니다.

먼저 가능한 각 값 $y \in \{0, 1, 2, 3\}$에 대한 2-Qubit 상태 벡터를 정의합니다.

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

지수를 단순화하면 이 벡터들을 다음과 같이 쓸 수 있습니다.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

이 벡터들은 서로 직교합니다. 즉, 그 중 어떤 두 벡터를 골라 내적을 계산하면 $0$이 됩니다. 각 벡터는 단위 벡터이기도 하므로, $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$은 정규직교 기저가 됩니다. 따라서 이 벡터들을 완벽하게 구별하는 측정이 존재함을 바로 알 수 있습니다. 즉, 그 중 하나가 주어지지만 어느 것인지 모르는 경우, 오류 없이 어느 것인지 알아낼 수 있습니다.

양자 Circuit으로 이러한 구별을 수행하려면 먼저 표준 기저 상태를 위 네 상태로 변환하는 유니터리 연산 $V$를 정의합니다.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

$V$를 $4\times 4$ 행렬로 나타내려면, $V$의 열을 상태 $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$로 설정하면 됩니다.

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

이것은 특별한 행렬로, 일부 독자들은 이미 접해 보았을 것입니다. 바로 $4$차원 이산 푸리에 변환과 관련된 행렬입니다. 이 사실에 비추어, 이 행렬을 $V$ 대신 $\mathrm{QFT}_4$라고 부르겠습니다. $\mathrm{QFT}$는 *양자 푸리에 변환(Quantum Fourier Transform)*의 약자로, 본질적으로 유니터리 연산으로 본 이산 푸리에 변환입니다. 양자 푸리에 변환에 대해서는 곧 더 자세히, 그리고 더 일반적인 맥락에서 다루겠습니다.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

이 연산의 역연산을 수행하면 반대 방향, 즉 상태 $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$을 표준 기저 상태 $\vert 0\rangle,\ldots,\vert 3\rangle$으로 변환할 수 있습니다. 이렇게 하면 측정을 통해 $\theta = y/4$를 설명하는 값 $y\in\{0,1,2,3\}$을 알 수 있습니다. 아래는 이를 수행하는 양자 Circuit의 다이어그램입니다.

요약하면, $y\in\{0,1,2,3\}$에 대해 $\theta = y/4$인 경우 이 Circuit을 실행하면, 측정 직전 상태는 $\vert \psi\rangle \vert y\rangle$ (2비트 이진 문자열로 인코딩된 $y$)가 되므로, 측정을 통해 오류 없이 값 $y$를 알 수 있습니다.

이 Circuit은 $\theta \in \{0,1/4,1/2,3/4\}$인 특별한 경우에 동기를 두고 있지만, $U$와 $\vert \psi\rangle$의 임의의 선택, 따라서 원하는 임의의 $\theta$ 값에 대해 실행할 수 있습니다. 아래는 임의의 $\theta$ 선택에 대해 Circuit이 생성하는 출력 확률의 그래프입니다.

이는 앞서 설명한 단일 qubit 방식에 비해 명확한 개선입니다. 완벽하지는 않아서 잘못된 답을 줄 수도 있지만, 답은 $\theta$에 가까운 $y/4$ 값으로 강하게 치우쳐 있습니다. 특히, 가장 가능성 높은 결과는 항상 $\theta$에 가장 가까운 $y/4$ 값에 해당하며 (이전과 마찬가지로 $\theta = 0$과 $\theta = 1$을 동일시), 그래프를 보면 $x$에 대한 이 가장 가까운 값이 항상 약 $40\%$보다 높은 확률로 나타납니다. $\theta$가 두 값의 정확히 중간, 예를 들어 $\theta = 0.375$인 경우, 두 개의 동등하게 가까운 $y$ 값이 동일한 확률로 나타납니다.

다수 Qubit으로의 일반화 준비

하나가 아닌 두 개의 제어 Qubit을 사용하고 4차원 양자 푸리에 변환의 역연산을 함께 사용함으로써 얻은 개선을 바탕으로, 이를 더욱 확장하는 것이 자연스러운 방향입니다. 즉, 제어 Qubit을 더 추가하는 것입니다. 이렇게 하면 일반적인 위상 추정 절차를 얻을 수 있습니다. 이것이 어떻게 동작하는지 곧 살펴보겠지만, 정확하게 설명하기 위해서는 양자 푸리에 변환을 더 일반적인 맥락에서 다루어야 합니다. 즉, 다른 차원에서 어떻게 정의되는지, 그리고 $m$ qubit 양자 Circuit으로 어떻게 구현(또는 역연산)할 수 있는지를 살펴볼 필요가 있습니다.

양자 푸리에 변환

양자 푸리에 변환(Quantum Fourier transform)은 임의의 양의 정수 차원 $N$에 대해 정의할 수 있는 유니터리 연산입니다. 이 절에서는 이 연산의 정의와, $N = 2^m$일 때 $m$개의 Qubit에 대해 비용 $O(m^2)$의 양자 Circuit으로 구현하는 방법을 살펴봅니다.

양자 푸리에 변환을 기술하는 행렬은 $N$차원 벡터에 대한 유사 연산인 *이산 푸리에 변환(discrete Fourier transform)*에서 유도됩니다. 이 연산은 다양한 관점에서 생각할 수 있습니다. 예를 들어, 선형 사상으로서 순수하게 추상적·수학적 관점에서 이산 푸리에 변환을 바라볼 수 있습니다. 또는 계산적 관점에서, $N$차원 복소수 벡터(실수부와 허수부를 이진 표기법으로 인코딩한다고 가정합시다)가 주어지고, 이산 푸리에 변환을 적용해 얻은 $N$차원 벡터를 계산하는 것이 목표인 관점으로 볼 수도 있습니다. 우리의 초점은 세 번째 방식, 즉 이 변환을 양자 시스템에서 수행할 수 있는 유니터리 연산으로 보는 것입니다.

주어진 입력 벡터에 대해 이산 푸리에 변환을 효율적으로 계산하는 알고리즘으로 *고속 푸리에 변환(fast Fourier transform)*이 있습니다. 신호 처리를 비롯한 다양한 분야에 응용되며, 역사상 가장 중요한 알고리즘 중 하나로 꼽힙니다. $N$이 2의 거듭제곱일 때 우리가 공부할 양자 푸리에 변환의 구현은, 고속 푸리에 변환을 가능하게 하는 바로 그 기반 구조에 기초하고 있습니다.

양자 푸리에 변환의 정의

양자 푸리에 변환을 정의하기 위해, 먼저 각 양의 정수 $N$에 대해 복소수 $\omega_N$을 다음과 같이 정의합니다.

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

이 수는 복소 단위원 위에서 $1$에서 시작하여 반시계 방향으로 $2\pi/N$ 라디안, 즉 원주의 $1/N$ 만큼 이동했을 때 얻는 값입니다. 몇 가지 예를 들면 다음과 같습니다.

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

이제 $N$차원 양자 푸리에 변환을 정의할 수 있습니다. 이 변환은 표준 기저 상태 $\vert 0\rangle,\ldots,\vert N-1\rangle$에 대응하는 행과 열을 갖는 $N\times N$ 행렬로 기술됩니다. 위상 추정에는 $N = 2^m$이 2의 거듭제곱인 경우만 필요하지만, 이 연산은 임의의 양의 정수 $N$에 대해 정의할 수 있습니다.

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

앞서 언급했듯이, 이것은 $N$차원 이산 푸리에 변환에 대응하는 행렬입니다. 이 행렬의 정의에서는 보통 앞의 $1/\sqrt{N}$ 인수가 포함되지 않는 경우도 있지만, 유니터리 행렬을 얻으려면 이 인수를 포함해야 합니다.

다음은 작은 $N$ 값에 대한 양자 푸리에 변환을 행렬로 나타낸 것입니다.

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

특히, $\mathrm{QFT}_2$는 아다마르(Hadamard) 연산의 다른 이름임을 알 수 있습니다.

유니터리성

임의의 $N$에 대해 $\mathrm{QFT}_N$이 유니터리임을 확인해 봅시다. 한 가지 방법은 열들이 정규직교 기저를 이룸을 보이는 것입니다. $y = 0$부터 $y = N-1$까지, 열 번호 $y$에 대응하는 벡터를 다음과 같이 정의할 수 있습니다.

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

임의의 두 벡터의 내적을 계산하면 다음과 같습니다.

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

이러한 합은 등비수열의 처음 $N$항의 합에 관한 다음 공식을 이용해 계산할 수 있습니다.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

구체적으로, $\alpha = \omega_N^{y-z}$로 놓고 이 공식을 사용합니다. $y = z$이면 $\alpha = 1$이므로, 공식을 적용하고 $N$으로 나누면

$$\langle \phi_y \vert \phi_y \rangle = 1$$

을 얻습니다.

$y\neq z$이면 $\alpha \neq 1$이므로, 공식에 의해

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0$$

이 됩니다.

이렇게 되는 이유는 $\omega_N^N = e^{2\pi i} = 1$이므로 $\omega_N^{N(y-z)} = 1^{y-z} = 1$이 되어 분자가 $0$이 되는 반면, $\omega_N^{y-z} \neq 1$이므로 분모는 $0$이 아니기 때문입니다. 직관적으로, 단위원 위에 고루 분포된 점들을 모두 더하면 서로 상쇄되어 $0$이 된다고 생각할 수 있습니다.

따라서 $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$이 정규직교 집합임을 확인하였고,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

이로부터 $\mathrm{QFT}_N$이 유니터리임을 알 수 있습니다.

제어 위상 Gate

양자 Circuit으로 양자 푸리에 변환을 구현하려면 제어 위상(controlled-phase) Gate를 사용해야 합니다. *위상 연산(phase operation)*은 실수 $\alpha$에 대해 다음과 같은 형태의 단일 qubit 유니터리 연산입니다.

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

이 Gate의 제어 버전은 다음과 같은 행렬을 갖습니다.

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

이 제어 Gate에서는 어느 Qubit이 제어이고 어느 Qubit이 대상인지가 사실 중요하지 않습니다. 두 가지 경우가 동치이기 때문입니다. 양자 Circuit 다이어그램에서 이 Gate를 나타내는 데는 다음 기호들 중 어느 것이든 사용할 수 있습니다.

세 번째 형태에서는 편의에 따라 $\alpha$ 레이블을 제어선 옆이나 아래쪽 제어 표시 아래에 놓기도 합니다.

$N = 2^m$이고 $m\geq 2$일 때 양자 푸리에 변환을 수행하려면, 표준 기저 상태에 대해 다음과 같이 작용하는 $m$ qubit 연산을 수행해야 합니다.

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

여기서 $a$는 비트이고 $y \in \{0,\ldots,2^{m-1} - 1\}$은 $m-1$비트 이진 표기법으로 인코딩된 수입니다. 이는 $m=5$인 경우를 예시로 하여 다음을 일반화하면 제어 위상 Gate로 구현할 수 있습니다.

일반적으로, $m\geq 2$인 임의의 경우에 대해 비트 $a$에 해당하는 맨 위 Qubit을 제어로 보고, $y$의 최하위 비트에 해당하는 Qubit에는 $\alpha = \pi/2^{m-1}$, $y$의 최상위 비트에 해당하는 Qubit에는 $\alpha = \frac{\pi}{2}$의 위상 Gate $P_{\alpha}$를 적용합니다. 이 제어 위상 Gate들은 서로 교환 가능하며 어떤 순서로도 수행할 수 있습니다.

QFT의 Circuit 구현

이제 차원 $N = 2^m$이 $2$의 거듭제곱일 때 양자 푸리에 변환을 Circuit으로 구현하는 방법을 살펴보겠습니다. 양자 푸리에 변환을 구현하는 방법은 사실 여러 가지가 있지만, 이 방법이 알려진 것 중 가장 단순하다고 할 수 있습니다. 양자 푸리에 변환을 양자 Circuit으로 구현하는 방법을 알면, 그 역연산을 구현하는 것도 간단합니다. 각 Gate를 역연산(즉, 켤레 전치)으로 교체하고 Gate를 역순으로 적용하면 됩니다. 단일 Gate만으로 구성된 모든 양자 Circuit은 이 방법으로 역연산할 수 있습니다.

이 구현은 재귀적 특성을 가지므로, 재귀적인 방식으로 설명하는 것이 가장 자연스럽습니다. 기저 사례는 $m=1$이며, 이 경우 양자 푸리에 변환은 하다마르(Hadamard) 연산입니다.

$m \geq 2$일 때 $m$개의 Qubit에 대해 양자 푸리에 변환을 수행하려면, 다음 단계를 따릅니다. 각 단계의 동작은 표준 기저 상태 $\vert x \rangle \vert a\rangle$에 대해 설명하며, 여기서 $x\in\{0,\ldots,2^{m-1} - 1\}$은 이진 표기법으로 $m-1$비트로 인코딩된 정수이고 $a$는 단일 비트입니다.

1. 먼저 하위/왼쪽의 $m-1$개 Qubit에 $2^{m-1}$차원 양자 푸리에 변환을 적용하여 다음 상태를 얻습니다:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   이는 단일 Qubit에 대한 하다마르 연산을 기저 사례로 삼아, 한 qubit 적은 경우에 대해 이 방법을 재귀적으로 적용함으로써 수행됩니다.

2. 상위/오른쪽 Qubit을 제어로 사용하여 나머지 $m-1$개 Qubit의 각 표준 기저 상태 $\vert y\rangle$에 위상 $\omega_{2^m}^y$를 주입하고(위에서 설명한 방법으로), 다음 상태를 얻습니다:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. 상위/오른쪽 Qubit에 하다마르 Gate를 수행하여 다음 상태를 얻습니다:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. Qubit의 순서를 치환하여 최하위 비트가 최상위 비트가 되도록 하고, 나머지는 위/오른쪽으로 이동합니다:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

예를 들어, $N = 32 = 2^5$일 때 얻는 Circuit은 다음과 같습니다. 이 다이어그램에서 Qubit에는 명확성을 위해 입력에 대한 표준 기저 벡터 $\vert x\rangle \vert a\rangle$와 출력에 대한 $\vert b\rangle \vert y\rangle$에 해당하는 이름이 붙어 있습니다.

분석

방금 설명한 Circuit이 $2^m$차원 양자 푸리에 변환을 구현함을 검증하기 위해 필요한 핵심 공식은 다음과 같습니다:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

이 공식은 정수 $a,$ $b,$ $x,$ $y$의 임의 선택에 대해 성립하지만, $a,b\in\{0,1\}$이고 $x,y\in\{0,\ldots,2^{m-1}-1\}$인 경우에만 필요합니다. 우변의 지수에서 곱을 전개하여 확인할 수 있습니다.

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

여기서 두 번째 등호는

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1$$

이라는 관찰을 이용합니다.

$2^m$차원 양자 푸리에 변환은 모든 $u\in\{0,\ldots,2^m - 1\}$에 대해 다음과 같이 정의됩니다.

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

$u$와 $v$를

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

($a,b\in\{0,1\}$이고 $x,y\in\{0,\ldots,2^{m-1} - 1\}$)로 쓰면 다음을 얻습니다.

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

마지막으로, 표준 기저 상태 $\vert x \rangle \vert a\rangle$와 $\vert b \rangle \vert y \rangle$을 $\{0,\ldots,2^m-1\}$ 범위의 정수에 대한 이진 인코딩으로 생각하면,

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

위 Circuit이 필요한 연산을 구현함을 알 수 있습니다. 양자 푸리에 변환을 수행하는 이 방법이 놀랍게 느껴진다면, 실제로 그럴 만합니다. 이것은 본질적으로 양자 Circuit 형태의 고속 푸리에 변환(FFT)입니다.

마지막으로, 방금 설명한 Circuit에서 사용되는 Gate의 수를 세어 보겠습니다. 제어-위상 Gate는 이전 수업에서 다룬 표준 Gate 집합에 포함되지 않지만, 우선 이를 무시하고 각각을 단일 Gate로 간주하여 계산하겠습니다.

$m$의 각 가능한 선택에 대해 필요한 Gate 수를 $s_m$이라 하겠습니다. $m=1$이면 양자 푸리에 변환은 하다마르 연산이므로,

$$s_1 = 1.$$

$m\geq 2$이면 위 Circuit에서 $m-1$개 Qubit에 대한 양자 푸리에 변환에 $s_{m-1}$개의 Gate, $m-1$개의 제어-위상 Gate, 하다마르 Gate 1개, $m-1$개의 스왑 Gate가 필요하므로,

$$s_m = s_{m-1} + (2m - 1).$$

합산하여 닫힌 형식의 식을 구하면:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

실제로는 이 방법에서 설명하는 만큼 많은 스왑 Gate가 필요하지 않습니다. Gate를 약간 재배열하면 모든 스왑 Gate를 오른쪽으로 밀어낼 수 있고, 필요한 스왑 Gate 수를 $\lfloor m/2\rfloor$개로 줄일 수 있습니다. 점근적으로 이것이 크게 개선된 것은 아닙니다: $\mathrm{QFT}_{2^m}$을 수행하는 Circuit의 크기는 여전히 $O(m^2)$입니다.

표준 Gate 집합의 Gate만을 사용하여 양자 푸리에 변환을 구현하려면, 각 제어-위상 Gate를 집합에 있는 Gate로 만들거나 근사해야 합니다. 필요한 Gate 수는 요구하는 정확도에 따라 달라지지만, $m$의 함수로 보면 총 비용은 여전히 이차함수적입니다.

사실 $P_{\alpha}$는 $\alpha$가 매우 작을 때 항등 연산에 매우 가깝다는 사실을 이용하면 — 즉 제어-위상 Gate 대부분을 그냥 생략해도 정확도 손실이 크지 않다는 점을 활용하여 — 이차보다 적은 수의 Gate로 양자 푸리에 변환을 상당히 정밀하게 근사하는 것도 가능합니다.

일반적인 절차와 분석

이제 위상 추정 절차를 일반적인 형태로 살펴보겠습니다. 아이디어는 위에서 고려한 2 qubit 버전의 위상 추정을 아래 다이어그램이 제시하는 자연스러운 방식으로 확장하는 것입니다.

위쪽에 새로운 제어 Qubit이 추가될 때마다 단일 연산 $U$를 수행하는 횟수가 두 배가 됩니다. 이는 각 제어-단일 연산에서 $U$의 지수로 다이어그램에 표시되어 있습니다.

제어-$U^k$ 연산을 구현하는 가장 단순한 방법은 제어-$U$ 연산을 $k$번 반복하는 것입니다. 이 방법을 사용한다면, 제어 Qubit을 추가하는 것이 Circuit 크기에 상당한 영향을 미친다는 점을 인식해야 합니다. 다이어그램처럼 $m$개의 제어 Qubit이 있을 경우 총 $2^m - 1$번의 제어-$U$ 연산이 필요합니다. 이는 $m$이 증가함에 따라 상당한 계산 비용이 발생함을 의미합니다. 하지만 동시에 $\theta$에 대한 훨씬 더 정확한 근사가 가능해집니다.

그러나 일부 $U$의 선택에 대해서는 $U$에 대한 Circuit을 단순히 $k$번 반복하는 것보다 더 효율적인 방식으로 큰 $k$ 값에 대한 $U^k$ 연산을 구현하는 Circuit을 만들 수 있다는 점도 중요합니다. 이에 대한 구체적인 예는 뒤에서 정수 인수분해의 맥락에서 살펴볼 것이며, 이전 단원에서 설명한 모듈러 지수화의 효율적인 알고리즘이 여기서 활약합니다.

이제 앞서 설명한 Circuit을 분석해 보겠습니다. 역 양자 푸리에 변환 직전의 상태는 다음과 같습니다:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

특수한 경우

$m=2$ 경우에서 했던 것과 유사하게, 먼저 $y\in\{0,\ldots,2^m-1\}$에 대해 $\theta = y/2^m$인 특수한 경우를 고려합니다. 이 경우 역 양자 푸리에 변환 이전의 상태는 다음과 같이 다르게 쓸 수 있습니다:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

따라서 역 양자 푸리에 변환을 적용하면 상태는

$$\vert\psi\rangle \vert y\rangle$$

가 되고, 측정을 통해 $y$(이진 부호화된 값)가 드러납니다.

확률의 경계

$\theta$가 정수 $y$에 대해 $y/2^m$의 형태를 취하지 않는 다른 값인 경우, 측정 결과가 확정적이지 않습니다. 하지만 서로 다른 결과에 대한 확률의 경계를 증명할 수 있습니다. 이어서 $0\leq \theta < 1$을 만족하는 임의의 $\theta$를 고려하겠습니다.

역 양자 푸리에 변환을 수행한 후 Circuit의 상태는 다음과 같습니다:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

따라서 위쪽 $m$개의 Qubit에 대한 측정을 수행하면 각 결과 $y$가 다음 확률로 나타납니다:

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

이 확률들을 더 잘 이해하기 위해, 앞서 살펴본 등비급수의 첫 항들의 합에 대한 공식을 다시 사용합니다.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

$p_y$ 공식에 나타나는 합은 $\alpha = e^{2\pi i (\theta - y/2^m)}$으로 놓아 단순화할 수 있습니다. 다음과 같은 결과를 얻습니다.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

따라서 $\theta = y/2^m$인 경우 $p_y = 1$임을 알 수 있으며(이 특수한 경우에서 이미 알고 있었던 것처럼), $\theta \neq y/2^m$인 경우에는

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2$$

임을 알 수 있습니다.

단위원 위에서 호의 길이와 현의 길이가 어떻게 관련되는지를 생각하면 이 확률들에 대해 더 많은 것을 알 수 있습니다. 다음은 임의의 실수 $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$에 대해 필요한 관계를 보여주는 그림입니다.

먼저, 현의 길이(파란색)는 호의 길이(보라색)보다 클 수 없습니다:

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

반대 방향으로 이 길이들을 비교하면, 호의 길이 대 현의 길이의 비율은 $\delta = \pm 1/2$일 때 가장 크며, 이 경우 그 비율은 원의 반둘레를 지름으로 나눈 값인 $\pi/2$입니다. 따라서 다음이 성립합니다:

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

그러므로

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

이 관계들에 기반한 분석은 다음 두 가지 사실을 드러냅니다.

1. $\theta$가 실수이고 $y\in \{0,\ldots,2^m-1\}$가

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}$$

   을 만족한다고 가정합니다.

   이는 $y/2^m$이 $\theta$에 대한 최선의 $m$비트 근사이거나, 정확히 $y/2^m$와 $(y-1)/2^m$ 또는 $(y+1)/2^m$ 사이의 중간에 위치함을 의미합니다. 따라서 $\theta$에 대한 두 최선의 근사 중 하나입니다.

   이 경우 $p_y$가 꽤 크다는 것을 증명하겠습니다. 고려하는 가정으로부터 $\vert 2^m \theta - y \vert \leq 1/2$이 따라오므로, 호와 현의 길이에 관한 두 번째 관찰을 사용하여 다음을 결론지을 수 있습니다:

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   또한 호와 현의 길이에 관한 첫 번째 관찰을 사용하여 다음을 결론지을 수 있습니다:

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   이 두 부등식을 $p_y$에 적용하면 다음이 드러납니다:

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   이는 앞서 $m=2$ 버전의 위상 추정에서 최선의 결과가 $40\%$보다 높은 확률로 나타난다는 관찰을 설명해 줍니다. 정확히는 $40\%$가 아니라 $4/\pi^2$이며, 실제로 이 경계는 모든 $m$ 선택에 대해 성립합니다.

2. 이제 $y\in \{0,\ldots,2^m-1\}$가

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}$$

   을 만족한다고 가정합니다.

   이는 $\theta$와 $y/2^m$ 사이에 $\theta$에 대한 더 좋은 근사 $z/2^m$이 존재함을 의미합니다.

   이번에는 $p_y$가 너무 크지 않다는 것을 증명하겠습니다. 단위원 위의 임의의 두 점은 절댓값 차이가 최대 $2$라는 사실로부터 다음과 같은 간단한 관찰을 시작할 수 있습니다:

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2.$$

   또한 위에서 언급한 호와 현의 길이에 관한 두 번째 관찰을 이번에는 $p_y$의 분모에 적용하여 다음을 결론지을 수 있습니다:

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   두 부등식을 결합하면 다음이 드러납니다:

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   이 경계는 우리의 목적에는 충분하지만 다소 거칩니다. 실제 확률은 보통 $1/4$보다 훨씬 낮습니다.

이 분석에서 중요한 결론은, $\theta$에 대한 매우 가까운 근사가 나타날 가능성이 높다는 것입니다. 즉, 최선의 $m$비트 근사를 $40\%$보다 높은 확률로 얻을 수 있으며, $2^{-m}$ 이상 벗어난 근사는 나타날 가능성이 낮아 확률 상한이 $25\%$입니다.

이러한 보장이 주어지면, 위상 추정 절차를 여러 번 반복하여 $\theta$에 관한 통계적 증거를 수집함으로써 신뢰도를 높일 수 있습니다. 하단 qubit 모음의 상태 $\vert\psi\rangle$은 위상 추정 절차에 의해 변하지 않으므로, 원하는 만큼 절차를 반복해서 사용할 수 있다는 점을 주목하는 것이 중요합니다. 특히, 매번 Circuit을 실행할 때마다 $40\%$보다 높은 확률로 $\theta$에 대한 최선의 $m$비트 근사를 얻으며, $2^{-m}$ 이상 벗어날 확률은 $25\%$로 경계가 지어집니다. Circuit을 여러 번 실행하고 가장 자주 나타나는 결과를 취한다면, 가장 자주 나타나는 결과가 최대 $25\%$의 확률로만 발생하는 것일 가능성은 극히 낮습니다. 결과적으로 $\theta$ 값으로부터 $1/2^m$ 이내에 있는 근사 $y/2^m$을 매우 높은 확률로 얻을 수 있습니다. 실제로 $1/2^m$보다 더 크게 벗어날 가능성은 절차를 반복하는 횟수에 따라 지수적으로 감소합니다.

다음은 $m = 3$과 $m=4$일 때 연속된 세 가지 $y$ 값에 대한 확률을 $\theta$의 함수로 나타낸 두 그래프입니다. (명확성을 위해 세 가지 결과만 표시했습니다. 다른 결과에 대한 확률은 동일한 기본 함수를 순환 이동하여 구할 수 있습니다.)