QAP-Router: 강화학습을 이용한 동적 이차 할당 문제로의 큐비트 라우팅 해결

큐비트 라우팅은 양자 컴파일링에서 근본적인 문제이며, NP-hard로 알려져 있습니다. 그 역동적인 특성 때문에 국소적인 라우팅 결정이 시간에 따라 전파되고 복합되어 글로벌하게 효율적인 해법을 찾기 어렵게 만듭니다. 기존의 휴리스틱 방법들은 제한된 예측(lookahead)을 가진 국소 규칙에 의존하는 반면, 최근의 학습 기반 접근 방식들은 라우팅을 일반적인 순차적 결정 문제로 취급하며 그 근본적인 구조를 완전히 활용하지 못하는 경우가 많습니다. 본 논문에서는 큐비트 라우팅을 동적 이차 할당 문제(Quadratic Assignment Problem, QAP) 공식화에 기반하여 바라보는 QAP-Router를 소개합니다. 논리적 상호작용, 즉 양자 게이트를 흐름 행렬(flow matrices)로, 하드웨어 토폴로지를 거리 행렬(distance matrix)로 모델링함으로써, 우리의 접근 방식은 상호작용-거리 결합을 통합된 목적 함수에 포착하며, 이는 강화학습 환경에서 보상(reward)을 정의합니다. 이 구조를 더욱 활용하기 위해, 정책 네트워크는 솔루션 인식 트랜스포머 백본(solution-aware Transformer backbone)을 사용하여 흐름 행렬과 거리 행렬 간의 상호작용을 어텐션 메커니즘에 인코딩합니다. 또한, 근시안적인 결정(myopic decisions)을 방지하기 위해 QAP 프레임워크에 자연스럽게 통합되는 예측(lookahead) 메커니즘도 추가했습니다. MQTBench, AgentQ 및 QUEKO 데이터셋의 1,831개 실제 양자 회로에 대한 광범위한 실험 결과, 우리의 방법은 기존 산업용 컴파일러 대비 라우팅된 회로의 CNOT 게이트 수를 각각 15.7%, 30.4%, 12.1% 감소시키는 것을 보여주었습니다.