An efficient Pauli decomposition algorithm for structured matrices

기술 요약: 구조화된 행렬을 위한 효율적인 파울리 분해 알고리즘

문제 정의
고전적인 $2^n \times 2^n$ 행렬을 파울리 문자열(Pauli strings)의 선형 결합으로 분해하는 것은, 특히 화학, 머신러닝, 금융 분야에서 근미래 양자 알고리즘(near-term quantum algorithms)의 엔드 투 엔드 구현을 위한 핵심적인 병목 구간입니다. VQE(Variational Quantum Eigensolver)나 선형 대수 솔버와 같은 많은 알고리즘은 입력 데이터가 파울리 문자열의 LCU(Linear Combination of Unitaries) 형태로 제공된다고 가정합니다. 그러나 일반적인 고전적으로 지정된 행렬에 대해서는 이러한 분해가 사전에 알려져 있지 않습니다.

일반적인 조밀한(dense) 행렬에 대한 기존 알고리즘들은 큐비트 수 $n$에 대해 지수적으로 스케일링됩니다. 가장 단순한 접근 방식은 $O(32^n)$의 시간을 요구하며, 기존의 최선책(예: PennyLane)은 $O(n4^n)$으로 스케일링됩니다. 이러한 지수적 비용은 최악의 경우 행렬이 모든 $4^n$개의 파울리 기저 요소에 걸쳐 지지(support)를 가질 수 있어, 모든 계수를 복구해야 하기 때문에 발생합니다.

본 논문은 파울리 분해 문제의 **약속된 버전(promise version)**을 다룹니다. 이는 입력 행렬 $M$이 오직 $k = \text{poly}(n)$개의 파울리 문자열에 대해서만 지지를 가진다는 것이 보장된다고 가정합니다. 또한, 행렬은 전체 $2^n \times 2^n$ 행렬을 메모리에 구축하지 않고도 특정 행이나 열의 비제로(non-zero) 항목을 검색할 수 있는 **고전적 희소 쿼리 모델(classical sparse query model)**을 통해 접근됩니다. 목표는 $n, k, \log(1/\delta)$에 대한 다항식 시간 내에 높은 확률로 정확한 파울리 분해(파울리 문자열과 그 계수의 집합)를 복구하는 것입니다.

방법론
저자들은 파울리의 이진 심플렉틱 형식(binary symplectic form)과 약속된 희소성($k$)을 활용하는 무작위 고전 알고리즘을 제안합니다. 이 알고리즘은 문제를 세 가지 주요 단계로 분해합니다:

1. 활성 파울리-X 부분($x$)의 발견:
   행 인덱스 $v$, 열 인덱스 $u$, 그리고 파울리-X 부분 $x$ 사이의 관계 $x = u \oplus v$를 설명하는 보조정리 1(Lemma 1)을 사용하여, 알고리즘은 행렬의 무작위 행들을 쿼리합니다. 비제로 항목들의 열 인덱스를 수집하고 이를 행 인덱스와 XOR함으로써, 알고리즘은 분해에 존재하는 구별되는 $x$ 비트 문자열의 집합 $X$를 식별합니다. 이 단계는 무작위 쿼리가 높은 확률로 활성 $x$ 문자열을 드러낼 것임을 보장하는 불리언 불확정성 원리(Fact 1)에 의존합니다.

2. 고유한 $x$ 문자열의 디코딩:
   각 $x$에 대해, 알고리즘은 해당 $x$가 "고유"한지(즉, 정확히 하나의 파울리 문자열과 연관되어 있는지, $p_x = 1$) 확인합니다. 고유하다면, 쿼리 함수 $b_x(u) = M_{x \oplus u, u}$는 단일 월쉬 캐릭터(Walsh character) $\beta_x(z)(-1)^{z \cdot u}$로 축소됩니다. 알고리즘은 영 벡터와 표준 기저 벡터에서 $b_x$를 평가함으로써 연관된 파울리-Z 부분 $z$와 계수 $\beta$를 복구합니다. 후보 솔루션이 쿼리된 지점들과 우연히 일치하는 퇴화된 사례가 아님을 검증하기 위해 무작위 입력을 사용하는 인증 단계가 수행됩니다.

