문제 설정
유니터리 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로 해석합니다.
표준 회로
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 기울기를 계산기저 숫자로 바꿉니다.
정확히 표현되는 경우
\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입니다.
정확히 표현되지 않는 경우
\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 비용
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는 껍데기이고, 내부 유니터리를 얼마나 싸게 구현하느냐가 전체 성능을 좌우합니다.
입력이 고유상태가 아닐 때
입력 상태가 여러 고유상태의 중첩이면 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
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 설계 체크리스트
- 추정하려는 유니터리 U가 무엇인지 명확히 적는다.
- 입력 상태가 고유상태인지, 고유상태의 중첩인지 구분한다.
- 필요한 phase precision과 counting qubit 수를 연결한다.
- controlled-U^{2^k} 구현 비용을 따로 추정한다.
- inverse QFT를 정확형으로 쓸지 approximate QFT로 줄일지 정한다.
- 측정 결과를 어떤 고전 후처리로 해석할지 기록한다.