DPRQ: A Dynamic Programming-based Qubit Routing Algorithm for Collective Communication in Distributed Quantum Computing

기술 요약: DPRQ: 분산 양자 컴퓨팅의 집합적 통신을 위한 동적 계획법 기반 큐비트 라우팅 알고리즘

문제 정의
분산 양자 컴퓨팅(DQC)은 단일 장치의 큐비트 용량 한계를 극복하기 위해 여러 양자 프로세서를 네트워크로 연결함으로써 양자 프로세싱을 확장하는 것을 목표로 한다. 그러나 노드 간 통신은 여전히 중요한 병목 현상으로 남아 있다. 일반적인 DQC 모델에서, 노드 간 게이트를 실행하는 것은 TP-Comm(양자 텔레포테이션) 프로토콜을 통해 하나의 아인슈타인-포돌스키-로젠(EPR) 쌍을 소비한다. EPR 쌍을 생성하고 유지하는 과정은 오류가 발생하기 쉬운 특성을 가지고 있기 때문에, 이는 매우 희소하고 값비싼 자원이다.

QuComm [20]과 같은 기존 방식은 이 과정을 최적화하기 위해 "집합적 통신(collective communication)"을 활용하여, 회로를 인터 노드 게이트들의 블록으로 나누고 이를 공통 어그리게이터(aggregator) 노드로 라우팅하지만, 심각한 한계점을 지닌다: 바로 탐욕적(greedy)인 블록 단위 라우팅 전략이다. QuComm은 각 블록 내에서의 라우팅은 최적화하지만, 이전 블록들로부터 발생하는 의존성과 상태 변화(큐비트 레이아웃)는 무시한다. 이러한 근시안적인 관점은 전역적 최적화를 방해하여, 전체 회로에 걸친 EPR 소비를 차원 미달(suboptimal)하게 만든다.

방법론
본 논문은 집합적 통신 블록으로 나뉜 DQC 회로에서 노드 간 통신 비용을 최소화하도록 설계된 큐비트 라우팅 알고리즘인 DPRQ를 제안한다. DPRQ는 (회로를 인터 노드 게이트 연결성에 따라 블록으로 분할하는) QuComm의 통신 융합 단계는 그대로 유지하되, 탐욕적 라우팅 단계를 동적 계획법(Dynamic Programming, DP) 접근 방식으로 대체한다.

이 방법론은 두 가지 주요 구성 요소로 이루어진다:

1. 블록 내 통신 비용 계산:
   주어진 블록과 선택된 어그리게이터 노드에 대해, DPRQ는 관련된 모든 큐비트를 해당 노드로 텔레포테이션하는 비용을 계산한다. 단순한 최단 경로 라우팅과 달리, DPRQ는 "조기 실행(early execution)" 기법을 채택한다. 현재 큐비트 위치와 어그리게이터 사이의 모든 최단 경로를 평가하여, 게이트를 조기에 실행할 수 있는 중간 노드들을 식별한다. 알고리즘은 노드의 제한된 EPR 용량을 고려하여, 이러한 중간 노드로 큐비트를 전송하는 데 드는 EPR 비용을 계산한다. 만약 특정 노드에 충분한 통신 큐비트가 없다면, 비용은 증가한다(SWAP 연산 필요). 알고리즘은 해당 블록에 대한 총 EPR 비용을 최소화하는 노드와 경로를 선택하고, 그에 따라 큐비트 레이아웃을 업데이트한다.

