Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth

기술 요약: 투 타워 양자 행렬 연쇄 곱셈 (Two-Tower Quantum Matrix Chain Multiplication)

문제 정의
행렬 연쇄 곱셈(Matrix chain multiplication)은 $W = M^{(0)} \cdots M^{(K-1)}$를 계산하는 것으로 정의되며, 여기서 $M^{(k)} \in \mathbb{R}^{P_k \times P_{k+1}}$이다. 이는 과학적 계산, 머신러닝, 그래프 분석에서 근본적인 연산이다. 고전적으로 $K$개의 서로 다른 행렬의 곱을 계산하려면 $O(KN^\omega)$의 산술 연산(여기서 $\omega < 2.372$)이 필요하며, 무제한 병렬성을 사용하더라도 회로 깊이는 $O(\log K \cdot \log N)$으로 증가한다.

양자 영역에서 기존의 선형 대수 서브루틴은 일반적으로 블록 인코딩(block-encoding)에 의존하며, 이는 행렬을 유니터리 행렬의 하위 블록으로 임베딩하는 방식이다. 서로 다른 행렬들의 체인(chain)에 대해, 블록 인코딩 접근 방식은 일반적으로 회로 깊이가 $K$에 따라 선형적으로 증가($O(K \cdot \text{polylog}(N))$)하고, 보조 큐비트(ancilla qubit) 수가 $K$와 함께 증가하는 문제를 겪는다. 또한, 블록 인코딩 접근 방식에서의 전체 서브노멀라이제이션 계수(subnormalization factor)는 개별 계수들의 곱($\prod \alpha_k$)이 되며, 이는 $K$가 증가함에 따라 성공 확률을 기하급수적으로 작게 만들 수 있다. 단일 행렬의 거듭제곱($A^K$)에 대해서는 양자 싱귤러 값 변환(QSVT)이 속도 향상을 제공하지만, 현재의 방법론으로는 서로 다른 행렬들의 체인에 대해 이와 유사한 깊이 독립적인 속도 향상을 구현하는 방법이 알려져 있지 않다.

방법론: 투 타워 구성 (The Two-Tower Construction)
저자들은 "투 타워 행렬 곱셈(Two-Tower Matrix Multiplication)"이라는 양자 서브루틴을 제안한다. 이 구성은 곱 $W$를 양자 상태의 진폭(amplitude)에 인코딩한다. 이 구성은 두 가지 주요 통찰에 기반한다:

1. 상태 준비의 벡터화 (State Preparation as Vectorization): 행렬의 엔트리를 진폭으로 인코딩하는 것은 행 단위 벡터화와 동일하다.
2. 크로네커 곱 항등식 (Kronecker Product Identity): $AXB$의 벡터화는$\text{vec}(AXB) = (B^T \otimes A)\text{vec}(X)$를 만족한다.

이 알고리즘은 두 개의 병렬 레이어에 걸쳐 상태 준비 연산자를 인터리빙(interleaving)함으로써, 레지스터 스왑과 순차적 의존성을 피하며 두 행렬 곱 서브루틴(Bernasconi 등 [15]의 연구)을 임의의 체인 길이 $K$로 일반화한다.

• 레지스터 할당: 회로는 $K+1$개의 레지스터를 사용한다. 행렬 체인 $M^{(0)}, \dots, M^{(K-1)}$에 대해, 레지스터는 행 및 열 인덱스를 보유하도록 할당된다. 인접한 행렬들은 레지스터를 공유하며, 이는 총 큐비트 수가 $\Theta(\sum_{k=0}^K \log P_k)$임을 의미한다.
• 두 개의 레이어:
  • 레이어 1 (OP(L)): 모든 짝수 인덱스 행렬($M^{(0)}, M^{(2)}, \dots$)에 대해 상태 준비 연산자 $SP(M^{(k)})$를 적용한다. 이 연산자들은 서로 분리된 레지스터 쌍에 작용하며 병렬로 실행된다.
  • 레이어 2 (OP(R)): 모든 홀수 인덱스 행렬($M^{(1)}, M^{(3)}, \dots$)에 대해 켤레 연산자 $SP(M^{(k)})^\dagger$를 적용한다. 이 연산자들 역시 (구체적으로는 짝수 인덱스 레지스터 사이의 공유 경계에) 분리된 쌍에 작용하며 병렬로 실행된다.
  • $K$가 짝수인 경우의 특수 사례: $K$가 짝수이면, 마지막 행렬 $M^{(K-1)}$은 오른쪽 이웃이 없다. 이 경우 $SP^\dagger$ 대신 모듈러 상태 준비(Modular State-Preparation, MSP) 연산자를 사용한다. 이 연산자는 공유 인덱스를 $|0\rangle$으로 축소하면서, 손실될 수 있는 출력 열 레지스터를 보존한다.
• 축약 메커니즘 (Contraction Mechanism): 핵심 메커니즘은 $SP(M)^\dagger |i, j\rangle$가 행렬 엔트리에 비례하는 진폭을 가지고 상태를 $|0, 0\rangle$으로 투영한다는 성질에 기초한다. 한 행렬에 $SP$를 적용하고 그 이웃인 행렬에$SP^\dagger$를 공유 레지스터 상에서 적용함으로써, 회로는 양자 중첩을 통해 모든 공유 인덱스(내적)를 동시에 합산하며, 결과적으로 행렬 곱셈을 수행한다.

