ATHENA: A Compiler For Optimized Scheduling In Distributed Quantum Computers

이 논문은 최첨단 방법들에 비해 텔레포테이션 오버헤드와 지연 시간을 현저히 줄이기 위해 다중 후보 블록 스케줄링과 EPR 용량 인식 조기 스케줄링을 활용한 유틸리티 기반 룩어워드를 통해 분산 양자 컴퓨터의 스케줄링 효율성을 향상시키는 컴파일러인 ATHENA 를 소개합니다.

핵심

거대한 저택의 여러 방에 흩어진 무용수들을 초대형 고난도 댄스 파티로 조직하려 한다고 상상해 보세요. 이것이 바로 **분산 양자 컴퓨터 (DQC)**의 모습입니다. 거대한 칩 하나 대신 여러 개의 작은 칩들을 서로 연결하는 방식입니다.

무용수들 (큐비트) 이 협력하려면 때로는 한 방에서 다른 방으로 이동해야 합니다. 양자 세계에서는 이 '이동'을 텔레포테이션이라고 부릅니다.

문제는 무용수를 방 사이에서 이동시키는 일이 느리고, 어색하며, 실수가 발생하기 쉽다는 점입니다. 이는 창문을 통해 깨지기 쉬운 유리 꽃병을 전달하려는 시도와 바로 옆에 서 있는 사람에게 건네는 것의 차이와 같습니다. 이 논문에서는 이러한 '비국소적 (non-local)' 이동을 지칭하며, 이는 같은 방 내에서 이루어지는 이동에 비해 4 배에서 7 배 더 느리고, 4 배 더 자주 고장이 난다고 설명합니다.

이 논문의 목표는 **아테나 (Athena)**라는 새로운 '파티 플래너' (컴파일러) 를 소개하는 것입니다. 아테나의 임무는 이러한 이동들을 최상의 순서로 스케줄링하여 파티를 더 빠르게 마치게 하고 깨진 꽃병의 수를 줄이는 것입니다.

기존 플래너들의 문제점

아테나 이전까지 최고의 플래너들 (예: QuComm) 은 다음과 같이 작동했습니다:

1. 한 번에 한 무용수 그룹만 살펴보았습니다. 그들은 몇 가지 이동을 그룹화하고, 그 그룹에 대해서만 무용수들을 이동시키는 최선의 방법을 찾은 뒤, 그 계획을 영구적으로 고정했습니다.
2. 예지력이 없었습니다. 그룹 A 에 대한 계획을 확정해 버리면, 나중에 그룹 B 의 작업을 훨씬 더 어렵게 만들 것임을 깨닫더라도 그 계획을 변경할 수 없었습니다.
3. 지나치게 기다렸습니다. 무용수가 이동할 준비가 되었고 복도가 비어있더라도, 플래너는 해당 그룹이 공식적으로 시작할 '시간'이 될 때까지 기다렸다가 이동을 시켰습니다. 이로 인해 길고 불필요한 대기 행렬이 생겼습니다.

저자들은 단순히 몇 단계 앞만 내다보는 방식이 작동하지 않는다는 사실을 발견했습니다. '무대'가 너무 커서 한 이동의 결과가 수십 개의 그룹이 지난 후에야 나타나기 때문입니다.

아테나의 해결책

아테나는 이러한 문제들을 해결하기 위해 두 가지 영리한 트릭을 도입합니다.

1. '스마트 미리보기' (유틸리티 기반 미리보기)

여행을 계획한다고 상상해 보세요. 나쁜 플래너는 다음 5 마일만 보고 그 이후 50 마일 뒤에 죽은 길이 있다는 것을 무시한 채 가장 빠른 경로를 선택합니다.
아테나는 더 영리합니다. 단순히 다음 몇 개의 무용수 그룹만 보지 않습니다. 대신 다음과 같이 묻습니다: "어떤 미래의 그룹들이 현재 그룹과 무용수를 공유하고 있는가?"

• 비유: 그룹 A 가 '밥'이라는 무용수를 이동시키고, 그룹 10 도 '밥'이 필요하다면, 아테나는 지금 당장 그룹 10 을 고려합니다. 그룹 5 가 밥을 필요로 하지 않는다면, 아테나는 이를 무시합니다.
• 효과: 이는 아테나가 너무 많은 데이터에 압도되지 않으면서도 '큰 그림'을 볼 수 있게 해줍니다. 현재 단계에 실제로 영향을 미치는 미래 단계들만 고려합니다.

