양자 위상 추정

(1) 직관적 비유

음파의 주파수를 분석하는 것처럼, QPE는 양자 연산자가 얼마나 빠르게 '회전'하는지—즉 위상—를 정밀하게 읽어낸다. 시계 바늘이 한 바퀴 도는 속도를 측정하듯, 연산자가 고유상태에 작용할 때 발생하는 위상 변화량 $\phi$를 이진수로 추출한다.

(2) 엄밀한 정의

유니타리 $U$와 그 고유상태 $|\psi ⟩$에 대해 $$U|\psi ⟩=e^{2\pi i\phi }|\psi ⟩,\phi \in [0,1)$$ 가 성립할 때, $n$개의 보조(ancilla) 큐비트에 아다마르 변환으로 중첩을 생성하고, 제어-$U^{2^k}$ 게이트를 순차 적용한 뒤, 역 양자 푸리에 변환(QFT${}^{†}$)으로 $\phi$의 $n$비트 이진 근사를 측정으로 획득한다. 성공 확률은 $1-ϵ$ 이상으로 보장된다.

(3) 중요성·응용

• 쇼어 알고리즘: 주기 탐색의 핵심 서브루틴으로 소인수분해를 지수적으로 가속
• 양자 화학: 분자 해밀토니언의 바닥 상태 에너지(고유값) 계산
• HHL 알고리즘: 선형계 풀이에서 고유값의 역수를 추출

고전 알고리즘 대비 지수적 속도 향상을 제공하며, 양자 알고리즘 설계의 표준 서브루틴으로 자리잡고 있다.