LCU는 유니터리가 아닌 연산을 유니터리들의 선형결합으로 구현하는 설계 기법입니다. OAA는 그 구현이 성공한 branch의 진폭을 키우는 방식입니다.
## 왜 LCU가 필요한가 {#motivation}
양자 회로가 직접 실행할 수 있는 기본 연산은 유니터리입니다. 하지만 우리가 원하는 연산은 유니터리가 아닐 때가 많습니다. 예를 들어 $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 {#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으로 보기 {#block}
위 회로에서 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로 이어지는 현대 양자 알고리즘 설계의 공통 인터페이스입니다.
## 성공확률 {#success}
입력 $|\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 {#oaa}
일반 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 {#hamiltonian}
해밀토니안이 Pauli string들의 합으로 주어지는 경우가 많습니다.
$$
H=\sum_\ell h_\ell P_\ell
$$
각 $P_\ell$는 유니터리이고, 계수 $h_\ell$를 PREPARE에 넣을 수 있습니다. 이렇게 해밀토니안을 block-encoding하면 Qubitization이나 QSVT로 $e^{-iHt}$, resolvent, spectral filter 같은 함수를 구현할 수 있습니다.
## LCU 설계 체크리스트 {#design}
1. 목표 연산을 $\sum_\ell \alpha_\ell U_\ell$로 쓸 수 있는지 확인한다.
2. $\alpha=\sum_\ell\alpha_\ell$가 너무 커지지 않는 표현을 고른다.
3. PREPARE의 상태 준비 비용을 따로 계산한다.
4. SELECT에서 controlled 유니터리 비용을 추정한다.
5. 성공확률이 낮으면 OAA나 fixed-point amplification을 고려한다.
6. 최종 목표가 block-encoding인지, 실제 postselected operation인지 구분한다.