2. '백업 계획' (다중 후보 스케줄링)

기존 플래너들은 "그룹 A 에게 옵션 A 가 가장 좋아 보이니, 이를 선택하자!"라고 말하며 옵션 B 를 폐기했습니다.
아테나는 말합니다. "옵션 A 는 좋아 보이지만, 어쩌면 옵션 B 가 나중에 우리를 골치 아프게 하는 일을 막아줄지도 모른다."

• 비유: 하나의 경로에만 매달리는 대신, 아테나는 여러 버전의 파티 계획을 병렬로 유지합니다. 동시에 다양한 경로를 탐색합니다. 만약 한 경로가 나중에 교통 체증으로 이어지는 것을 발견하면, 다른 경로로 전환할 수 있습니다. 최종 승자는 마지막 순간에만 선택합니다.

3. '일찍 일어나는 새' (EPR 용량 인식 조기 스케줄링)

양자 세계에서 무용수를 이동시키려면 특별한 '복도 허가증' (EPR 자원이라고 함) 이 필요합니다.

• 기존 방식: 플래너는 이동이 필요한 정확한 순간에 허가증을 요청했습니다. 만약 허가증이 더 일찍 준비되어 있었다면, 그것은 사용되지 않은 채 방치되었습니다.
• 아테나 방식: 복도가 비어 있고 허가증이 준비되어 있다면, 아테나는 춤 동작이 공식적으로 시작되기 전이라도 무용수를 즉시 이동시킵니다.
• 효과: 이는 무용수들이 허가증을 기다리며 멈추지 않고 원활하게 움직이게 하여 전체 파티 속도를 크게 높입니다.

결과

저자들은 아테나를 다양한 '춤 동작' (양자 프로그램) 에 대해 테스트하고 현재 최고의 플래너와 비교했습니다. 그 결과는 다음과 같습니다:

• 이동 횟수 감소: 아테나는 방 사이의 느리고 어색한 이동 횟수를 평균 34% 감소시켰으며 (최대 65% 감소 사례도 있음).
• 더 빠른 파티: 프로그램을 완료하는 데 걸린 총 시간이 절반으로 줄었습니다 (평균 2 배 빠르고, 일부 경우 2.9 배 빠름).
• 향상된 품질: 오류 (mistakes) 와 대기 (decoherence) 가 줄어들어 양자 프로그램의 최종 결과가 훨씬 더 정확해졌습니다.

요약

아테나를 다음과 같이 초-조직적인 파티 플래너로 생각하세요:

1. 실제로 중요한 파티 부분들만 미리 봅니다.
2. 만일의 사태를 대비해 여러 개의 백업 계획을 준비해 둡니다.
3. 공식 시작 시간을 기다리는 대신, 복도가 비는 대로 즉시 사람들을 이동시킵니다.

이러한 방식으로 아테나는 분산 양자 컴퓨터가 훨씬 더 빠르고 신뢰성 있게 작동하도록 하여, 이러한 강력한 기계들을 가로막아 온 '과도한 이동' 문제를 해결합니다.

기술 요약

기술 요약: Athena: 분산 양자 컴퓨터를 위한 최적화 스케줄링 컴파일러

1. 문제 제기

분산 양자 컴퓨터 (DQC) 는 광학 인터커넥트를 통해 작은 칩들을 연결함으로써 단일 칩의 확장성 한계를 해결합니다. 이는 더 큰 시스템 크기를 가능하게 하지만, 상당한 성능 저하를 초래합니다. 비국소 CNOT 게이트(다른 칩에 있는 큐비트 간의 연산) 는 큐비트 재배치 또는 게이트 텔레포테이션 수행을 위해 텔레포테이션에 의존합니다. 이러한 비국소 연산은 국소 CNOT 대비 4.3~7.7 배 더 느리고, 4 배 더 오류가 발생하기 쉽습니다. 이는 프로그램 충실도를 심각하게 저하시키고 지연 시간을 증가시킵니다.

기존 DQC 컴파일러 (예: AutoComm, QuComm) 는 비국소 CNOT 을 '블록'으로 그룹화하고 해당 블록 내에서 텔레포테이션 경로를 통합적으로 최적화함으로써 이를 완화하려 시도합니다. 그러나 본 논문은 이러한 블록 수준 스케줄링 접근법의 두 가지 치명적인 한계를 지적합니다:

