Approximate simulation of complex quantum circuits using sparse tensors

기술 요약: 희소 텐서를 이용한 복잡한 양자 회로의 근사 시뮬레이션

문제 정의
고전 컴퓨터를 이용한 양자 회로 시뮬레이션은 검증 가능한 양자 우위의 경계를 정의하고, 양자 다체 문제를 해결하며, 하드웨어 개발을 가이드하는 데 필수적이다. 텐서 네트워크 방법(예: Matrix Product States, Density Matrix Renormalization Group)이 복잡한 회로를 시뮬레이션하는 데 있어 최첨단 기술이 되었으나, 이들은 종종 효율성을 달ase하기 위해 기저에 깔린 대칭성이나 낮은 차원에 의존한다. 더욱이, 일반적인 고전 시뮬레이션은 복잡도 이론($P \neq NP$)에 의해 제한되므로, 보편적인 다항 시간 시뮬레이터를 구현할 수 없다. 저자들은 특이값 분해(SVD)나 기저에 깔린 대칭성, 또는 낮은 차원을 요구하지 않으면서, 전통적인 텐서 네트워크가 어려움을 겪을 수 있는 회로를 구체적으로 겨냥하여 양자 상태를 근사할 수 있는 시뮬레이션 도구의 필요성을 식별하였다.

방법론: 절단된 희소 텐서 시뮬레이션 (TruSTS)
본 논문은 희소하게 분포된 텐서를 사용하여 양자 회로를 근사적으로 시뮬레이션하는 방법인 TruSTS를 소개한다. 핵심 접근 방식은 $N$-큐비트 양자 상태 $|\psi\rangle$를 $k$개의 기저 상태($k \le 2^N$)의 선형 결합인 희소 상태 $|\phi\rangle$로 표현하는 것이다.

• 데이터 구조: 희소 상태는 크기가 $k$인 두 개의 고정 길이 배열을 사용하여 저장된다:
  1. $x[x_i]$: 기저 상태의 이진 비트스트링을 나타내는 정수 좌표 배열.
  2. $\alpha[\alpha_i]$: 해당 기저 상태에 대응하는 복소 확률 진폭 배열.
  3. 정수 포인터 nnz는 현재 채워진 요소의 수를 추적한다.
• 비트와이즈 컨트랙션 알고리즘: 양자 게이트(텐서 $\hat{U}$로 표현됨)를 적용하기 위해, 알고리즘은 압축 희소 행렬(Compressed Sparse Row, CSR) 곱셈에서 영감을 얻은 비트와이즈 정렬 전략을 채택한다:
  1. 게이트에 의해 결합되는 큐비트를 선택하기 위한 비트마스크를 정의한다.
  2. 상태 배열을 "결합되지 않은" 비트(마스크의 보집합)를 기준으로 정렬한다. 이는 게이트가 동일하게 작용하는 계산적으로 독립적인 서브 배열들로 기저 상태들을 그룹화한다.
  3. 각 서브 배열에 대해 독립적인 $4\times4$ 행렬 컨트랙션을 통해 게이트를 적용한다.
  4. 이 과정은 게이트 적용당 nnz를 최대 4배까지 증가시킬 수 있다.
• 절단 (Truncation): nnz의 지수적 증가를 방지하기 위해, 알고리즘은 각 게이트 적용 후 상태를 다시 크기 $k$로 절단한다. 저자들은 두 가지 절단 전략을 비교한다:
  • Top-k: 확률 진폭이 가장 큰 $k$개의 항을 유지한다.
  • Random-k: 무작위로 선택된 $k$개의 항을 유지한다.
  • 절단 과정에서 손실된 확률 질량을 보상하기 위해 $|\phi\rangle$에 재정규화 계수 $\gamma$를 적용한다.

주요 기여 및 이론적 유도
저자들은 재정규화 파라미터 $\gamma$와 시뮬레이션 충실도(fidelity) $f = |\langle \psi | \phi \rangle|^2$ 사이의 관계를 유도한다.