2. DP 기반 블록 간 큐비트 라우팅:
   DPRQ는 일련의 집합적 통신 블록을 동적 계획법 문제로 취급한다. 이는 블록 $b_k$를 실행하기 위해 $n_k$를 블록 $b_k$의 어그리게이터 노드로 사용하는 최소 총 통신 비용을 나타내는 비용 행렬 $C(b_k, n_k)$를 유지한다.

   • 상태 전이: 블록 $b_k$와 어그리게이터 $n_k$에 대한 비용을 계산하기 위해, 알고리즘은 이전 블록 $b_{k-1}$의 가능한 모든 어그리게이터 노드 $n_{k-1}$을 살펴본다. 이후 이전 블록의 최종 큐비트 레이아웃을 기준으로 주어진 전환 비용 $T(b_k, n_{k-1}, n_k)$를 계산한다.
   • 전역 최적화: 이전 블록($b_{k-1}$)으로부터 유도된 최적의 최종 레이아웃을 현재 블록($b_k$)의 초기 레이아웃으로 고려함으로써, DPRQ는 전역 엔드 투 엔드(end-to-end) EPR 비용을 최소화하는 어그리게이터 노드의 시퀀스를 식출한다. 이 접근 방식은 이전의 최적 결정으로부터 파생된 초기 레이아웃 공간을 탐색하지만, 공간 및 시간 복잡성을 관리하기 위해 여러 레이아웃을 유지하는 대신 각 튜플 $(b_{k-1}, n_{k-1})$에 대해 단 하나의 최적 최종 레이아웃만을 명시적으로 저장하고 활용한다.

주요 기여

• 지능형 라우팅 프레임워크: 저자들은 집합적 통신 블록으로 분할된 DQC 회로에서 EPR 비용을 줄이기 위해 특별히 설계된 큐비트 라우팅 프레임워크를 제시한다.
• 동적 계획법 접근 방식: 본 논문은 탐욕적 전략과 대조되는, 블록 간 의존성을 포착하는 DP 기반 기술을 도입한다. 이를 통해 알고리즘이 현재의 라우팅 결정이 미래의 블록에 미칠 영향을 고려할 수 있게 한다.
• 포괄적 평가: 제안된 알고리즘은 네 가지 양자 회로(Bernstein-Vazirani, Ripple-Carry Adder, VQE, QAOA)와 다양한 DQC 구성(EPR 용량, 회로 너비, 네트워크 토폴로지가 변하는 경우)에 대해 최첨단 베이스라인인 QuComm과 비교 평가되었다.

결과
평가 결과, DPRQ는 노드 간 통신(EPR 쌍 호출 횟수로 측정됨)을 줄이는 데 있어 QuComm보다 일관되게 우수한 성능을 보였다:

• 전반적인 성능: DPRQ는 QuComm 대비 인터 노드 통신에서 평균 24.40%의 감소를 달al성하였으며, 최대 85.06%의 감소를 기록했다.
• 확장성: DPRQ의 이점은 DQC 네트워크의 노드 수가 증가함에 따라 더욱 두드러진다. EPR 용량이 제한적인 시나리오(예: 용량 = 2)와 높은 노드 수를 가진 경우, DPRQ는 벤치마크 회로 전반에 걸쳐 최대 평균 48.54%의 감소율을 제공한다.
• 강건성: DPRQ는 다양한 네트워크 토폴로지(mesh-grid, ring, fully-connected)에 대해 탄력성을 보여준다. 직접 연결이 복잡한 어그리게이터 선택의 필요성을 줄여주는 완전 연결(fully-connected) 토폴로지에서는 이점이 줄어들지만, DPRQ가 베이스라인보다 성능이 떨어지는 경우는 없었다.
• 회로 민감도: DPRQ는 EPR 용량 변화와 관계없이 특정 회로(BV 등)에 대해 거의 일정한 라우팅 비용을 유지하는 반면, QuComm은 전역 최적화의 부재로 인해 비용이 더 크게 변동한다.

의의 및 주장
본 논문은 DPRQ가 최적화 패러다임을 로컬(블록 단위)에서 글로벌(회로 단위)로 전환함으로써 기존의 탐욕적 라우팅 방식보다 상당한 개선을 제공한다고 주장한다. 저자들은 이러한 접근 방식이 통신 자원이 제한된 현재 및 미래의 DQC 네트워크에서 특히 필수적이라고 단언한다. 블록 내 실행과 블록 간 상태 전이 사이의 트레이드오프를 효과적으로 관리함으로써, DPRQ는 대규모 양자 회로를 분산 하드웨어에서 더 효율적으로 실행할 수 있게 한다. 이 연구는 DQC 네트워크가 더 많은 프로세서를 포함하도록 확장됨에 따라, 블록 경계를 가로질러 최적화하는 능력이 실질적인 양자 컴퓨팅을 위해 점점 더 중요해질 것임을 시사한다.