Qubitization은 block-encoding된 행렬을 walk operator로 바꾸고, QSP는 그 고유위상에 원하는 다항식을 새깁니다. 현대 Hamiltonian simulation과 QSVT의 핵심 언어입니다.
## 출발점: block-encoding {#block}
유니터리 $U$가 행렬 $A/\alpha$를 block으로 담고 있다고 합시다.
$$
(\langle0|\otimes I)U(|0\rangle\otimes I)
=
{A\over\alpha}
$$
여기서 $\alpha$는 normalization factor입니다. LCU로 만든 유니터리도 block-encoding의 예입니다. Qubitization은 이 block-encoding을 더 구조적인 walk operator로 바꿔서 spectrum을 직접 다루게 합니다.
## walk operator {#walk}
성공 ancilla subspace에 대한 reflection을 $R=2|0\rangle\langle0|\otimes I-I$라 두면, qubitization의 walk operator는 대략 아래처럼 생깁니다.
$$
W=RU
$$
정확한 convention은 문헌마다 조금씩 다르지만 핵심은 같습니다. $A/\alpha$의 고유값 $\lambda$가 walk operator의 고유위상 $\theta$와 연결됩니다.
$$
\lambda=\cos\theta
$$
즉 행렬 고유값 문제를 유니터리 고유위상 문제로 바꿉니다.
## QSP의 기본 생각 {#qsp}
Quantum Signal Processing은 하나의 signal unitary와 보조 phase rotation들을 번갈아 적용해 원하는 polynomial transformation을 구현합니다.
$$
U_{\Phi}(x)
=
e^{i\phi_0 Z}
U(x)
e^{i\phi_1 Z}
U(x)
\cdots
e^{i\phi_d Z}
$$
여기서 phase list $\Phi=(\phi_0,\dots,\phi_d)$가 알고리즘의 핵심 파라미터입니다. 적절한 $\Phi$를 찾으면 matrix element가 원하는 polynomial $p(x)$가 됩니다.
## phase sequence가 하는 일 {#phase-sequence}
QSP에서 회로 구조는 거의 고정되어 있고, 구현할 함수는 phase sequence가 결정합니다. 같은 signal unitary를 쓰더라도 phase를 바꾸면 $x$, $x^3$, $e^{-itx}$ 근사, sign 함수 근사 등으로 바뀝니다.
따라서 고급 회로설계에서는 두 문제가 분리됩니다.
1. 좋은 block-encoding 또는 signal oracle을 만든다.
2. 원하는 함수에 대응하는 QSP phase sequence를 합성한다.
두 번째 문제는 수치해석과 approximation theory의 영역입니다.
## Hamiltonian simulation과 qubitization {#hamiltonian}
해밀토니안 $H$를 block-encoding했다고 합시다.
$$
(\langle0|\otimes I)U_H(|0\rangle\otimes I)=H/\alpha
$$
목표는 $e^{-iHt}$입니다. 고유값 $\lambda$마다 $e^{-i\alpha t\lambda}$를 적용해야 하므로, QSP polynomial이 이 함수를 근사하게 설계합니다.
$$
p(\lambda)\approx e^{-i\alpha t\lambda}
$$
이 방식은 Trotter 방식과 달리 commutator 구조에 덜 의존하고, query complexity가 거의 최적인 Hamiltonian simulation 알고리즘으로 이어집니다.
## 비용 구조 {#cost}
Qubitization/QSP 계열의 비용은 보통 아래처럼 봅니다.
$$
\text{cost}
\approx
d\cdot \text{cost(block-encoding)}
+\text{cost(phase rotations)}
$$
$d$는 polynomial degree입니다. degree는 목표 함수, 시간 $t$, normalization $\alpha$, 오차 $\epsilon$에 의해 결정됩니다. phase rotation 자체보다 block-encoding 호출이 비싼 경우가 많습니다.
## 직관 {#intuition}
고전적으로 행렬 함수 $f(A)$를 구현하려면 eigenvalue마다 $f(\lambda)$를 적용하면 됩니다. 양자에서는 eigenvalue를 직접 읽으면 상태가 붕괴합니다. QSP/QSVT 계열은 eigenvalue를 측정하지 않고, 유니터리 회로의 간섭 구조 안에서 해당 변환이 일어나게 합니다.
이 점이 QPE 기반 알고리즘과의 큰 차이입니다. QPE는 고유값을 레지스터에 적고 조건부 연산을 하는 느낌이고, QSP/QSVT는 고유값에 대한 polynomial transformation을 coherent하게 직접 합성하는 느낌입니다.