출발점: block-encoding
유니터리 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
성공 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의 기본 생각
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가 하는 일
QSP에서 회로 구조는 거의 고정되어 있고, 구현할 함수는 phase sequence가 결정합니다. 같은 signal unitary를 쓰더라도 phase를 바꾸면 x, x^3, e^{-itx} 근사, sign 함수 근사 등으로 바뀝니다.
따라서 고급 회로설계에서는 두 문제가 분리됩니다.
- 좋은 block-encoding 또는 signal oracle을 만든다.
- 원하는 함수에 대응하는 QSP phase sequence를 합성한다.
두 번째 문제는 수치해석과 approximation theory의 영역입니다.
Hamiltonian simulation과 qubitization
해밀토니안 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 알고리즘으로 이어집니다.
비용 구조
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 호출이 비싼 경우가 많습니다.
직관
고전적으로 행렬 함수 f(A)를 구현하려면 eigenvalue마다 f(\lambda)를 적용하면 됩니다. 양자에서는 eigenvalue를 직접 읽으면 상태가 붕괴합니다. QSP/QSVT 계열은 eigenvalue를 측정하지 않고, 유니터리 회로의 간섭 구조 안에서 해당 변환이 일어나게 합니다.
이 점이 QPE 기반 알고리즘과의 큰 차이입니다. QPE는 고유값을 레지스터에 적고 조건부 연산을 하는 느낌이고, QSP/QSVT는 고유값에 대한 polynomial transformation을 coherent하게 직접 합성하는 느낌입니다.