기술 요약: 양자 사선 고유투영 (Quantum Oblique Eigenprojection)

문제 정의

본 논문은 양자 컴퓨터에서 **사선 고유투영(oblique eigenprojections)**을 수행하는 데 따르는 과제를 다룹다. 헤르미트 행렬(고유 공간이 직교하는 경우)에 대한 양자 알고리즘은 양자 특잇값 변환(QSVT)과 같은 프레임워크를 통해 잘 확립되어 있지만, 일반적인 비정규(non-normal) 행렬은 상당한 장애물이 된다. 비정규 행렬의 경우, 힐베르트 공간은 일반화된 비직교 고유 부공간(generalized, non-orthogonal eigensubspaces)으로 분해된다. 과제는 입력 상태를 타겟 스펙트럼 영역(예: 단위 원판 내부의 고유값)과 연관된 특정 불변 부공간으로 투영하는 동시에, 보완적인 영역과 연관된 성분들을 억제하는 양자 알고리즘을 구축하는 것이다.

이 문제는 스펙트럼이 복소수인 경우 근본적으로 차단된다. 실수 스펙트럼의 경우와 달리, 복소 평면에서는 다항식이 타겟 영역의 지시 함수(indicator function)를 유의미한 오차 없이 근사하는 것이 불가능하다는 최대 절댓값 원리(maximum modulus principle)가 적용되기 때문이다. 결과적으로, 해석적 함수(및 그에 따른 다항식)에 의존하는 표준 QSVT 및 양자 고유값 변환(QEVT) 기법은 이 문제를 직접 해결할 수 없다.

레졸번트 적분(resolvent integration)(코시 적분 공식을 사용하는 방식)과 같은 기존 접근 방식은 타겟 스펙트럼을 둘러싸는 경로를 따라 행렬 레졸번트 $(\zeta I - A)^{-1}$를 적분하여 비해석적 함수를 처리할 수 있다. 그러나 이러한 방법들은 결정적인 비효율성을 갖는다: 이들은 $\alpha = \Theta(\|\Pi\|/\delta)$로 스케일링되는 **정규화 인자(normalization factor)**를 초래한다(여기서 $\|\Pi\|$는 투영의 노름이고 $\delta$는 스펙트럼 갭이다). 이 팽창된 정규화 인자는 투영을 서브루틴으로 사용하는 모든 알고리즘의 쿼리 복잡도를 크게 증가시키는데, 특히 블록 인코딩의 성공 확률이 $\alpha^2$에 반비례하기 때문이다.

방법론

저자들은 이산화된 레졸번트 적분으로부터 생성된 블록 인코딩의 전체 구조를 활용함으로써 표준 레졸번트 적분 방법을 개선하는 새로운 접근 방식을 제안한다.

1. 이산화된 레졸번트 적분: 사선 고유투영 $\Pi$는 트래피조이드 규칙(trapezoidal rule)을 사용하여 레졸번트의 경로 적분을 이산화함으로써 근사된다. 이는 $\Pi \approx \frac{1}{n} \sum_{j=0}^{n-1} (I - \omega^{-j}_n A)^{-1}$ 형태의 이동된 레졸번트들의 합을 생성한다.
2. 블록 인코딩 구축: 표준 방식은 이러한 이동된 레졸번트들을 포함하는 블록 대각 행렬 $M$을 구성하고 이를 QSVT를 사용하여 역행렬을 구한다. 헤더마드 변환을 보조 레지스터에 적용하면, 결과적인 역행렬의 좌상단 블록이 $\Pi$를 근사하게 된다. 그러나 나머지 블록들은 구조화되지 않은 상태로 남게 되며, 이로 인해 정규화 인자는 전체 행렬의 최악의 노름인 $\Theta(1/\delta)$에 의해 결정된다.
3. 이산 푸리에 변환(DFT) 분석: 본 연구의 핵심 통찰은 역행렬 $M^{-1}$의 블록들이 임의적인 것이 아니라 **순환 구조(circulant structure)**를 가진다는 점이다. 저자들은 헤더마드 변환 대신 **양자 푸리에 변환(QFT)**을 사용하여 $M^{-1}$을 공액(conjugate)함으로써, 모든 블록 $(k, l)$이 이동된 레졸번트의 특정 이산 푸리에 모드 $S_m$에 대응함을 밝혀낸다.
   • 제0차 모드 $S_0$는 고유투영 $\Pi$를 근사한다.
   • 고차 모드 $S_m$은 스펙트럼-집합 조건(예: 행렬이 대각화 가능하거나 유계된 수치 범위를 갖는 경우) 하에서 기하급수적으로 감소한다.
4. 양방향 블록 프리컨디셔닝(Two-Sided Block Preconditioning): 저자들은 푸리에 기저에서 작동하는 양방향 블록 프리컨디셔닝 기법을 도입한다. 이들은 계산 기저에서 대각 행렬인 스케일링 연산자 $T$를 적용하여 역전 전의 행렬을 수정한다.
   • 스케일링 파라미터 $t$가 감소함에 따라, 첫 번째 블록 행과 열은 커진다.
   • 그러나 이 프리컨디셔닝은 추출된 좌상단 블록의 역-갭 성장(inverse-gap growth)을 억제하여, 정규화 인자를 $\Theta(1/\delta)$에서 $O(c \|\Pi\|)$로 감소시킨다(여기서 $c$는 스펙트럼-집합 조건에 따른 상수이다).
   • 이 정규화는 이론적으로 가능한 최솟값인 $\|\Pi\|$에 근접한 최적의 수준이다.

