Linear combination of unitaries with exponential convergence

기술 요약: 지수적 수렴을 갖는 유니터리의 선형 결합 (LCU)

문제 정의
선형 결합의 유니터리(Linear Combination of Unitaries, LCU)는 비유니터리 연산자를 구성하기 위해 유니터리 블록 인코딩을 구축하는 데 사용되는 양자 컴퓨팅의 기초적인 프리미티브로, 선형 시스템 해결, 개방형 양자 역학 시뮬레이션, 양자 특잇값 변환(QSVT) 등의 응용을 가능하게 한다. 그러나 기존의 일반적인 분해 방법들은 상당한 확장성 병목 현상에 직면해 있다. 널리 쓰이는 방식은 저차 테일러 전개(예: 유한 차분법)를 사용하여 비유니터리 연산자를 근사하는데, 이 경우 서브노멀라이제이션 계수 $\alpha$(비유니터리 연산자를 유니터리 내에 임베딩하기 위해 필요한 스케일링 인자)가 목표 오차의 역수에 대해 다항식적으로 증가($\alpha = \text{poly}(1/\epsilon)$)하게 된다. 이러한 관계는 사후 선택(post-selection)의 성공 확률을 저하시키거나 값비싼 진폭 증폭(amplitude amplification)을 필요로 하므로, 일반적인 LCU를 고정밀 애플리케이션이나 고정된 오차 예산을 가진 환경에서 구현하는 것을 비실용적으로 만든다. 희소하거나 구조화된 연산자에 대해서는 정확한 구성법이 존재하지만, 임의의 비유니터리 연산자를 위한 효율적인 일반 기법은 여전히 제한적이다.

방법론
저자들은 **푸리에 확장법(Fourier extension method)**에 기반한 일반적인 분해 방법을 제안한다. 이 방법은 국소적인 테일러 전개에 의존하는 대신, 더 큰 주기적 도메인 $[-\pi, \pi]$ 내의 부분 구간 $[-\pi/\eta, \pi/\eta]$에서 항등 사상 $f(\tau) = \tau$를 매끄러운 주기적 확장(smooth, periodic extension)을 통해 근사한다.

1. 푸리에 사인 급수(Fourier Sine Series): 함수 $f(\tau) = \tau$는 연속 최소제곱 최적화를 통해 유도된 계수 $a_k$를 갖는 사인 급수 $\sum a_k \sin(k\tau)$로 근사된다. 도메인 확장 계수 $\eta > 1$을 선택함으로써, 함수는 확장된 도메인 상에서 매끄럽고 주기적이 되며, 이를 통해 항의 수 $m$이 증가함에 따라 계수 $a_k$의 지수적 수렴을 가능하게 한다.
2. 연산자 분해: 사인 급수는 행렬 입력에 적용된다. $\sin(k\tau H) = (e^{ik\tau H} - e^{-ik\tau H}) / 2i$라는 항등식을 사용하여, 이 방법은 에르미트 연산자 $H$를 유니터리들의 선형 결합으로 표현한다. 일반적인 비유니터리 연산자 $A$에 대하여, 저자들은 이를 에르미트 성분($H_1$)과 반에르미트 성분($iH_2$)으로 분해한다. 최종 근사는 다음과 같이 $4m$개의 유니터리 연산자를 포함한다:
   $$A \approx \sum_{k=1}^m \frac{a_k}{2\tau} \left( i e^{-ik\tau H_1} - e^{-ik\tau H_2} - i e^{ik\tau H_1} + e^{ik\tau H_2} \right)$$
3. 계수 최적화: 논문은 계수를 선택하기 위한 두 가지 전략을 소개한다:
   • 최소제곱법 (Least-Squares, LS): 근사 오차 $\epsilon$을 최소화하여 지수적 수렴을 이끌어낸다.
   • 정규화 피팅 (Regularized Fitting): 푸리에 확장 기저의 과완전성(overcompleteness, $\eta > 1$)을 활용하여, 고정된 오차 예산 내에서 서브노멀라이제이션 $\alpha$ (계수들의 $L_1$-노름)를 최소화한다. 이는 오차와 서브노멀라이제이션 사이의 파레토 프런트(Pareto front)를 추적하며, 이를 통해 충실도(fidelity)를 희생하지 않으면서 $\alpha$를 줄일 수 있는 계수들을 선택할 수 있게 한다.

