Bidirectional Path Integral Monte Carlo Simulation of Quantum Circuits

기술 요약: 양자 회로의 양방향 경로 적분 몬테카를로 시뮬레이션

문제 정의
양자 알고리즘을 검증하고, 근사 양자 장치를 벤치마킹하며, 양자 우위를 연구하기 위해서는 양자 회로의 고전적 시뮬레이션이 필수적이다. 그러나 임의의 회로를 시뮬레이션하는 것은 일반적으로 큐비트 수($n$)와 게이트 깊이($L$)에 따라 기하급수적으로 증가하는 계산 자원을 요구한다. 슈뢰딩거 기반 접근 방식(상태 벡터 시뮬레이션)은 정확한 결과를 제공하지만, $O(2^n)$의 메모리 복잡도로 인해 약 30~50개의 큐비트로 제한된다. 반면, 파인만 경로 적분 방법은 전체 상태 벡터를 저장하는 대신 계산 경로를 합산함으로써 $O(nL)$의 유리한 공간 복잡도를 제공한다. 하지만 이러한 방법들은 경로의 수($|P| = 2^{n(L-1)}$)가 조합론적으로 폭발하며, "차원의 저주" 문제를 겪는다.

표준 몬테카를로(MC) 추정치는 이를 극복하기 위해 일부 경로를 확률적으로 샘플링하려고 시도한다. 그러나 이들의 효율성은 두 가지 주요 요인에 의해 저해된다:

1. 경로 공간의 희소성(Path Space Sparsity): 많은 회로에서 대다수의 경로는 진폭이 0이다. 단방향(순방향 전용) 샘플링을 통해 소수의 비제로(non-zero) 경로를 찾는 것은 매우 비효율적이며, 이는 드물게 나타나는 고기여도 경로가 마침내 샘플링될 때 높은 분산을 초래한다.
2. 수치적 부호 문제(Numerical Sign Problem): 서로 상쇄되는 기여를 가진 경로들 사이의 파괴적 간섭는 평균 위상을 0에 가깝게 만들어, 안정적인 추정치를 얻기 위한 샘플링 요구량을 기하급수적으로 증가시킨다.

방법론
저자들은 양방향 경로 추적과 다중 중요도 샘플링(Multiple Importance Sampling, MIS)을 결합하여 전이 진폭 $\langle\Psi_f| \hat{U}|\Psi_0\rangle$을 추정하는 근사 고전 알고리즘인 **양방향 샘플링(Bidirectional Sampling, BS)**을 제안한다.

1. 양방향 경로 생성: 컴퓨터 그래픽스의 양방향 경로 추적(BDPT)에서 영감을 얻은 이 알고리즘은 두 개의 독립적인 무작위 보행(random walk)을 결합하여 경로를 생성한다:

   • 입력 상태 $|\Psi_0\rangle$로부터 레이어 $L-1$까지 진행하는 순방향(forward) 보행.
   • 출력 상태 $|\Psi_f\rangle$로부터 (수반 유니터리 $\hat{U}^\dagger$를 사용하여) 레이어 $1$까지 진행하는 역방향(backward) 보행.
   • 이 세그먼트들은 모든 가능한 레이어 $l \in \{0, \dots, L-1\}$에서 결정론적으로 연결되어, 하나의 샘플링된 세그먼트 쌍으로부터 $L$개의 서로 다른 전체 경로를 생성한다.

2. 다중 중요도 샘플링(MIS): 낮은 확률의 샘플링 이벤트로 인한 분산을 해결하기 위해, 알고리즘은 균형 휴리스틱(balance heuristic)을 채택한다. 생성된 모든 경로는 이론적으로 $L$개의 레이어 중 어느 지점에서든 순방향 및 역방향 세그먼트를 연결하여 구성될 수 있으므로, 추정치는 주어진 경로에 대해 $L$가지 가능한 생성 전략의 확률을 합산한다.

   • 최종 추정식은 다음과 같이 정의된다:
     $$\tilde{I}_{BS} = \frac{1}{N \cdot L} \sum_{i=0}^{N-1} \sum_{l=0}^{L-1} \frac{f(\bar{z}_{i,l})}{\sum_{d=0}^{L-1} p_d(\bar{z}_{i,l})}$$
   • 이 방식은 특정 연결을 찾기가 매우 어려운 경우 발생하는 극도로 작은 샘플링 확률로 나누는 것을 방지함으로써, 분산을 완화하고 추정치의 "피크(peaks)" 현상을 방지한다.