주요 결과

본 논문은 세 가지 주요 정리를 확립한다:

• 정리 1 (행렬 레졸번트의 DFT): 푸리에 기저에서의 레졸번트 적분의 이산화 블록들에 대한 폐쇄형 표현(closed-form expression)을 제공한다. 이는 블록들이 이동(shift)의 거듭제곱에 따라 기하급수적으로 감소하는 성질을 가짐을 보여준다.
• 정리 2 (단위 원판 투영): 스펙트럼이 단위 원과 분리된 행렬 $A$에 대해, 내부 부공간으로의 사선 고유투영 $\Pi$를 정규화 인자 $\alpha_\Pi = O(c \|\Pi\|)$와 쿼리 복잡도 $O\left(\frac{c \alpha_A \|\Pi\|}{\delta} \log \frac{c \|\Pi\|}{\varepsilon} \log \frac{1}{\varepsilon}\right)$로 블록 인코딩할 수 있음을 입증한다. 이는 쿼리 복잡도는 표준 방식과 일치하지만 정규화 인자는 획기적으로 개선된 결과이다.
• 정리 3 (일반 영역): 임의의 복소 평면 타겟 영역으로 결과를 확장한다. 해석적 분리 맵 $f$(예: 타겟 영역을 단위 원판으로 매핑하는 유리 함수)를 사용하여, 문제를 $f(A)$에 대한 단위 원판 케이스로 환원한다. 비용은 $f(A)$와 단위 원 사이의 갭에 따라 결정된다.

응용 분야

저자들은 이 개선된 프리미티브가 다음 세 가지 특정 응용 분야에서 상당한 속도 향상을 가져옴을 보여준다:

1. 복소 스펙트럼의 고유상태 준비: Low와 Su의 QEVT 알고리즘을 복소 고유값을 갖는 비정규 행렬으로 확장한다. 새로운 방법은 고유상태를 준비하는 데 있어 쿼리 복사도가 $O(\|\Pi\|^2 / (\eta \delta))$로 스케일링되는데, 이는 표준 레졸번트 적분 방식의 $O(\|\Pi\|^2 / (\eta \delta^2))$ 스케일링에 비해 **이차적 개선(quadratic improvement)**을 달성한 것이다. 이 개선은 진폭 증폭(amplitude amplification) 횟수가 갭에 독립적으로 $O(\|\Pi\|/\eta)$로 스케일링되기 때문에 발생한다.
2. 연속 시간 대수 리카티 방정식(Continuous-Time Algebraic Riccati Equations): 최적 제어 및 양자 화학에서 발생하는 이 방정식들을 푸는 것은 비정규 해밀토니안의 불변 부공간으로 투영하는 문제로 귀결된다. 이 방법은 Rodenas-Ruiz, Zhao, Lee의 기존 솔버에 비해 갭 의존성을 **세제곱 개선(cubically improves)**하며, 전체 복잡도에서 $1/\delta$ 인자 두 개를 제거한다.
3. 상식 실베스터 방정식(Ordinary Sylvester Equations): 블록 행렬의 불변 부공간으로 투영함으로써 $AX + XB = C$를 해결한다. 이 방법은 Wang과 Liu의 직접 증강 방법의 갭 의존성을 **이차적으로 개선(quadratically improves)**한다.

의의 및 주장

본 논문은 이 작업이 비정규 행렬과 관련된 양자 알고리즘을 위한 근본적인 프리미티브를 제공한다고 주장한다. 정규화 인자를 $\|\Pi\|$에 가깝게 달성하면서도 역 갭에 대해 거의 선형적인 쿼리 복잡도를 유지함으로써, 저자들은 Hermitian 행렬을 위한 QSVT의 효율성과 비-Hermitian 문제를 해결하는 데 필요한 능력 사이의 간극을 메운다.

저자들은 다음과 같은 이유로 본 연구의 중요성을 강조한다:

• 비해석적 함수를 위해 사용되어 온 기존의 "팽창된 정규화 인자" 문제를 해결했다.
• 비해석적 행렬 함수(특히 사선 고유투영)가 다항식 근사를 사용할 수 없음에도 불구하고, QSVT와 유사한 복잡도로 양자 컴퓨터에서 구현될 수 있음을 입증했다.
• DFT를 통한 전체 블록 구조 분석과 양방향 프리컨디셔닝을 적용하는 기술은 블록 인코딩을 최적화하기 위한 새로운 패러다임을 제시하며, 이는 다른 비해석적 함수에도 적용될 수 있다.

저자들은 연구 범위에 대해 신중한 태도를 유지하며, 프리컨디셔닝이 레졸번트의 특정 폐쇄형 DFT에 의존하며, 모든 구성(예: Wang과 Liu의 곱-레졸번트 접근법)에 즉각적으로 적용되지는 않는다고 언급했다. 또한, Hermitian 행리에 대한 QSVT의 비용이 타겟 함수의 기하학적 구조에 의해 결정되는 것과 달리, 본 모델의 비용은 입력 행렬의 스펙트럼 갭에 의해 지배된다는 점을 명시했다.