주요 기여

• 이중 로그 스케일의 서브노멀라이제이션을 갖는 지수적 수렴: 주요 이론적 기여는 근사 오차가 유니터리 개수 $m$에 대해 지수적으로 감소($m = O(\log(1/\epsilon))$)하는 동시에, 서브노멀라이제이션 $\alpha$는 $O(\log \log(1/\epsilon))$으로만 스케일링되는 분해법을 제시했다는 점이다. 이는 기존의 유한 차분법이 보이는 다항식 스케일링($\alpha = \text{poly}(1/\epsilon)$)에 비해 획기적인 개선이다.
• 정규화 전략: 저자들은 푸리에 확장 기저를 과완전한 것으로 취급함으로써, 정규화된 최적화 문제를 풀어 표준 최소제곱법보다 훨씬 낮은 서브노멀라이제이션을 갖는 계수 벡터를 찾아낼 수 있음을 입증하였다. 이를 통해 높은 충실도의 블록 인코딩을 구현할 수 있다.
• 회로 구현: 논문은 $4m$개의 유니터리 항을 제어하기 위해 $O(\log m)$개의 보조 큐비트를 사용하는 양자 회로 구현을 상세히 설명하며, $(\alpha, n_a, \epsilon)$-블록 인코딩을 달성한다.

결과
마르코프적 개방 양자 시스템(순수 탈위상 현상을 겪는 구동된 큐비트)의 상태 벡터 표현을 사용한 수치 시뮬레이션은 이론적 주장을 검증한다:

• 수렴성: 블록 인코딩의 오차는 $m$에 대해 지수적 수렴을 보이며, $m=16$일 때 배정밀도 부동 소수점 정확도($\epsilon \approx 10^{-12}$)에 도달한다.
• 서브노멀라이제이션: 최소제곱 계수의 경우, $m$이 증가함에 따라 $\alpha$가 완만하게 증가한다($\approx 5$). 그러나 정규화된 계수의 경우, $m$이 증가함에 따라 $\alpha$가 감소하며, $m=32$ 및 $m=64$에서 $\approx 2$만큼 낮은 값에 도달한다.
• 비용 효율성: 리소스 오버헤드를 나타내는 "비용" 지표 $\alpha m$은, 정규화된 계수가 최소제곱 계수보다 훨씬 낮은 서브노멀라이제이션으로 목표 오차를 달성할 수 있음을 보여준다. 예를 들어, $m=16$에서 정규화된 계수는 $m=8$인 최소제곱 항들과 대등한 정확도를 제공하면서도, 진폭 증폭 요구 사항을 1.74배 감소시킨다.

의의 및 주장
본 논문은 푸리에-LCU가 특정 구조적 대칭성이나 희소성 패턴에 국한되지 않는 다재다능하고 정확한 비유니터리 양자 컴퓨팅 프레임워크를 제공한다고 주장한다. 오차 감소와 서브노멀라이제이션 증가를 분리함으로써, 이 방법은 국소적 테일러 전사보다 우월한 "글로벌 근사 전략"을 제공한다.

저자들은 알고리즘적 이점(지수적 수렴)은 이론적으로 견고하지만, 실질적인 효용성은 관리 가능한 서브노멀라이제이션을 갖는 고품질 블록 인코딩을 구축할 수 있는 능력에 있다고 강조한다. 이는 과도한 서브노멀라이제이션으로 인해 신호가 노이즈와 구별 불가능해질 수 있는, 고정된 오차 예산이나 노이즈 플로어를 가진 하드웨어 환경에서 매우 중요하다. 이 방법은 QSVT 및 기타 비유니터리 맵을 필요로 하는 알고리즘을 위한 강력한 접근 지점 역할을 한다. 저자들은 엔드 투 엔드(end-to-end) 이점이 기저의 제어된 해밀토니안 시뮬레이션($e^{\pm ik\tau H}$)을 적절한 회로 깊이로 구현할 수 있는 능력에 달려 있으며, 이는 실제 배포를 위한 문제 특화적인 과제로 남아 있다고 언급하였다.