1. 블록 간 선행 검토 (Lookahead) 부재: 현재 컴파일러는 다음 블록으로 이동하기 전에 블록의 스케줄을 확정합니다. 따라서 현재 블록의 텔레포테이션 결정이 미래 블록의 텔레포테이션 비용에 미치는 영향을 평가할 수 없습니다. 특정 큐비트에서의 연속적인 텔레포테이션은 대부분 국소 게이트로 구성된 많은 수의 블록 (예: QAOA 프로그램에서 약 89 개 블록) 으로 분리되어 있으므로, 후속 블록을 포함하도록 선행 검토 창을 단순히 확장하는 것은 비효율적입니다.
2. 지연된 스케줄링: 컴파일러는 이전 블록이 완전히 스케줄링될 때까지 미래 게이트와 이에 필요한 텔레포테이션의 스케줄링을 미룹니다. 이러한 '수요 기반' 스케줄링은 상당한 지연 오버헤드를 초래합니다. 실험에 따르면 데이터 의존성이 더 일찍 해결되었음에도 불구하고 텔레포테이션의 약 50% 가 평균 7.5 ms(최대 36 ms) 동안 대기하는 것으로 나타났습니다.

2. 방법론: Athena 컴파일러

저자들은 이러한 한계를 극복하기 위해 유틸리티 기반 선행 검토와 다후보 블록 스케줄링 (UMS) 및 **EPR 용량 인식 조기 스케줄링 (EES)**이라는 두 가지 주요 메커니즘을 통해 설계된 Athena 컴파일러를 제안합니다.

2.1 유틸리티 기반 선행 검토와 다후보 블록 스케줄링 (UMS)

UMS 는 블록 간 선행 검토 부재와 비최적 스케줄에 대한 조기 확정 위험을 해결합니다.

• 유틸리티 기반 선행 검토: UMS 는 다음 $F$개의 블록을 맹목적으로 고려하는 대신, 현재 스케줄링 중인 블록과 중첩되는 큐비트를 공유하는 '유용한' 미래 블록만 포함하는 선행 검토 창을 구성합니다. 이를 통해 컴파일러는 지수적 복잡성을 초래하지 않으면서 관련 미래 연산에 대한 텔레포테이션 경로를 최적화할 수 있습니다.
• 다후보 스케줄링: 컴파일러가 국소적으로 최적이지만 전역적으로는 비최적인 스케줄에 고정되는 것을 방지하기 위해 UMS 는 솔루션 트리를 유지합니다. 현재 블록에 대해 최대 너비 $w$까지 여러 개의 후보 스케줄을 유지합니다. 각 비국소 게이트에 대해 UMS 는 텔레포테이션 경로 (RELOCATE 대 Re-CNOT) 를 평가하고 스케줄링 그룹 내 미래 게이트에 미치는 영향을 추정합니다. 트리는 즉시 텔레포테이션 비용, EPR 해제 비용, 그리고 미래 게이트에 미치는 영향의 추정 비용을 포함한 비용 함수를 기반으로 상위 $w$개 솔루션만 유지되도록 가지치기됩니다.

2.2 EPR 용량 인식 조기 스케줄링 (EES)

EES 는 지연된 스케줄링으로 인한 지연 오버헤드를 해결합니다.

• 의존성 분리: EES 는 텔레포테이션 스케줄링과 이를 필요로 하는 CNOT 게이트 스케줄링을 분리합니다. 미래 텔레포테이션에 관여하는 큐비트가 중간 연산에 필요하지 않다면, EPR 용량이 사용 가능할 경우 재배치를 조기에 스케줄링합니다.
• 조기 실행: 미래 게이트에 대한 데이터 의존성이 해결되면, EES 는 원래 블록 타임라인보다 일찍 해당 게이트와 필요한 텔레포테이션을 스케줄링하려 시도합니다.
• 용량 제약: 중간 연산에 필요한 EPR 자원을 조기 스케줄링이 고갈시키는 것을 방지하기 위해 EES 는 EPR 용량 분포를 추적합니다. 총 텔레포테이션 수를 증가시키거나 칩의 EPR 용량을 완전히 소모하지 않는 경우에만 작업을 앞당겨 스케줄링하여 하류 연산이 불이익을 받지 않도록 보장합니다.

2.3 워크플로우

Athena 는 표준 컴파일 흐름으로 작동합니다:

