dSABRE: A SABRE-Style Router for Multi-Core Distributed Quantum Computers

본 논문은 기존 최첨단 방법 대비 자원 사용량을 크게 줄인 다중 코어 분산 양자 컴퓨터를 위한 새로운 라우터인 dSABRE를 소개하며, 이는 코어 내부 게이트 해결을 우선시하고 용량을 고려한 텔레포테이션 스코어링 메커니즘을 활용하여 EPR 소비를 최소화합니다.

핵심

거대한 고위험 무도회를 조직하려 한다고 상상해 보세요. 하지만 공연장은 여러 개의 분리된 방 (코어라고 부름) 으로 나뉘어 있습니다. 춤추는 사람들은 큐비트 (양자 비트) 이고, 음악은 양자 회로 (일련의 지시사항) 입니다.

춤이 원활하게 진행되려면, 때로는 춤추는 사람 쌍이 손을 잡고 함께 회전해야 합니다. 그들이 같은 방에 있다면 서로 쉽게 다가갈 수 있습니다. 하지만 서로 다른 방에 있다면 벽을 통과할 수 없습니다. 대신 한 방에서 다른 방으로 이동하기 위해 특수하고 비싸며 느린 '텔레포트' 서비스를 이용해야 합니다. 이 서비스는 EPR 쌍이라는 제한된 자원을 소모합니다 (이를 귀중한 '마법 티켓'이라고 생각하세요).

문제는 다음과 같습니다: 최소한의 마법 티켓을 사용하면서 춤추는 사람들이 함께 춤출 수 있도록 어떻게 이동시켜야 할까요?

이것이 DSABRE가 해결하는 문제입니다. 여기서는 해당 논문이 이를 간단한 용어로 설명하는 방식을 보여줍니다:

1. 이전 방법들의 문제점

DSABRE 이전에는 TELESABRE와 같은 다른 라우터들이 문제가 발생하기만 하면 대응하는 교통 경찰과 같았습니다.

• 방이 춤추는 사람들로 너무 붐비면, 이전 라우터들은 교통 체증이 발생한 후까지 기다렸습니다.
• 일단 체증이 발생하면 춤추는 사람을 강제로 내보내려 했지만, 이는 종종 추가 마법 티켓을 소모하거나 전체 파티를 정지시키는 ('데드락') 결과를 낳았습니다.
• 또한 그들은 춤 지시사항을 엉망이고 무작위적인 순서로 살펴보았기 때문에, 누가 다음에 이동해야 할지 예측하기 어려웠습니다.

2. DSABRE 의 해결책: 더 똑똑하고 선제적인 관리자

DSABRE 는 더 지능적인 전략을 사용하는 새로운 '라우터' (교통 관리자) 입니다. 마법 티켓을 절약하기 위해 세 가지 주요 수단을 사용합니다:

A. "5 점 평가표" (더 나은 의사결정)

DSABRE 가 춤추는 사람을 새로운 방으로 이동시킬지 결정할 때, 단순히 파트너가 "얼마나 가까운지"만 보지 않습니다. 대신 5 가지 항목 평가표를 사용합니다:

1. 스테이징 비용: 춤추는 사람이 현재 방 안에서 문까지 가기 위해 몇 걸음을 옮겨야 하는가?
2. 용량 페널티: 이것이 가장 중요합니다. 목적지 방이 이미 춤추는 사람들로 꽉 차 있다면, DSABRE 는 이를 큰 '나쁜 점수'로 매깁니다. 춤추는 사람을 그곳으로 보내는 것을 거부하여 방이 교통 체증으로 변하는 것을 방지합니다.
3. 홉 (Hop) 이득: 아직 도착하지 않았더라도, 춤추는 사람을 최종 목적지 방에 더 가깝게 만드는 이동을 보상합니다.
4. 즉각적 이득: 이 이동이 춤추는 사람을 지금 당장 파트너에게 얼마나 더 가깝게 만드는가?
5. 선제적 예측: 몇 단계 앞을 내다보아 이 이동이 다가오는 춤에 도움이 될지 확인합니다.

