기술 요약: 무작위화를 통한 마르코프 연산 개방 양자계의 더 빠른 양자 시뮬레이션

문제 정의

양자 컴퓨터에서 마르코프 연산 개방 양자계(OQS)를 시뮬레이션하려면 Gorini-Kossakowski-Sudarshan-Lindblad (GKSL) 마스터 방정식에 의해 지배되는 동역학적 진화를 근사해야 한다. 핵심적인 제약 조건은 시뮬레이션이 진화의 물리적 타당성을 보존해야 한다는 것이며, 이는 근사된 맵이 완전 양의 값(Completely Positive) 및 트레이스 보존(Trace Preserving) 성질을 갖는 CPTP 맵이어야 함을 의미한다.

닫힌 계(closed systems)를 위한 Trotter-Suzuki (TS) 곱 공식은 표준적으로 사용되지만, OQS에 대한 적용에는 한계가 있다. 1차 및 2차 결정론적 TS 공식은 CPTP 근사를 보장하지만, 고차 결정론적 공식은 음의 시간 단계(negative time steps)를 포함하는 재귀적 구조로 인해 Lindbladian에 대해 CPTP 맵을 생성하지 못하고 CPTP 성질을 위반하는 경우가 많다. 반대로, 기존의 확률적 알고리즘들은 개선된 정밀도와 게이트 복잡도를 제공하지만, 실패할 확률이 0이 아닌 문제를 안고 있다. 따라서 CPTP 진화의 특성을 희생하거나 복잡한 서브루틴의 상당한 오버헤드에 의존하지 않으면서도, 게이트 복병도와 정밀도 측면에서 개선된 스케일링을 제공하는 비확률적(non-probabilistic) 알고리즘이 필요하다.

방법론

저자들은 마르코프 OQS를 시뮬레이션하기 위해 **무작위화(randomisation)**를 활용하는 새로운 비확률적 알고리즘을 소개한다. 핵심 방법론은 이산 분포로부터 게이트 세트를 구성하기 위해 **고전적 샘플링(Classical Sampling, CS)**을 사용하는 세 가지 뚜의 접근 방식을 포함한다:

1. 무작위 1차 TS 공식:

   • 결정론적 TS에서의 고정된 구성 채널 순서 대신, 이 방법은 순방향($S_1^\rightarrow$)과 역방향($S_1^\leftarrow$) 1차 곱 공식의 볼록 결합(convex combination)을 구성한다.
   • $S_1^{(ran)}(\tau) = \frac{1}{2}(S_1^\rightarrow(\tau) + S_1^\leftarrow(\tau))$.
   • 구현 시 클래식 오라클을 사용하여 각 시간 단계마다 순방향과 역방향 순서 중 하나를 무작위로 선택한다.

2. 무작위 2차 TS 공식:

   • 이 방법은 구성 생성자(generators)의 모든 치환 $\sigma \in \text{Sym}(M)$에 대한 볼록 결합을 취함으로써 2차로 무작위화를 일반화한다.
   • $S_2^{(ran)}(\tau) = \frac{1}{M!} \sum_{\sigma \in \text{Sym}(M)} S_\sigma^2(\tau)$.
   • 구현 시 각 시간 단계마다 순열을 균등하게 무작위 샘플링한다.

3. OQS를 위한 QDRIFT 채널:

   • Hamiltonian 시뮬레이션을 위한 QDRIFT 프로토콜에서 영감을 받아, 이 방법은 확률 $p_k = \gamma_k / \Gamma$ (여기서 $\Gamma = \sum \gamma_k$는 총 붕괴율)에 따라 구성 채널 $e^{\omega L_k}$를 확률적으로 적용한다.
   • 채널은 $\mathcal{E}_\omega^{(QD)}(\rho) = \sum_{k=1}^M p_k e^{\omega L_k}$로 정의된다.
   • TS 공식과 달리, 이 방법의 게이트 복잡도는 명시적 공식에 포함된 생성자 항의 개수 $M$에 독립적이며, 대신 총 붕괴율 $\Gamma$에 의존한다.

주요 기술적 차별점:
본 연구의 중요한 방법론적 기여는 믹싱 렘마(mixing lemma, Campbell and Hastings)에 의존하지 않고 무작위 OQS 시뮬레이션에 대한 오차 범위를 도출했다는 점이다. 믹싱 렘마는 유니터리 연산자(Hamiltonian 시뮬레이션)의 기하학에 특화된 것으로, CPTP 맵에는 적용되지 않는다. 저자들은 대신 직접적인 테일러 전개와 조합론적 논증을 사용하여 다이아몬드 노름(diamond norm) 오차를 제한함으로써, 무작위 공식이 비유니터리 동역학에도 불구하고 시간 단계 $\tau$에 대해 고차 정확도를 달름을 증명하였다.

주요 결과 및 게이트 복잡도

논문은 목표 정밀도 $\epsilon$과 시뮬레이션 시간 $t$에 대한 엄격한 오차 범위와 단계 수($N$)의 한계를 도출한다. 게이트 복잡도는 필요한 "단순 채널"(구성 지수 함수)의 총 개수로 정의된다.

