왜 polynomial인가
행렬 A에 대한 함수 f(A)를 직접 구현하기 어렵다면, 다항식으로 근사합니다.
$$
f(A)\approx p(A)=\sum_{k=0}^{d} c_k A^k
$$고유값 관점에서는 A|u_j\rangle=\lambda_j|u_j\rangle일 때 아래가 됩니다.
$$
p(A)|u_j\rangle=p(\lambda_j)|u_j\rangle
$$따라서 스펙트럼 구간에서 p(x)가 f(x)를 잘 근사하면 행렬 함수도 잘 근사됩니다.
구간 스케일링
Chebyshev 다항식은 보통 x\in[-1,1]에서 다룹니다. 행렬 스펙트럼이 다른 구간에 있으면 먼저 스케일링합니다.
$$
\tilde A={2A-(b+a)I\over b-a}
$$그러면 A의 고유값이 [a,b]에 있을 때 \tilde A의 고유값은 [-1,1]에 들어갑니다. QSVT에서도 block-encoding은 보통 singular value가 [-1,1] 또는 [0,1] 범위로 정규화된 형태를 사용합니다.
Chebyshev 다항식
Chebyshev 다항식은 아래로 정의됩니다.
$$
T_k(x)=\cos(k\arccos x)
$$처음 몇 개는 아래입니다.
$$
T_0(x)=1,\quad T_1(x)=x,\quad T_2(x)=2x^2-1,\quad T_3(x)=4x^3-3x
$$여기서 가장 작은 출발점은 사인·코사인의 2배각 공식입니다. 예를 들어 \cos(2\theta)=2\cos^2\theta-1이므로 x=\cos\theta라고 두면 T_2(x)=2x^2-1이 바로 나옵니다. 마찬가지로 \cos(3\theta)를 전개하면 T_3(x)=4x^3-3x가 됩니다. 즉 Chebyshev는 낯선 고급 다항식이라기보다, 삼각함수 각도 곱셈을 x의 다항식으로 다시 쓴 것입니다.
재귀식도 중요합니다.
$$
T_{k+1}(x)=2xT_k(x)-T_{k-1}(x)
$$Chebyshev basis는 [-1,1]에서 수치적으로 안정적이고, minimax 근사와 연결됩니다. 그래서 Hamiltonian simulation, QSP polynomial 설계, spectral filtering에서 자주 등장합니다.
Chebyshev expansion
함수 f(x)를 아래처럼 전개합니다.
$$
f(x)\approx \sum_{k=0}^{d} a_k T_k(x)
$$polynomial approximation에서 Chebyshev가 편한 이유도 2배각 감각과 이어집니다. T_k(\cos\theta)=\cos(k\theta)라서, 함수의 모양을 여러 주파수의 cos 성분으로 나눈 뒤 다시 x에 대한 다항식으로 옮겨 적는다고 볼 수 있습니다. 회로설계에서는 이 전개 계수와 필요한 차수가 곧 block-encoding 호출 횟수, phase sequence 길이, 근사 오차로 이어집니다.
복소 지수 함수에는 Bessel function 계수가 등장합니다.
$$
e^{-i\tau x}
=
J_0(\tau)+2\sum_{k=1}^{\infty}(-i)^kJ_k(\tau)T_k(x)
$$이 식은 Hamiltonian simulation에서 e^{-iHt}를 Chebyshev 다항식으로 근사하는 출발점이 됩니다.
자주 근사하는 함수들
| 함수 | 쓰임 | 주의점 |
|---|---|---|
| e^{-itx} | Hamiltonian simulation | 차수가 시간 t와 오차에 의존 |
| 1/x | linear system | 0 근처 singularity 때문에 gap 필요 |
| \mathrm{sign}(x) | projector, eigenvalue filtering | 불연속점 주변에서 높은 차수 필요 |
| step function | spectral thresholding | 전이 구간을 둬야 구현 가능 |
QSP/QSVT의 parity 제약
QSP로 구현 가능한 polynomial에는 parity와 boundedness 제약이 있습니다. 대략적으로 degree d polynomial은 d와 같은 parity를 가져야 합니다.
$$
p(-x)=(-1)^d p(x)
$$실무적으로는 원하는 함수 f를 바로 근사하는 대신, 짝함수/홀함수 부분으로 나누거나 보조 polynomial을 추가해 QSP 조건을 만족시키는 방식으로 설계합니다.
오차를 어떻게 적는가
근사 오차는 보통 uniform norm으로 적습니다.
$$
\|f-p\|_\infty
=
\max_{x\in D}|f(x)-p(x)|
\le \epsilon
$$행렬 스펙트럼이 D 안에 있으면 operator norm 오차도 연결됩니다.
$$
\|f(A)-p(A)\|\le\epsilon
$$따라서 polynomial 설계 문서에는 반드시 근사 구간 D, 차수 d, 목표 오차 \epsilon, 함수의 gap 또는 smoothness 조건을 함께 적어야 합니다.