비유: 가구를 옮긴다고 상상해 보세요. 이전 라우터들은 그 방이 이미 박스로 가득 차 있더라도 "가까우니까"라고만 생각하며 소파를 다음 방으로 밀어 넣었습니다. DSABRE 는 먼저 방이 꽉 찼는지 확인하고 "아니요, 그 방은 너무 붐비니 소파를 복도에 두는 게 좋겠습니다"라고 말합니다.

B. "선제적 대피" (체증 발생 전 정리)

이것이 DSABRE 의 비밀 무기입니다.

• 구 방식: 방이 100% 꽉 차기까지 기다렸다가, 당황하며 사람들을 밖으로 내보내려 했습니다.
• DSABRE 방식: '수요 목록'을 유지합니다. 다가오는 춤을 위해 A 방이 춤추는 사람들로 붐비게 될 것으로 예상되는데, A 방이 이미 거의 꽉 차 있다면, DSABRE 는 혼잡이 시작되기 전에 현재 춤추고 있지 않은 유휴 춤추는 사람들을 A 방에서 선제적으로 이동시킵니다.
• 결과: 혼잡이 도착했을 때 공간이 확보됩니다. 교통 체증도, 낭비되는 마법 티켓도 없습니다.

C. "레이어별" 지도 (더 나은 계획)

DSABRE 다가오는 춤들을 미리 살펴볼 때, 목록을 무작위로 스캔하지 않습니다. 춤의 순서를 존중하며 레이어별로 지도를 작성합니다.

• 비유: 요리 레시피를 읽는다고 상상해 보세요. 이전 라우터는 수프보다 디저트 재료를 먼저 읽을 수 있습니다. DSABRE 는 올바른 순서대로 레시피를 읽으므로, 다음에 필요한 재료 (춤추는 사람) 가 무엇인지 정확히 알고, 아직 필요하지 않은 물건을 옮기는 시간을 낭비하지 않습니다.

3. 결과: 훨씬 더 효율적인 파티

저자들은 다양한 크기 (25 명, 36 명, 64 명의 춤추는 사람) 의 여러 다른 '파티' (양자 회로) 에서 DSABRE 를 테스트했습니다.

• 결과: DSABRE 는 이전 최선 방법 (TELESABRE) 보다 41% 에서 44% 적은 마법 티켓 (EPR 쌍) 을 사용했습니다.
• 확장성: 최대 360 명의 춤추는 사람이 있는 거대한 파티에서 테스트했을 때, DSABRE 는 여전히 완벽하게 작동한 반면, 이전 방법은 종종 멈춰서 포기했습니다.

요약

간단히 말해, DSABRE는 서로 연결된 여러 작은 칩으로 구성된 양자 컴퓨터를 조직하는 더 지능적인 방법입니다. 교통 체증이 발생하기를 기다리는 대신, 다음과 같이 작동합니다:

1. 춤추는 사람을 붐비는 방으로 보내기 전에 용량을 확인합니다.
2. 공간을 확보하기 위해 유휴 춤추는 사람들을 미리 이동시킵니다.
3. 논리적이고 단계적인 순서로 이동을 계획합니다.

이는 칩을 연결하는 데 필요한 비싼 '마법 티켓' (EPR 쌍) 을 절약하여 양자 컴퓨터가 더 효율적으로 작동하도록 합니다.

기술 요약

기술 요약: DSABRE – 멀티코어 분산 양자 컴퓨터를 위한 SABRE 스타일 라우터

문제 제기
결함 허용 양자 컴퓨팅으로 가는 길은 단일 모놀리식 칩을 넘어 분산 양자 컴퓨터 (DQCs) 로 확장하는 것을 요구하며, 여기서 여러 개의 작은 양자 처리 유닛 (QPU 또는 "코어") 이 광학 또는 마이크로파 링크를 통해 상호 연결됩니다. DQC 에서 회로를 실행하는 것은 양자 비트 할당, 통신 원시 연산 선택, 그리고 라우팅/스케줄링으로 구성된 컴파일 파이프라인을 포함합니다. 이 맥락에서 지배적인 목표는 **EPR 소모 (얽힌 쌍)**를 최소화하는 것이며, 이는 EPR 생성이 로컬 게이트 연산에 비해 느리고 잡음이 많으며 속도 제한을 받기 때문입니다.

