Quantum Phase Estimation은 많은 고급 양자 알고리즘의 중심 부품입니다. Shor, HHL, Hamiltonian simulation 분석, amplitude estimation이 모두 “유니터리의 고유위상을 읽는다”는 문법 위에 있습니다.
## 문제 설정 {#problem}
유니터리 $U$와 그 고유상태 $|u\rangle$가 있다고 합니다.
$$
U|u\rangle=e^{2\pi i\phi}|u\rangle,
\qquad 0\le \phi <1
$$
QPE의 목표는 $\phi$를 $m$비트 정밀도로 추정하는 것입니다. 측정 결과가 정수 $y$로 나오면 보통 $\tilde\phi=y/2^m$로 해석합니다.
## 표준 회로 {#circuit}
counting register $m$큐비트를 $|0^m\rangle$에서 시작해 Hadamard로 균등중첩을 만듭니다.
$$
{1\over\sqrt{2^m}}\sum_{k=0}^{2^m-1}|k\rangle|u\rangle
$$
그 다음 $|k\rangle$가 들고 있는 정수만큼 $U^k$를 적용한 것과 같은 controlled powers를 겁니다.
$$
{1\over\sqrt{2^m}}\sum_{k=0}^{2^m-1}e^{2\pi i k\phi}|k\rangle|u\rangle
$$
이제 counting register에는 등차수열 phase가 들어 있습니다. inverse QFT는 이 phase 기울기를 계산기저 숫자로 바꿉니다.
## 정확히 표현되는 경우 {#exact}
$\phi=j/2^m$이면 QPE는 이상적으로 $|j\rangle$를 확정적으로 출력합니다.
$$
{1\over\sqrt{2^m}}\sum_{k=0}^{2^m-1}e^{2\pi i k j/2^m}|k\rangle
\xrightarrow{\mathrm{QFT}^{-1}}
|j\rangle
$$
예를 들어 $\phi=5/8=0.101_2$이고 $m=3$이면 결과는 $101$입니다.
## 정확히 표현되지 않는 경우 {#inexact}
$\phi$가 $m$비트로 정확히 표현되지 않으면 결과는 가장 가까운 정수 근처에 퍼집니다. $N=2^m$라 두면 측정값 $y$의 진폭은 기하급수 합입니다.
$$
\alpha_y
=
{1\over N}\sum_{k=0}^{N-1}e^{2\pi i k(\phi-y/N)}
=
{1\over N}\,{1-e^{2\pi i N(\phi-y/N)}\over 1-e^{2\pi i(\phi-y/N)}}
$$
따라서 확률은 $y/N$이 $\phi$에 가까울수록 큽니다. 회로설계 관점에서 precision을 높이려면 counting qubit을 늘려야 하지만, controlled-$U^{2^k}$ 비용도 함께 커집니다.
## controlled powers 비용 {#cost}
QPE의 비용은 inverse QFT보다 controlled powers에 의해 결정되는 경우가 많습니다.
$$
\mathrm{cost(QPE)}
\approx
\sum_{k=0}^{m-1}\mathrm{cost}\!\left(\mathrm{controlled}\text{-}U^{2^k}\right)
+\mathrm{cost}(\mathrm{QFT}^{-1})
$$
Shor에서는 $U^{2^k}$가 modular multiplication이고, HHL에서는 Hamiltonian simulation입니다. 즉 QPE는 껍데기이고, 내부 유니터리를 얼마나 싸게 구현하느냐가 전체 성능을 좌우합니다.
## 입력이 고유상태가 아닐 때 {#input-not-eigen}
입력 상태가 여러 고유상태의 중첩이면 QPE는 고유위상을 확률적으로 샘플링합니다.
$$
|\psi\rangle=\sum_j \beta_j |u_j\rangle,
\qquad
U|u_j\rangle=e^{2\pi i\phi_j}|u_j\rangle
$$
QPE 뒤 상태는 대략 아래처럼 됩니다.
$$
\sum_j \beta_j |\tilde\phi_j\rangle|u_j\rangle
$$
측정하면 $|\beta_j|^2$ 비율로 고유위상 하나가 나옵니다. HHL은 이 구조를 이용해 고유값별로 역수를 걸고, amplitude estimation은 Grover iterate의 고유위상을 읽습니다.
## Iterative QPE {#iterative}
counting register를 많이 쓰기 어렵다면 iterative phase estimation을 사용할 수 있습니다. 하나의 ancilla를 반복 측정하면서 phase bit을 높은 자리부터 추정합니다. 이 방식은 width를 줄이는 대신 회로 반복과 feed-forward 제어가 필요합니다.
NISQ 장비에서는 깊은 controlled powers가 부담스럽기 때문에, 표준 QPE보다 variational phase estimation, robust phase estimation, Bayesian phase estimation 같은 변형이 쓰이기도 합니다. 다만 이 문서 흐름에서는 표준 QPE를 먼저 정확히 이해하는 것이 우선입니다.
## QPE 설계 체크리스트 {#checklist}
1. 추정하려는 유니터리 $U$가 무엇인지 명확히 적는다.
2. 입력 상태가 고유상태인지, 고유상태의 중첩인지 구분한다.
3. 필요한 phase precision과 counting qubit 수를 연결한다.
4. controlled-$U^{2^k}$ 구현 비용을 따로 추정한다.
5. inverse QFT를 정확형으로 쓸지 approximate QFT로 줄일지 정한다.
6. 측정 결과를 어떤 고전 후처리로 해석할지 기록한다.