• 충실도 경계: 이들은 무작위 양자 회로에 대해 기대 충실도 $\bar{f}$가 대략 $\gamma^2$(유지된 확률 질량)이며, 간섭 항으로 인해 약간의 양의 편차가 발생함을 입증한다.
• 상한 및 하한:
  • 하한 $\bar{f}_{min} \approx 1/2^N$은 상태가 단 하나의 무작위 기저 상태로 절단되는 경우를 가정하여 유도된다.
  • 상한 $f_{max}$는 출력 분포가 포터-토머스(Porter-Thomas) 분포를 따른다고 가정할 때 유도된다. 이 상한은 회로 실행 도중이 아니라, 실행 후에 가장 확률이 높은 $k$개의 비트스트링을 식별하고 유지할 수 있다면 가질 수 있는 최선의 충실도를 나타낸다. 논문은 $d = k/2^N$ (절단 비율)일 때 $f_{max} \approx d(1 - \ln d)$임을 명시한다.

결과
저자들은 레이어 형태로 배치된 Haar-무작위 2-큐비트 유니터리를 포함하는 무작위 양자 회로에 대해 TruSTS를 벤치마킹하였다.

• 충실도 대 절단: $N=24$ 큐비트에 대한 시뮬레이션 결과, 근사 상태의 충실도는 재정규화 계수의 제곱인 $\gamma^2$에 따라 대략적으로 스케일링된다. Top-k 절단은 확률을 유지된 항들에 집중시킴으로써 Random-k 절단보다 일관되게 우수한 성능을 보였다.
• 런타임 스케일링:
  • $k$에 대하여: 게이트당 런타임은 유지되는 항의 수 $k$에 따라 선형적으로 스케일링된다.
  • $N$에 대하여: $k \ll 2^N$인 경우, 게이트당 런타임은 큐비트 수 $N$에 대해 대략 일정하다 (최대 $N=64$까지 테스트됨). 이는 상태가 희소하게 유지되는 한, 알고-리즘이 전체 힐베르트 공간 크이에 의존하는 오버헤드를 도입하지 않음을 나타낸다.
• 메모리: 이 방법은 전체 $2^N$ 메모리를 할당하는 것을 피하고 오직 $k$개의 항만을 저장한다.
• MPS와의 비교: quimb 라이库리를 사용한 $N=24$ 큐비트, 5개 레이어에 대한 MPS와의 예비 비교 결과, 테스트된 파라미터 범위 내에서 MPS가 대부분의 데이터 범위에서 더 유리한 런타임-충실도 트레이드오프를 제공하며, 유사한 런타임에 대해 더 높은 충실도를 유지함을 보여준다. 그러나 TruSTs는 런타임이 증가함에 따라 $f \sim 10^{-8}$ 근처의 하한에 도달하는 안정적이고 예측 가능한 충실도 감소를 보여준다.

의의 및 주장
본 논문은 특히 다음과 같은 시나리오에서 텐서 네트워크 기반 시뮬레이터의 능력을 확장하기 위한 도구로서 TruSTS를 위치시킨다:

1. 대칭성이 없는 경우: 이 방법은 기저에 깔린 대칭성에 의존하지 않는다.
2. SVD를 피하는 경우: SVD의 계산 비용 없이 절단을 달성한다.
3. 내재적 희소성이 존재하는 경우: 본래 희소한 양자 상태에 매력적이다.

저자들은 TruSTs가 충실도와 런타임 사이의 유용한 트레이드오프를 제공하며, 높은 충실도가 엄격하게 요구되지 않는 회로에서 즉각적인 응용 가능성이 있다고 주장한다. 이들은 이 연구가 희소 텐서 네트워크를 최적화하고, 복잡한 양자 시스템의 고전 시뮬레이션 경계를 더욱 확장하기 위해 TruSTS를 텐서 네트워크 컨트랙션 순서 최적화 전략과 결합하는 연구의 토대가 된다는 점을 강조한다. 저자들은 엄격한 대안 방법과의 비교 및 교차 엔트로피 충실도(cross-entropy fidelity)와 같은 측정 가능한 양에 대한 조사가 중요한 향후 연구 분야임을 언급하며 겸허한 태도를 유지한다.