왜 LCU가 필요한가
양자 회로가 직접 실행할 수 있는 기본 연산은 유니터리입니다. 하지만 우리가 원하는 연산은 유니터리가 아닐 때가 많습니다. 예를 들어 e^{-iHt}를 근사하거나, A^{-1}, polynomial p(A), projector 같은 연산을 만들고 싶을 수 있습니다.
LCU는 목표 연산을 유니터리들의 가중합으로 씁니다.
$$
A=\sum_{\ell=0}^{L-1}\alpha_\ell U_\ell,
\qquad \alpha_\ell\ge0
$$여기서 U_\ell들은 실제 회로로 구현 가능한 유니터리입니다.
PREPARE와 SELECT
LCU 회로는 보통 두 오라클로 구성됩니다. 먼저 PREPARE는 ancilla index register에 계수의 제곱근을 준비합니다.
$$
\mathrm{PREPARE}|0\rangle
=
{1\over\sqrt{\alpha}}\sum_\ell \sqrt{\alpha_\ell}|\ell\rangle,
\qquad
\alpha=\sum_\ell \alpha_\ell
$$SELECT는 index에 따라 대응하는 유니터리를 적용합니다.
$$
\mathrm{SELECT}
=
\sum_\ell |\ell\rangle\langle\ell|\otimes U_\ell
$$전체 회로는 아래처럼 씁니다.
$$
W=
(\mathrm{PREPARE}^\dagger\otimes I)
\mathrm{SELECT}
(\mathrm{PREPARE}\otimes I)
$$block-encoding으로 보기
위 회로에서 ancilla를 다시 |0\rangle으로 측정하는 block을 보면 목표 연산이 들어 있습니다.
$$
(\langle0|\otimes I)W(|0\rangle\otimes I)
=
{A\over \alpha}
$$즉 W는 더 큰 Hilbert space에서 A/\alpha를 위쪽 block으로 포함하는 유니터리입니다. 이것이 block-encoding의 기본 그림입니다.
LCU는 단순한 트릭이 아니라, 이후 Qubitization, QSP, QSVT로 이어지는 현대 양자 알고리즘 설계의 공통 인터페이스입니다.
성공확률
입력 |\psi\rangle에 대해 LCU 회로를 적용하면 ancilla가 |0\rangle인 branch에 A|\psi\rangle/\alpha가 들어갑니다.
$$
W|0\rangle|\psi\rangle
=
|0\rangle {A|\psi\rangle\over\alpha}
+|\perp\rangle
$$성공확률은 대략 \|A|\psi\rangle\|^2/\alpha^2입니다. \alpha가 크면 성공확률이 작아집니다. 그래서 coefficient normalization과 amplitude amplification이 중요해집니다.
Oblivious Amplitude Amplification
일반 amplitude amplification은 성공/실패 subspace에 대한 reflection을 반복해 성공 진폭을 키웁니다. OAA는 입력 상태 |\psi\rangle를 몰라도 ancilla의 성공 표시만으로 진폭을 증폭합니다.
성공 projector를 \Pi=|0\rangle\langle0|\otimes I라 하면 reflection은 아래입니다.
$$
R=2\Pi-I
$$LCU 유니터리 W와 reflection을 조합해 성공 branch의 진폭을 키웁니다. “oblivious”라는 말은 데이터 레지스터의 실제 상태에 의존하지 않고, ancilla 성공 조건만 보고 증폭한다는 뜻입니다.
Hamiltonian simulation에서 LCU
해밀토니안이 Pauli string들의 합으로 주어지는 경우가 많습니다.
$$
H=\sum_\ell h_\ell P_\ell
$$각 P_\ell는 유니터리이고, 계수 h_\ell를 PREPARE에 넣을 수 있습니다. 이렇게 해밀토니안을 block-encoding하면 Qubitization이나 QSVT로 e^{-iHt}, resolvent, spectral filter 같은 함수를 구현할 수 있습니다.
LCU 설계 체크리스트
- 목표 연산을 \sum_\ell \alpha_\ell U_\ell로 쓸 수 있는지 확인한다.
- \alpha=\sum_\ell\alpha_\ell가 너무 커지지 않는 표현을 고른다.
- PREPARE의 상태 준비 비용을 따로 계산한다.
- SELECT에서 controlled 유니터리 비용을 추정한다.
- 성공확률이 낮으면 OAA나 fixed-point amplification을 고려한다.
- 최종 목표가 block-encoding인지, 실제 postselected operation인지 구분한다.