Matrix Product Operators In The Age of Block Encoding

기술 요약: 블록 인코딩 시대의 행렬 곱 연산자(Matrix Product Operators)

문제 정의
선형 결합 유니타리(Linear Combination of Unitaries, LCU) 및 블록 인코딩 프레임워크에 기반한 양자 시뮬레이션 알고리즘은 특히 해밀토니안 시간 진화(Hamiltonian time evolution)를 시뮬레이션할 때 상당한 자원 오버헤드 문제에 직면하곤 한다. 전통적인 방식은 시간 진화 연산자 $e^{-itH}$를 명시적인 파울리 문자열(Pauli strings)의 합(테일러 급수)으로 전개한다. 그러나 $N$개의 사이트와 $T=O(N)$의 상호작용을 갖는 국소 스핀 체인(local spin chains)의 경우, 이러한 명시적 전개는 차수가 $K$인 다항식에 대해 $O(N^K)$로 스케일링되는 조합론적 파울리 항의 증가를 초사한다. 또한, 해밀토니안 $H$를 행렬 곱 연산자(MPO)로서 먼저 블록 인코딩한 후 양자 고윳값 변환(Quantum Eigenvalue Transformation, QET)을 적용하는 대안적 방법들은 종종 지수적인 정규화 페널티를 초래한다. 이 페널티는 비유니타리(non-unitary) 해밀토니안 MPO를 블록 인코딩하기 위해 필요한 국소 유니타리 딜레이션(local unitary dilation) 과정에서 발생하며, 이로 인해 정규화 인자 $\alpha_{dil}(H)$가 시스템 크기에 따라 지수적으로 증가하게 된다(예: $\sim 1.43^N$). 이는 성공 확률을 심각하게 저하시키고 과도한 진폭 증폭(amplitude amplification)을 요구하게 만든다.

방법론
저자들은 MPO를 단순히 블록 인코딩되어야 할 압축된 객체가 아니라, 양자 선형 대수를 위한 구조화된 중간 표현(Intermediate Representation, IR)으로 취급하는 "컴파일된 다항식(compiled-polynomial)" 접근법을 제안한다. 핵심 방법론은 세 가지 뚜렷한 단계로 구성된다:

1. 압축된 LCU로서의 MPO: 저자들은 MPO를 "가상 경로(virtual paths)"에 대한 압축된 Lcu 프로그램으로 해석한다. 각 로컬 MPO 텐서를 개별적으로 유니타리화하는 대신, 각 로컬 텐서를 로컬 유니타리 기저(예: 파울리 기저)로 전개한다. MPO의 가상 본드(virtual bonds)는 로컬 연산자의 시퀀스를 생성하는 유한 상태 오토마타(finite-state automaton)로 해석된다. 이를 통해 MPO를 계수 $c_\gamma$를 갖는 특정 파울리 문자열에 대응하는 가상 경로 $\gamma$들의 합으로 볼 수 있다.
2. 조건부 컴파일(Conditional Compilation): 저자들은 조건부 준비(conditional preparation) 및 선택(selection) 단계를 사용하여 MPO 구조로부터 LCU 회로를 직접 구축하는 블록 인코딩 컴파일러를 개발한다. 표준 LCU 회로($PREP^\dagger SELECT PREP$)는 일련의 조건부 단계로 일반화된다.
   • 조건부 준비 (CPREP): $N$개의 조건부 상태 준비 단계가 수행된다. 각 단계는 들어오는 가상 본드 라벨($a_{n-1}$)에 조건부로 로컬 연산자 라벨($\mu_n$)과 나가는 가상 본드 라벨($a_n$)을 준비한다. 이때 확률은 MPO 텐서로부터 유도된 "역방향 메시지(backward messages, $\beta_n$)"를 사용하여 인코딩되며, 이를 통해 전역 분포가 MPO 계수와 일치하도록 보장한다.
   • 조건부 선택 (SELECT): 준비된 경로 라벨에 따라 로컬 유니타리가 적용된다.
   • 정규화: 정규화 인자 $\alpha_{MPO}$는 모든 경로를 명시적으로 합산할 필요 없이, 절대값 전이 행렬(absolute-value transfer matrices)의 텐서 수축(tensor contraction)을 통해 효율적으로 계산된다.
