Hamiltonian Simulation 심화

목표

해밀토니안 H와 시간 t가 주어졌을 때 아래 유니터리를 구현합니다.

$$
U(t)=e^{-iHt}
$$

입력 상태가 에너지 고유상태라면 phase가 붙습니다.

$$
H|E_j\rangle=E_j|E_j\rangle
\quad\Rightarrow\quad
e^{-iHt}|E_j\rangle=e^{-iE_jt}|E_j\rangle
$$

QPE는 이 phase를 읽어 에너지를 추정합니다.

Pauli decomposition

양자컴퓨팅에서는 해밀토니안을 Pauli string의 합으로 표현하는 일이 많습니다.

$$
H=\sum_{\ell=1}^{L} h_\ell P_\ell
$$

각 P_\ell는 I,X,Y,Z의 텐서곱입니다. 예를 들면 아래와 같습니다.

$$
P_\ell=X_0Z_1Y_3
$$

Pauli string 하나의 시간발전 e^{-ih_\ell P_\ell t}는 basis change, CNOT ladder, R_z, inverse ladder로 구현할 수 있습니다.

Trotter-Suzuki

항들이 서로 commute하지 않으면 일반적으로 아래가 정확하지 않습니다.

$$
e^{-i(A+B)t}\ne e^{-iAt}e^{-iBt}
$$

하지만 작은 시간 조각으로 나누면 근사할 수 있습니다.

$$
e^{-i(A+B)t}
\approx
\left(e^{-iA t/r}e^{-iB t/r}\right)^r
$$

고차 Suzuki formula는 오차를 줄이지만 회로 길이가 늘어납니다. NISQ에서는 낮은 차수 Trotter가 직관적이고 구현이 쉬워 자주 쓰이지만, 큰 정밀도와 긴 시간에서는 qubitization 계열이 더 좋은 이론 복잡도를 가질 수 있습니다.

Taylor/LCU 방식

지수함수를 Taylor series로 전개합니다.

$$
e^{-iHt}
\approx
\sum_{k=0}^{K}{(-itH)^k\over k!}
$$

H가 Pauli string 합이면 H^k는 Pauli string product들의 합입니다. 이를 LCU로 구현하고 OAA로 성공확률을 키울 수 있습니다. 이 방식은 Trotter와 달리 항들의 commutator 오차를 직접 누적하는 방식이 아니라 series truncation 오차를 관리합니다.

Chebyshev 방식

스케일된 해밀토니안 \tilde H의 spectrum이 [-1,1]에 있으면 아래 전개를 사용할 수 있습니다.

$$
e^{-i\tau \tilde H}
=
J_0(\tau)I
+2\sum_{k=1}^{\infty}(-i)^kJ_k(\tau)T_k(\tilde H)
$$

Chebyshev 다항식은 recurrence로 안정적으로 다룰 수 있고, QSP polynomial 설계와도 연결됩니다. 실제 회로에서는 이 전개를 LCU로 구현하거나 QSP/QSVT polynomial로 흡수합니다.

Qubitization 방식

해밀토니안을 block-encoding합니다.

$$
(\langle0|\otimes I)U_H(|0\rangle\otimes I)=H/\alpha
$$

그 다음 QSP를 사용해 e^{-i\alpha t x}를 근사하는 polynomial을 구현합니다.

$$
p(x)\approx e^{-i\alpha t x}
$$

이 방식의 query complexity는 대략 O(\alpha t+\log(1/\epsilon)) 형태로 설명됩니다. 세부 상수와 모델은 다르지만, 큰 그림은 block-encoding 호출 횟수가 시간과 오차에 의해 정해진다는 것입니다.

방식 비교

방식	장점	주의점
Trotter	구현 직관이 좋고 Pauli 회로로 바로 전개 가능	commutator 오차, 긴 시간에서 깊이 증가
Taylor/LCU	series truncation으로 오차 관리	PREPARE/SELECT/OAA 비용
Chebyshev	스펙트럼 구간 근사가 안정적	계수와 polynomial degree 설계 필요
Qubitization/QSP	좋은 query complexity, 현대적 통합 프레임워크	block-encoding과 phase sequence 준비가 어려움

설계 문서에 적을 것

H의 표현: Pauli sum, sparse oracle, block-encoding 등
normalization \alpha 또는 \|H\| bound
목표 시간 t와 허용 오차 \epsilon
선택한 simulation 방식
query 수, 2Q gate 수, ancilla 수
QPE에 넣을 경우 필요한 controlled simulation 비용