TELESABRE와 같은 최첨단 라우터들은 SABRE 스타일 휴리스틱을 사용하여 코어 간 회로를 라우팅하지만, 혼잡을 방어적으로 처리합니다. TELESABRE 는 페널티를 통해 포화 상태의 코어에 도달하는 것을 억제하고, 미리보기 정보를 삭제함으로써 데드락에서 복구하려고 시도합니다. 그러나 밀집되거나 대규모 인스턴스에서는 이러한 반응형 접근 방식이 과도한 EPR 쌍을 소모하거나 아예 수렴하지 못하는 경우가 많습니다. 이 논문이 다루는 핵심 과제는 능동적 혼잡 관리의 부재와 코어 간 환경에서 기존 미리보기 메커니즘의 비효율성입니다.

방법론: DSABRE
DSABRE 는 멀티코어 프로세서를 위해 설계된 SABRE 스타일 라우터입니다. 이는 고정된 초기 레이아웃 (Qiskit SabreLayout 에 의해 생성됨) 내에서 작동하며 라우팅 단계, 즉 코어 내 SWAP 순서 지정과 코어 간 텔레포테이션 (특히 teledata, 즉 논리 양자 비트를 코어 간에 이동) 에 초점을 맞춥니다. 이 알고리즘은 각 반복마다 네 가지 단계를 가진 미리보기 주도 루프를 실행합니다:

1. Drain (배출): 1Q 게이트와 인접한 코어 내 2Q 게이트를 실행합니다.
2. Partition (분할): 남은 프론트 레이어 게이트를 코어 내 ($F_{intra}$) 와 코어 간 ($F_{inter}$) 으로 분리합니다.
3. Score & Apply (점수 매기기 및 적용):
   • $F_{intra}$가 비어 있지 않다면, 가장 좋은 코어 내 SWAP 을 선택합니다.
   • $F_{intra}$가 비어 있다면, 코어 간 텔레포테이션 후보와 능동적 혼잡 완화 후보를 점수 매기고, 가장 낮은 점수를 받은 동작을 적용합니다.
4. Checkpoint/Rollback (체크포인트/롤백): 진전이 있을 때 상태를 저장합니다. 설정된 반복 횟수 동안 정지 상태라면 체크포인트를 복원하고 강제로 진전을 이루어 데드락을 탈출합니다.

주요 기여 및 메커니즘
이 논문은 DSABRE 가 최첨단 기술보다 개선되는 것을 이끄는 세 가지 구체적인 메커니즘을 식별합니다:

1. 5 항 게이트 중심 텔레포테이션 점수:
   TELESABRE 의 전역 에너지 추정과 달리, DSABRE 는 코어 간 이동에 대해 로컬이고 게이트 중심인 점수 ($s$) 를 사용합니다. 이 점수는 다음 다섯 가지 항을 결합합니다:

   • 스테이징 비용 ($d_{prep}$): 양자 비트를 통신 포트로 이동시키는 데 필요한 코어 내 SWAP.
   • 용량 페널티 ($c_{cap}$): 여유 용량이 낮은 코어로 텔레포테이션하는 것을 명시적으로 페널티화하여 라우터가 포화 상태의 코어를 범람하는 것을 방지하는 항.
   • 홉 이득 ($g_{hop}$): 목표까지의 코어 간 거리를 줄이는 이동에 대한 방향성 보상. 최적의 스테이징 위치에서 멀리 떨어진 착륙 포트로 이동할 때 이를 보상합니다.
   • 프론트 레이어 이득 ($\Delta_F$): 현재 게이트에 대한 물리적 거리의 즉각적인 감소.
   • 미리보기 ($\tilde{\Delta}_E$): 미래 거리 감소의 감쇠 가중 합.

2. 능동적 혼잡 완화:
   DSABRE 는 코어에 대한 명시적 수요 벡터를 유지합니다. 코어가 포화 상태 (높은 수요, 낮은 용량) 에 도달하기 전에, 라우터는 수요가 높은 코어에서 유휴 양자 비트를 멀리 텔레포테이션하는 "완화 후보"를 능동적으로 생성합니다. 이러한 이동은 동일한 목적 함수 내에서 ($\Delta_F=0$으로) 점수 매겨지며 게이트 주도 이동과 직접 경쟁합니다. 이는 반응형 시스템에서 데드락으로 이어지는 "퇴거 연쇄"를 방지합니다.