$M$을 GKSL 생성자의 항의 개수, $\Lambda = \max_k \|\hat{L}_k\|_\diamond$를 (붕괴율을 포함한) $\hat{L}_k$의 최대값, $\Omega = \max_k \|L_k\|_\diamond$를 (율이 정규화된) 생성자의 최대값이라고 하자.

• 1차 결정론적 TS: $O((t\Lambda)^2 M^3 / \epsilon)$로 스케일링된다.
• 1차 무작위 TS (CS): $O((t\Lambda)^{3/2} M^{5/2} / \sqrt{\epsilon})$로 스케일링된다.
  • 개선 사항: 2차 결정론적 공식과 동일한 스케일링을 가지면서도 구조가 더 단순하다. $M$에 대한 의존도를 $M^3$에서 $M^{5/2}$로 개선하였다.
• 2차 결정론적 TS: $O((t\Lambda)^{3/2} M^{5/2} / \sqrt{\epsilon})$로 스케일링된다.
• 2차 무작위 TS (CS): $O((t\Lambda)^{3/2} M^2 / \sqrt{\epsilon})$로 스케일링된다.
  • 개선 사항: $M$에 대한 이차 의존성을 달성하여, 결정론적 및 1차 무작위 공식보다 성능이 크게 향상되었다.
• QDRIFT 채널 (CS): $O((t\Gamma\Omega)^2 / \epsilon)$로 스케일링된다.
  • 개선 사항: 게이트 복잡도에 $M$에 대한 명시적 의존성이 없으며, 대신 총 붕해율 $\Gamma$에 의존한다. 그러나 이 독립성은 조건부적이다: $\Gamma \le M \max_k \gamma_k$이므로, 붕괴율이 서로 비슷할 때 $\Gamma$는 $M$에 따라 선형적으로 증가하며, 이 경우 QDRIFT 채널은 결정론적 TS 공식과 유사하게 $M$에 대해 스케일링된다. 이 방법은 $\Gamma$가 작거나 $M$과 독립적으로 유계인 시스템(예: 몇 개의 강한 소산자에 의해 지배되는 시스템)에서 뚜렷한 이점을 제공한다.

의의 및 주장

저자들은 본 연구가 Hamiltonian 시뮬레이션의 강력한 무작위화 기법을 마르코프 연산 개방 양자계라는 일반적인 환경으로 체계적으로 확장했다고 주장한다. 본 연구의 의의는 다음 세 가지 측면에서 설명된다:

1. 비확률적 효율성: 제안된 방법들은 비확리적(error bounds는 결정론적이지만 회로 구성에는 무작위 샘플링이 포함됨)이며, 진화의 CPTP 성질을 유지하여 다른 확률적 OQS 알고리즘에서 나타나는 실패 확률 문제를 피한다.
2. 확장성: 무작위 TS 공식은 결정론적 TS 공식에 비해 생성자 항의 개수 $M$에 대한 스케일링이 개선되었다. 구체적으로, 2차 무작위 공식은 $M$에 대한 의존도를 이차(quadratic)로 낮추었으며, QDRIFT 채널은 $M$에 대한 명시적 의존성을 제거하였다(단, $\Gamma$의 거동에 따라 조건부임).
3. 구현의 단순성: 이 방법들은 고도의 결정론적 알고리즘(근사 선형 시간 $t$ 스케일링을 달성하기 위해 블록 인코딩이나 양자 신호 처리와 같은 복잡한 서브루틴이 필요한 방식)과 달리, 고전적 샘플링을 사용하여 게이트 세트를 구성하므로 구현이 간단하다. 저자들은 초기 결함 허용 양자 컴퓨터의 경우, 이러한 무작위 방식의 낮은 오버헤드와 구조적 단순성이 특히 $M$이 큰 시스템을 시뮬레이션할 때 실용적인 선택이 될 것이라고 주장한다.

논문은 무작위 방식가 시뮬레이션 시간 $t$에 대한 스케일링(이차 또는 그 이상) 측면에서는 일부 고급 결정론적 방법(근사 선형 시간)보다 불리할 수 있음을 명시적으로 언급하면서도, $M$에 대한 다항식적 개선과 낮은 구현 오버헤드가 대규모 소산 시스템을 짧거나 중간 정도의 시간 동안 시뮬레이션하는 등의 특정 시나리오에서 유리하다고 밝히고 있다.

본 연구는 믹싱 렘마를 CPTP 맵으로 일반화하는 것, 고차 스케일링을 위한 최적의 볼록 혼합을 찾는 것, 그리고 이러한 결과를 비마르코프(non-Markovian) 역학으로 확장하는 것 등의 미해결 과제를 제시하며 마무리된다. 또한, 역방향 시간 린블라디안($e^{-tL}$)의 비-CPTP 특성으로 인해 고차 무작위 공식으로 확장하는 데 따르는 어려움을 강조한다.