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

요약

본 논문에서 제안하는 QAP-Router는 양자 컴파일링의 핵심 문제인 큐비트 라우팅을 동적 이차 할당 문제(QAP)로 공식화하여 해결합니다. 이 접근 방식은 양자 게이트를 흐름 행렬, 하드웨어 토폴로지를 거리 행렬로 모델링하고, 이를 통합된 목적 함수에 포함시켜 강화학습 환경의 보상으로 정의합니다. 솔루션 인식 트랜스포머 백본과 예측 메커니즘을 활용하여 근시안적 결정을 방지함으로써, 기존 컴파일러 대비 CNOT 게이트 수를 크게 줄이는 효과를 입증했습니다.

핵심 포인트

• 큐비트 라우팅 문제를 NP-hard인 동적 이차 할당 문제(QAP)로 공식화함.
• 양자 상호작용을 흐름 행렬, 하드웨어 토폴로지를 거리 행렬로 모델링하여 통합 목적 함수를 구축함.
• 솔루션 인식 트랜스포머 백본과 어텐션 메커니즘을 사용하여 복잡한 상호작용을 인코딩함.
• 예측(lookahead) 메커니즘을 추가하여 근시안적 결정의 한계를 극복함.
• 실제 양자 회로 데이터셋에서 기존 컴파일러 대비 CNOT 게이트 수를 평균적으로 크게 감소시키는 성능을 보임.