3. BFS 레이어 코어 간 확장 집합:
   표준 SABRE 는 위상 순서로 미리보기 집합을 구축하여 관련 없는 와이어를 혼합할 수 있습니다. TELESABRE 는 BFS 레이어를 사용하지만 게이트를 임의로 가중치 처리합니다. DSABRE 는 DAG 에서 너비 우선 탐색 (BFS) 을 사용하여 레이어별로 코어 간 미리보기 집합을 구축합니다. 결정적으로, 각 레이어 내에서 프론트와 와이어를 공유하는 게이트가 먼저 방출됩니다. 미리보기 감쇠는 BFS 깊이 ($\gamma^{dep(g)}$) 를 기반으로 적용되어 단기 후계자가 신호를 지배하도록 하고, 위상 순서보다 DAG 종속성을 더 엄격히 준수하도록 합니다.

실험 결과
저자들은 25, 36, 64 논리 양자 비트의 18 개 MQT-Bench 회로를 그리드 - 오브 - 그리드 아키텍처 (B-grid 및 H-grid) 를 사용하여 TELESABRE 및 pytket-dqc(게이트 텔레포테이션 기반 라우터) 에 대해 DSABRE 를 평가했습니다.

• EPR 감소: DSABRE 는 TELESABRE 대비 기하평균 EPR 소모를 41–44% 감소시키고, pytket-dqc 대비 16–68% 감소시켰습니다.
• 확장성: 64 양자 비트 무작위 회로에서 TELESABRE 는 모든 시드에서 수렴에 실패한 반면, DSABRE 는 라우팅을 완료했습니다. 최대 360 양자 비트의 양자 푸리에 변환 (QFT) 회로에 대한 확장성 스윕은 회로 크기와 아키텍처가 확장됨에 따라 DSABRE 가 그 우위를 유지함을 확인했습니다.
• 절제 연구:
  • 용량 페널티를 제거하면 기하평균 EPR 이 25q 에서 약 59%, 64q 에서 약 59% 증가하여 이것이 가장 중요한 구성 요소임을 확인했습니다.
  • 능동적 혼잡 완화를 비활성화하면 64q 스위트에서 EPR 이 23.4% 증가했으며, 밀집 회로 (AE, QFT) 의 경우 100% 이상 증가했습니다.
  • BFS 레이어 확장 집합을 위상 순서로 대체하면 EPR 이 3–11% 증가했으며, 더 큰 회로일수록 이득이 커졌습니다.
• 비용 민감도: 텔레포테이션의 상대적 비용 ($c_{tele}$) 이 증가함에 따라 (광학 링크 하드웨어 시뮬레이션), DSABRE 와 TELESABRE 간의 성능 격차가 벌어지며, DSABRE 는 높은 비용 비율에서 최대 약 39% 더 많은 EPR 을 절약합니다.

의의 및 주장
이 논문은 분산 라우팅이 복잡한 후보별 점수 공식보다는 미리보기 신호와 아키텍처 용량 제약이 동일한 점수 단계에 포함되도록 보장하는 것에서 더 많은 이점을 얻는다고 주장합니다. 능동적 혼잡 완화와 용량 인식 점수를 통합함으로써 DSABRE 는 방어적이고 반응적인 라우터들이 겪는 데드락과 과도한 EPR 소모를 피합니다.

저자들은 DSABRE 를 정적 할당 방법 (하이퍼그래프 파티셔닝 등) 과 시간 인식 스케줄러와 보완적인 것으로 위치시킵니다. 현재 DSABRE 는 teledata(상태 텔레포테이션) 만 사용하지만, 향후 다른 원시 연산이나 버스트 실행 패스와 결합될 수 있는 견고한 라우팅 엔진으로 설계되었다고 언급합니다. 결과는 명시적 용량 관리가 분산 양자 컴파일 확장에 필수적인 구성 요소임을 시사합니다.