3. 공간 복잡도: 알고리즘은 회로 기술과 현재 경로 상태만을 유지하여, 큐비트 수와 무관하게 파인만 경로 방식의 특징인 $O(nL)$ 공간 복합도를 보존한다.

주요 기여 및 결과
논문은 Deucalion 슈퍼컴퓨터를 이용한 경험적 실험을 통해 세 가지 특정 가설을 검증한다:

• H1: 우수한 수렴 속도.
  BS 알고리즘은 단방향 순방향 샘플링(FS)에 비해 유의미하게 빠른 수렴 속도를 보여준다.

  • 분산 감소: 대규모 회로(예: 25 큐비트, 95 레이어)에서 BS는 동일한 샘플 수에 대해 FS보다 분산을 5 자릿수(orders of magnitude)만큼 감소시켰다.
  • 경로 발견: BS는 희소한 공간에서 비제로 진폭 경로를 발견하는 데 훨씬 효과적이다. 25 큐비트 IQP 회로의 경우, BS는 동일한 계산 노력 대비 FS보다 약 6 자릿수 더 많은 비제로 경로를 찾아냈다.
  • 시간 효율성: 샘플당 $L$개의 경로를 생성하는 계산 비용을 고려하더라도, BS는 실행 시간당 분산 측면에서 FS보다 우수하다.

• H2: 대규모 회로로의 확장성.
  $O(nL)$ 메모리 풋프린트를 활용하여, 저자들은 최대 4096 큐비트의 회로를 성공적으로 시뮬레이션했다.

  • 결정론적 출력이 알려진 Hidden Shift 회로(HSC)를 사용하여 256, 1024, 4096 큐비트 회로의 전이 진폭을 추정했다.
  • 이와 대조적으로, 상태 벡터 시뮬레이터는 $O(2^{4096})$의 메모리가 필요하며 이는 물리적으로 불가능하다. BS 방식은 4096 큐비트 케이스에서 약 2.5 MiB의 RAM만을 사용하였으며, 이는 큐비트 수에 따른 선형적 확장을 입증한다.

• H3: 희소성 대 수치적 부호 문제.
  저자들은 성능 향상이 수치적 부호 문제(파괴적 간섭)를 더 잘 처리했기 때문인지, 아니면 단순히 희소한 경로 공간을 더 잘 샘플링했기 때문인지를 조사했다.

  • 500개의 무작위 회로를 분석한 결과, BS의 FS 대비 분산 감소는 경로 공간의 희소성과 강한 상관관계를 보였으나, 부호 문제의 척도인 역 제곱 평균 위상($\chi$)과는 상관관계가 거의 없었다.
  • 결론: 개선의 원인은 수치적 부호 문제의 완화가 아니라, 희소한 영역에서 비제로 경로를 효율적으로 찾아내고 가중치를 부여하는 양방향 접근 방식의 능력에 있다. 수치적 부호 문제는 여전히 PIMC 방법의 중요한 과제로 남아 있다.

의의 및 주장
본 논문은 제안된 양방향 샘플링 추정기가 메모리 제약으로 인해 전통적인 상태 벡터 방식이 실패하는 대규모 양자 회로를 시뮬레이션하기 위한 견고하고 편향되지 않은 방법을 제공한다고 주장한다. 주요 의의는 다음과 같다:

1. 실현 가능성: 최소한의 메모리 오버헤드로 클래식 하드웨어에서 수천 개의 큐비트(4096까지 입증됨)를 시뮬레이션할 수 있게 한다.
2. 효율성: 순방향 전용 샘플링에 비해 상당한 분산 감소를 제공하여, 경로 공간이 매우 희소한 회로의 진폭을 추정하는 데 실용적이다.
3. 방법론적 전이: 물리 기반 전역 조명(BDPT 및 MIS)의 기술을 양자 회로 시뮬레이션 영역에 성공적으로 적용하였다.

저자들은 수치적 부호 문제에 대해 겸허한 태도를 유지하며, BS가 샘플링 효율을 높이기는 하지만, 강한 파괴적 간섭(높은 $\chi$)에 의해 부과되는 기하급수적인 샘플링 요구량은 여전히 경로 적분 몬테카를로 방법의 근본적인 한계임을 인정한다. 향후 연구에서는 노이즈가 있는 시스템을 다루고, 부호 문제를 완화할 수 있는 대안적인 경로 표현을 탐구하는 것이 필요하다고 명시하였다.