3. 다항식 합성: 대상 유니타리 $e^{-itH}$는 먼저 MPO 표현 내에서 다항식 $P_\chi(t)$로 근사된다(테일러 전개를 사용). 이 다항식 MPO는 그 후 직접 블록 인코딩된다. 이는 해밀토니안 $H$를 먼저 블록 인코딩한 후 QET를 적용하는 표준 경로와 대조된다.

주요 기여

• 가상 경로 LCU: 본 논문은 MPO를 가상 경로에 대한 압축된 LCU 프로그램으로 해석함으로써, 텐서 네트워크 데이터 구조로부터 블록 인코딩 오라클을 체계적으로 조립하는 방법을 제시한다.
• 컴파일러 아키텍처: 조건부 준비 및 선택 단계를 사용하여 MPO 데이터 구조를 양자 회로로 변환하는 새로운 컴파일러를 제시하며, 이를 통해 텐서 네트워크를 양자 회로를 위한 유효한 중간 표현으로 취급한다.
• 병목 현상 회피: 다항식 변환을 (블록 인코딩 전) MPO 수준에서 컴파일하는 것이 두 가지 주요 병목 현상을 피할 수 있음을 입증한다:
  1. 명시적인 파울리 문자열의 조합론적 $O(N^K)$ 증가.
  2. 비유니타리 해밀토니안 MPO를 직접 블록 인코딩할 때 발생하는 지수적 정규화 페널티($\alpha_{dil}(H)$).

결과
저자들은 하이젠베르크 모델(Heisenberg model)과 변형된 버전(사이트 의존적 자기장 및 이량화 포함)에 대해 시스템 크기 $N=64$까지의 수치적 검증을 수행하였다.

• 본드 차원 스케일링: 해밀토니안 거듭제곱 $H^K$에 대해, 요구되는 MPO 본드 차원 $\chi$는 완만하게 성장한다(예: $10^{-6}$ 오차에서 $K=4$일 때 $\chi=24$). 이는 압축되지 않은 스케일링인 $5^K$보다 현저히 낮다.
• 정규화: 컴파일된 유니타리 MPO의 정규화 인자 $\alpha_{MPO}(P_\chi)$는 큰 $N$과 $K$에 대해서도 작은 상수 범위 내에서 유지된다. 이는 H-first MPO-dilation 경로에서 관찰된 지수적 성장과 극명한 대조를 이룬다.
• 복잡도: 전체 회로 비용 프록시는 $C_3 \sim \alpha_{MPO}(P_\chi) N \chi^2$로 스케일링된다. 테스트된 영역에서 이는 명시적 파울리 문자열 LCU 확장의 $O(N^K)$ 스케일링에 비해 다항식적인 속도 향상을 나타낸다. 구체적으로, $\chi=4$인 필드 변형 모델의 경우 비용은 $N^{1.17}$으로 스케일링되었고, 이량화 모델의 경우 $N^{1.35}$로 스케일링되어 선형 스케일링에 근접하였다.

의의 및 주장
본 논문은 텐서 네트워크를 단순한 압축 표현이 아닌 컴파일러 분석을 위한 구조화된 데이터로 취급하는 것이 양자 알고리즘을 가속화하는 새로운 길을 열어준다고 주장한다. 주요 의의는 (해밀토니안을 다항식 MPO로 클래식하게 전처리한 후 컴파일하는) 작업 순서를 변경하는 것이 자원 요구 사항을 극적으로 변화시킬 수 있음을 보여준 데 있다.

저자들은 자신들의 방법이 명시적인 파울리 문자열 증가와 기존 MPO 기반 블록 인코딩 전략의 지수적 정규화 페널티를 피함으로써 다항식적인 속도 향상을 제공한다고 단언한다. 결론적으로 이 접근법은 MPO 본드 차원과 경로 정규화가 완만한 근사적 유니타리 실시간 전파기(approximately unitary real-time propagators)에 특히 효과적이다. 저자들은 오라클 비용, 반복 횟수 및 성공 확률 스케일링을 결합한 종합적인 분석이 필요하므로, 큐비타이제이션(qubitization) 방법과의 완전한 비교는 여전히 열려 있는 과제라고 겸허히 언급하였다. 또한, 향-후 연구로서 멀티프로덕트 공식(multiproduct formulas)과 이 컴파일러를 결합하거나 비유니타리 함수에 적용하는 방안을 제안하였다.