주요 결과 및 복잡도

• 회로 깊이: 총 회로 깊이는 $O(\max_k \text{polylog}(P_k P_{k+1}))$이다. 결정적으로, 이 깊이는 체인 길이 $K$와 무관하다. 이는 각 행렬 $M^{(k)}$를 폴리로그 시간 내에 양자 상태로 로드할 수 있음(예: QRAM 활용)을 전제로 한다.
• 큐비트 수: 알고리즘은 $O(\sum_{k=0}^K \log P_k)$개의 큐비트를 요구한다. $K$개의 $N \times N$ 정사각 행렬에 대해, 이는 $\Theta(K \log N)$이다. 이는 고전 메모리($O(KN^2)$)에 비해 지수적인 압축을 나타내지만, $K$로부터 자유롭지는 않다. 즉, 이 알고리즘은 큐비트 수를 희생하여 깊이를 줄인다.
• 게이트 수: 총 게이트 수는 $K$에 선형적이며, 구체적으로 $\Theta(K \cdot \text{polylog}(N))$이다. 이는 총 $K$개의 상태 준비 연산자가 적용되기 때문이다.
• 신호 가중치 ($\Omega_W$): 출력 상태는 정규화 계수 $N = 1/\prod \|M^{(k)}\|_F$에 의해 스케일링된 원하는 곱 $W$를 포함한다. 신호 가중치는 $\Omega_W = \|W\|_F^2 / \prod \|M^{(k)}\|_F^2$로 정의된다.
  • $\Omega_W \leq 1$이다.
  • 조건수가 좋은 행렬(평탄한 스펙트럼)의 경우, $\Omega_W$는 $K$에 따라 지수적으로 감소한다.
  • 스펙트럼 구조가 집중된 행렬(rank-1에 가까운 경우)의 경우, $\Omega_W$는 1에 가깝게 유지된다.
  • 저자들은 진폭 증폭(Amplitude Amplification)을 통해 $\Omega_W$를 상수로 높일 수 있지만, 이 과정에서 $O(1/\sqrt{\Omega_W})$의 반복 횟수가 발생하여 $K$에 대한 의존성이 다시 도입된다는 점을 언급한다.

기여

1. 깊이 독립적 서브루틴: 회로 깊이가 $K$에 독립적인 양자 행렬 연쇄 곱셈 서브루틴을 제공하여, 기존의 $K$에 따라 깊이가 증가하는 방식들을 개선하였다.
2. 정확성 증명: 임의의 체인 길이 $K$(홀수 및 짝수 모두)에 대한 정확성 증명을 제시하였다.
3. 체인-벡터 특화: $Wv$를 계산하기 위한 특화된 버전(행렬 체인이 벡터에 적용되는 경우)을 제공하며, 이는 반복 솔버 및 파워 메서드(power methods)에 유용하다.
4. 오픈 소스 구현: Qiskit 및 QCLAB 프레임워크를 통한 공개 구현을 제공한다.

의의 및 주장
본 논문은 투 타워 알고리즘을 행렬 인코딩된 상태 위에서 작동하는 다운스트림 양자 알고리즘을 위한 깊이 효율적인 빌딩 블록으로 포지셔닝한다. 저자들은 이 알고리즘의 이점이 행렬 엔트리의 전체 토모그래피(tomography)보다는 진폭 추정(Amplitude Estimation)을 통해 추출 가능한 집계된 양(예: 노름, 트레이스, 내적 또는 스펙트럼 특성)을 요구할 때 실현된다고 명시한다.

식별된 구체적인 응용 분야는 다음과 같다:

• 노름 추정 및 분산 추정.
• 그래프 스펙트럼 분석 (보행 횟수 계산 또는 혼합 추정을 위한 $A^K$ 계산).
• 체인 구조를 가진 연산자를 이용한 선형 시스템 해결 (HHL 또는 Neumann-series LCU를 통해).
• 양자 머신러닝 커널 평가.
• 반복적 수치 방법 (예: 파워 메서드, 크릴로프 부공간(Krylov subspace) 구축).

저자들은 신호 가중치 문제에 대해 신중한 입장을 유지한다. 즉, 깊이는 $K$와 무관하지만 신호 가중치는 감소할 수 있으며, 이를 위해 진폭 증폭이 필요하여 $K$에 따른 비용이 다시 발생한다는 점을 인정한다. 따라서 이들은 모든 행렬 체인 작업에 대한 보편적인 지수적 속도 향상을 주장하는 것이 아니라, 특정 트레이드오프, 즉 큐비트 자원(선형 $K$)을 사용하여 회로 깊이(상수 $K$)를 확보하는 것을 주장한다.

향후 연구 방향
논문은 향 미래 연구를 위한 세 가지 구체적인 방향을 제시한다:

1. 하이브리드 전략: 신호 가중치 감소를 관리하기 위해 투 타워(상수 깊이, 증가하는 큐비트)와 블록 인코딩(증가하는 깊이, 더 적은 큐비트) 사이를 교차 사용하는 방식.
2. 복소수 행렬: 복소수 값 행렬로의 확장.
3. 유니터리 체인: 양자 시뮬레이션 및 프로세스 토모그래피를 위한 유니터리 연산자 체인의 일반화.