1. 매핑: 정적 또는 동적 파티셔닝 방법 (Min-Cut 등) 을 사용하여 프로그램 큐비트를 물리적 칩에 할당합니다.
2. 블록 형성: 중첩되는 큐비트와 EPR 용량 제약을 기반으로 게이트를 블록으로 그룹화합니다.
3. UMS 스케줄링: 다후보 유틸리티 기반 접근법을 사용하여 블록을 스케줄링합니다.
4. EES 최적화: 자격을 갖춘 작업을 가능한 한 일찍 실행하도록 스케줄을 정교하게 다듬습니다.

3. 주요 기여

본 논문은 다음과 같은 구체적인 기여를 합니다:

1. Athena 컴파일러: 텔레포테이션 오버헤드와 지연 시간을 줄이는 DQC 를 위한 새로운 컴파일러.
2. UMS 메커니즘: 중첩되는 큐비트에만 초점을 맞춘 유틸리티 기반 선행 검토를 사용하고, 비최적 경로에 대한 조기 확정을 피하기 위해 여러 후보 스케줄을 유지하는 스케줄링 전략.
3. EES 메커니즘: 사용 가능한 EPR 용량을 활용하고 블록 경계를 가로지르는 데이터 의존성을 해결함으로써 미래 연산과 재배치를 조기에 스케줄링하는 전략.
4. 종합 평가: 다양한 DQC 아키텍처 (2×2, 2×3, 3×3) 및 프로그램 크기 (최대 86.4K 개의 CNOT) 에 걸쳐 최신 컴파일러 (QuComm) 와의 광범위한 벤치마킹.

4. 결과

대표적인 벤치마크 (QAOA, 쇼어 알고리즘, QFT, VQE 포함) 에 대한 평가는 QuComm 대비 상당한 개선을 보여줍니다:

• 텔레포테이션 감소: Athena 는 평균 **34%**만큼, 최선의 경우 **65%**까지 유효 텔레포테이션 수를 감소시킵니다.
• 지연 시간 감소: Athena 는 QuComm 대비 평균 2.0 배, 최대 2.9 배까지 프로그램 지연 시간을 줄입니다.
• 확장성: 이러한 개선은 다양한 시스템 크기 (100~500 큐비트) 및 칩 구성에서 유지됩니다.
• 충실도 영향: 텔레포테이션과 지연 시간을 줄임으로써 Athena 는 프로그램 충실도를 향상시킵니다. 32 큐비트 QAOA 프로그램의 경우, 충실도가 QuComm 의 0.08 에서 Athena 의 0.15 로 증가하여 88% 개선되었습니다.
• EES 영향: EES 구성 요소만으로도 텔레포테이션 동시성이 1.68 배 증가하여 대기 시간을 크게 단축시킵니다.

5. 중요성 및 주장

본 논문은 Athena 가 블록 수준 스케줄링의 근본적인 한계를 해결함으로써 DQC 컴파일 분야에서 중요한 진전을 이루었다고 주장합니다. 저자들은 다음과 같은 점을 강조합니다:

• 선행 검토의 중요성: 블록 내에서만 최적화하는 것만으로는 부족합니다. 텔레포테이션 결정의 영향은 먼 미래까지 미치므로, 유틸리티 기반 선행 검토 접근법이 필수적입니다.
• 유연성이 비최적성을 방지함: 여러 후보 스케줄을 유지함으로써 컴파일러는 국소적으로는 최적이지만 전역적으로는 비최적인 결정에서 회복할 수 있습니다. 이는 단일 경로 그리디 컴파일러에 결여된 기능입니다.
• 지연 시간이 병목 현상임: 미래 연산 스케줄링의 지연은 주요 지연 원인이며, EPR 자원을 신중하게 관리한다면 텔레포테이션 스케줄링과 게이트 스케줄링을 분리함으로써 완화할 수 있습니다.

저자들은 Athena 를 큐비트 매핑 전략과 직교하며 기존 내결함성 컴파일 흐름과 호환 가능한 일반화 가능한 솔루션으로 위치시킵니다. 다만, 완전한 엔드투엔드 내결함성 컴파일은 향후 연구로 남겨두었다고 언급합니다. 논문은 대규모 DQC 를 실현 가능하게 만들기 위해서는 오류 및 지연 시간 페널티를 직접 해결하는 최적화된 저수준 스케줄링이 필수적이라고 결론지었습니다.