3. 퇴화된 $x$ 문자열의 디코딩:
   만약 $x$가 "퇴화"되었다면(즉, $p_x \geq 2$인 파울리 문자열과 연관됨), 문제는 희소 월쉬-하다마르 스펙트럼(sparse Walsh-Hadamard spectrum)을 복구하는 문제로 귀결됩니다. 알고리즘은 무작위 폴딩(random folding) 기법을 채택합니다:

   • 무작위 이진 행렬 $R$을 사용하여 $n$-비트 스펙트럼 인덱스($z$)를 $m$-비트 빈(bin)으로 매핑합니다 ($m \ll n$).
   • 이 "폴딩" 과정은 높은 확률로 개별 $z$ 문자열을 "싱글톤 빈(singleton bin)"으로 격리합니다.
   • 싱글톤 빈의 경우, 알고리즘은 시프트된 쿼리(shifted queries)를 사용하여 $z$ 문자열의 비트와 계수를 결정합니다.
   • 복구된 항들은 잔여 함수(residual function)에서 차감되며, 모든 $x$에 대한 항을 찾을 때까지 이 과정이 반복됩니다.
   • 최종적인 무작위 검증을 통해 누락된 항이 없는지 확인합니다.

주요 기여

• 알고리즘 설계: 본 논문은 $k$-희소성 및 희소 쿼리 접근이라는 약속 하에서 파울리 분해 문제를 해결하는 무작위 고전 알고리즘(Algorithm 1)을 제시합니다.
• 복잡도 개선: $n$에 대해 지수적으로 스케일링되는 기존 방법들과 달리, 제안된 알고리즘은 $n, k, \log(1/\delta)$에 대한 다항식의 쿼리 및 실행 시간 복잡도를 달성합니다.
• 이론적 보장: 알고리즘은 사용자가 선택한 임의의 $\delta \in (0, 1)$에 대해 적어도 $1-\delta$의 확률로 성공합니다. 저자들은 각 단계(발견, 고유 디코딩, 퇴화 디코딩)에 대한 실패 확률에 대한 엄격한 경계값을 제공합니다.
• 희소 월쉬-하다마르 기법: 본 연구는 무작위 폴딩과 시프트 기반 비트 복구를 활용하여, 파울리 분해의 맥락에 불리언 큐브에서의 희소 복구 기법(특히 희소 월쉬-하다마르 디코딩)을 적용했습니다.

결과

• 수치적 벤치마크: 저자들은 $n = 2$에서 $30$, $k = 2^n$인 무작위 인스턴스에 대해 알고리즘을 테스트했습니다.
  • 작은 $n$ ($n < 10$)의 경우, 무작위 알고리즘의 오버헤드로 인해 기존의 PennyLane PauliDecompose 루틴보다 느립니다.
  • $n=10$ 부근에서 교차점이 발생합니다. $n > 10$인 경우, 제안된 알고리즘은 지수 시간 베이스라인보다 현저히 뛰어난 성능을 보입니다.
  • 관찰된 실행 시간 및 쿼리 횟수는 이론적 경계값과 일치하게 $n$에 대해 다항식으로 스케일링됩니다.
  • 모든 테스트 실행에서 알고리즘은 실패 없이 전체 분해를 성공적으로 복구했습니다.
• 확장성: 알고리즘은 전체 행렬을 구축하거나 조밀한 분해 알고리즘을 실행하는 것이 계산적으로 불가능한 영역인 $n=30$까지의 인스턴스를 성공적으로 처리했습니다.

의의 및 주장
본 논문은 일반적인 행렬에 대해 파울리 분해를 찾는 것이 지수적으로 어렵지만, 파울리 기저에서 희소함이 보장된 행렬에 대해서는 효율적으로 해결 가능함을 주장합니다. 이 영역은 구조화된 고전 데이터를 사용하는 근미래 양자 알고리즘에 매우 유용합니다.

저자들은 자신의 알고리즘이 $k = \text{poly}(n)$인 **약속된 문제(promise problem)**를 위해 특별히 설계되었음을 강조합니다. 이들은 일반적인 조밀한 케이스를 해결한다고 주장하지 않습니다. 이 연구의 의의는 파울리 분해를 필요로 하는 양자 알고리즘을 위한 효율적인 고전적 전처리(preprocessing)를 가능하게 하여, 엔드 투 엔드 양자 워크플로우의 주요 병목 현상을 제거할 수 있다는 점에 있습니다. 또한, 간결한 고전적 규칙에 의해 정의되거나 쿼리 접근만 가능한 신뢰할 수 없는 서버에 데이터가 보유된 경우와 같은 구체적인 응용 맥락을 강조합니다.

논문은 도출된 상한(upper bounds)이 느슨할 수 있으며, 향후 연구에서 더 타이트한 경계값, 하한(lower bounds) 및 근사적으로 희소한 행렬로의 확장을 탐구할 수 있다는 점을 언급하며 겸허하게 마무리됩니다.