QuPort: Topology-, Port-, and Congestion-Aware Compilation for Modular Multi-QPU Quantum Systems

본 논문은 3 단계 모델과 TPCCAP 알고리즘을 활용하여 큐비트 매핑, 포트 할당, 그리고 인터커넥트 혼잡을 공동으로 최적화함으로써 QPU 간 트래픽과 통신 병목 현상을 최소화하는 다중 QPU 시스템을 위한 모듈형 컴파일 프레임워크인 QuPort 를 소개합니다.

핵심

거대한 복잡하고 많은 손님이 '양자 비트'(큐비트) 이고, 그들이 머무는 방들이 작은 개별 양자 컴퓨터인 QPUs인 파티를 조직하려 한다고 상상해 보세요.

과거에는 모든 손님이 하나의 거대한 볼룸에 있었습니다. '파티 기획자'(컴파일러) 의 역할은 서로 대화해야 하는 손님들이 서로 옆에 서 있도록 하는 것이 전부였습니다. 만약 그들이 옆에 있지 않다면, 기획자는 그들이 대화할 수 있을 때까지 사람들을 재배치해야 했습니다 (이 과정을 '라우팅'이라고 합니다).

하지만 이제 우리는 모듈형 양자 컴퓨터를 구축하고 있습니다. 거대한 볼룸 하나 대신, 많은 작은 개별 방들 (QPU) 이 있는 건물을 가지고 있습니다. 일부 방들은 복도로 연결되어 있지만, 그 복도들은 좁고 사용하기 비쌉니다.

이 논문은 QuPort라는 새로운 파티 기획자를 소개합니다. 간단한 비유를 사용하여 그 작동 방식을 설명하겠습니다:

1. 세 가지 지도

파티를 계획하기 위해 QuPort 는 세 가지 다른 지도를 동시에 봅니다:

• 손님 명단 (논리적 그래프): 누가 누구와 얼마나 대화해야 하는가? (일부 손님은 절친하여 끊임없이 대화해야 하고, 다른 이들은 한 번만 '안녕'이라고 인사합니다).
• 방 배치도 (물리적 지도): 각 작은 방 안에서 어떤 의자들이 서로 옆에 있는가?
• 건물 설계도 (연결 그래프): 방들은 어떻게 연결되어 있는가? 직접적인 복도가 있는가, 아니면 다음 방에 도달하려면 세 개의 다른 방을 거쳐야 하는가?

2. 큰 문제: '입구' 병목 현상

만약 두 명의 절친을 다른 방에 배치하면, 그들은 복도 너머로 외쳐야 합니다. 하지만 두 가지 큰 문제가 있습니다:

1. 너무 많은 외침: 너무 많은 친구 쌍이 다른 방에 있으면 복도가 막힙니다.
2. 문이 너무 적음: 각 방에는 몇 개의 '통신 문'(포트) 만 있습니다. 100 명의 손님이 방에 있지만 그중 5 명만 밖으로 외쳐야 한다면, 한 번에 5 명만 나갈 수 있습니다. 나머지는 갇히게 됩니다.

3. 해결책: TPCCAP 전략

QuPort 는 누가 어느 방에 들어갈지 결정하기 위해 TPCCAP라는 특별한 전략을 사용합니다. 세 가지 요소를 균형 있게 맞추려고 노력합니다:

• 거리: 절친을 같은 방에 두려고 노력합니다. 만약 다른 방에 있어야 한다면, 서로 가까운 이웃 방 (짧은 복도) 에 배치합니다.
• 문 압력: 어떤 방도 실제로 가진 문보다 더 많은 '문'을 사용하도록 강요받지 않도록 합니다. 문이 5 개뿐인 방에 10 명의 외치는 손님을 넣지 않습니다.
• 복도 교통: 복도 중 하나가 너무 많은 교통량으로 막히지 않도록 외침을 분산시킵니다.

4. QuPort 가 파티를 계획하는 방법 (알고리즘)

QuPort 는 단순히 추측하지 않고, 최상의 배치를 찾기 위해 몇 가지 영리한 트릭을 사용합니다:

• 무거운 간선 클러스터링: 가장 강한 우정 관계를 먼저 보고 나머지 문제를 걱정하기 전에 그 쌍들을 같은 방에 묶어둡니다.
• 균형 잡힌 탐욕적 접근: 한 번에 한 명씩 방을 채우며, 방을 너무 붐비게 하지 않으면서 그 손님에게 가장 합리적인 방을 선택합니다.
• 시뮬레이션 어닐링: 이는 '두 번째 추측' 단계와 같습니다. 초기 계획 후, 두 손님을 바꾸는 것과 같은 무작위 작은 변경을 시도하여 파티가 더 원활하게 진행되는지 확인합니다. 변경이 상황을 개선하면 유지합니다. 상황을 악화시키더라도 '충분히 좋은' 하지만 '완벽하지는 않은' 계획에 갇히지 않기 위해 잠시 유지할 수도 있습니다.

5. '원격 이벤트' 목록

손님들이 방에 배정되면, QuPort 는 특별한 지시 목록을 생성합니다.

• 로컬 지시: "손님 A 와 손님 B 는 1 번 방에 있습니다. 그들은 정상적으로 대화할 수 있습니다."
• 원격 이벤트: "손님 A 는 1 번 방에 있고 손님 B 는 2 번 방에 있습니다. 그들은 대화해야 합니다."

QuPort 는 그들이 복도 너머로 어떻게 대화하는지 (레이저, 전선, 또는 마법을 사용하는지) 를 파악하지 않습니다. 단지 그 대화가 발생해야 하는 지점을 표시하고 하드웨어 엔지니어에게 "여기에 이 특정 외침을 처리할 프로토콜을 구축해야 합니다"라고 말합니다.

6. 일정

마지막으로, QuPort 는 파티가 얼마나 걸릴지 추정합니다. 복도가 막히거나 문이 부족해지지 않으면서 동시에 발생할 수 있는 '외침'의 수를 세어봅니다. 이러한 추상적인 규칙을 기반으로 총 소요 시간 (메이크스팬) 을 대략적으로 추정합니다.

QuPort 가 아닌 것

이 논문은 이 도구가 무엇이 아닌지에 대해 매우 명확합니다:

• 물리적인 기계가 아닙니다.
• 양자 컴퓨터의 구체적인 물리 (배터리 수명이나 레이저가 만드는 오류 양과 같은 것) 를 알지 못합니다.
• 실제로 방 사이에서 '외침'을 수행하지는 않습니다.

요약하자면: QuPort 는 모듈형 양자 컴퓨터를 위한 스마트한 교통 통제관입니다. 서로 기다리며 갇히지 않도록 여러 작은 컴퓨터 간 작업을 가장 잘 분할하는 방법을 찾아내면서, 실제로 존재하는 문이나 복도보다 더 많은 것을 사용하려 하지 않도록 보장합니다. 이는 실제 하드웨어 엔지니어들이 나중에 '외침' 기술을 구축하는 최선의 방법을 파악할 수 있도록 지시를 준비합니다.

기술 요약

기술 요약: QuPort - 모듈형 다중 QPU 양자 시스템을 위한 토폴로지, 포트, 혼잡 인식 컴파일

1. 문제 정의

여러 양자 처리 장치 (QPU) 를 인터커넥트를 통해 연결하는 모듈형 양자 아키텍처는 단일 장치와 구별되는 고유한 컴파일러 과제를 제시합니다. 단일 장치 컴파일러에서는 주요 제약 조건이 로컬 커플링 맵이며, 비로컬 상호작용은 SWAP 삽입을 통해 해결됩니다. 그러나 모듈형 시스템에서는 서로 다른 QPU 에 있는 큐비트 간의 상호작용이 단순히 "더 긴" 로컬 게이트가 아니라, 희소한 통신 자원인 인터커넥트 토폴로지, 통신 포트, 링크 용량에 의존합니다.

기존 컴파일러는 종종 QPU 간 통신을 부차적인 문제로 간주하거나 표준 라우팅 내부에 숨깁니다. 그러나 이 접근 방식은 모듈형 시스템에는 부적절합니다. 단일 커플링 그래프에서는 수용 가능한 매핑이 다음과 같은 경우 모듈형 환경에서는 실패할 수 있기 때문입니다:

1. 과도한 QPU 간 트래픽을 생성하는 경우.
2. 소수의 인터커넥트 링크에 트래픽을 집중시켜 혼잡을 유발하는 경우.
3. 통신 포트가 부족한 QPU 에 다른 QPU 와 상호작용하는 너무 많은 경계 큐비트 (boundary qubits) 를 할당하는 경우.

본 논문은 특정 물리적 원격 게이트 프로토콜 (예: 광학 링크, 얽힘 생성) 을 선택하기 전에 로컬 장치 연결성과 QPU 간 통신을 명시적으로 동시에 고려하는 컴파일러 프레임워크의 필요성을 다룹니다.

2. 방법론

QuPort 는 Qiskit 위에 구축된 Python 기반 컴파일 프레임워크입니다. 이는 리소스 사용을 최적화하기 위한 3 단계 시스템 모델과 특정 파티셔닝 알고리즘을 도입합니다.

2.1 시스템 모델

프레임워크는 컴파일 문제를 세 가지 별도의 그래프로 추상화합니다:

1. 논리적 상호작용 그래프 ($G_L$): 노드가 논리적 큐비트이고 간선 가중치가 두 큐비트 간 상호작용의 빈도나 시간적 중요도를 나타내는 가중치 무방향 그래프입니다.
2. 물리적 커플링 맵: 각 개별 QPU 내의 연결성을 나타내는 방향 그래프입니다 (예: 그리드, 링, 클리크).
3. QPU 인터커넥트 그래프 ($G_Q$): QPU 를 연결하는 토폴로지를 나타내는 무방향 그래프입니다 (예: 메시, 링, Clos, 팻트리). 이 그래프는 홉 거리와 링크 부하를 계산하는 데 사용됩니다.

시스템은 각각 $C$개의 연산 큐비트와 $P$개의 통신 큐비트를 가진 $N$개의 QPU 를 가정합니다. 논리적 큐비트에서 QPU 로의 파티션 ($\pi$) 은 각 QPU 당 용량 제약 ($C+P$) 을 준수해야 합니다.

2.2 TPCCAP 목적 함수

QuPort 의 핵심은 세 가지 비용 항의 가중 합을 최소화하는 TPCCAP(토폴로지, 포트, 혼잡 인식 파티셔닝) 목적 함수 $J(\pi)$입니다:

1. 가중 컷 거리: $\sum w_{ij} \cdot d(\pi(i), \pi(j))$. 이는 인터커넥트 그래프에서 멀리 떨어진 QPU 에 할당된 큐비트 간의 상호작용을 패널티로 부과합니다. 여기서 $d$는 최단 경로 거리입니다.
2. 통신 포트 오버플로우: $\sum \max(0, b_q - P)^2$. 이는 가용 통신 포트 ($P$) 를 초과하는 경계 큐비트 ($b_q$) 의 수를 가진 QPU 에 패널티를 부과합니다.
3. 라우팅 링크 부하 혼잡: $\sum L_e^2$. 이는 인터커넥트 간선 ($e$) 의 부하 제곱을 패널티로 부과하여 특정 링크에 트래픽이 집중되는 것을 억제합니다.

2.3 알고리즘

QuPort 는 파티셔닝 및 레이아웃 문제를 해결하기 위한 휴리스틱 파이프라인을 구현합니다:

• 무거운 간선 클러스터링: 클러스터 크기가 QPU 용량을 초과하지 않는 한 고가중치 논리적 쌍을 클러스터로 병합합니다.
• 균형 잡힌 탐욕적 파티셔닝: 가중 차수에 기반하여 논리적 큐비트를 하나씩 할당하며, 이미 할당된 이웃 근처에 배치하는 것을 보상하면서 QPU 간 부하를 균형 있게 분배합니다.
• TPCCAP 로컬 검색: 용량 제약을 유지하면서 $J(\pi)$ 목적 함수를 줄이기 위해 큐비트를 이동시켜 초기 파티션을 정제합니다.
• TPCCAP-SA(시뮬레이션 어닐링): 목적 함수를 증가시키는 이동을 때때로 수용하여 지역 최소값을 탈출하는 확률적 정제 단계를 추가합니다.
• 통신 포트 인식 레이아웃: 파티셔닝 후, 다른 QPU 와의 상호작용 총 가중치인 "외부 점수"를 기반으로 통신 포트를 차지할 특정 논리적 큐비트를 선택합니다.
• 분산 프로그램 구성: 분산 모드에서 프레임워크는 QPU 간 두 큐비트 연산을 명시적인 원격 이벤트로 추출하고 동기화 장벽을 삽입하며, 로컬 연상은 해당 QPU 커플링 맵 내에서만 라우팅합니다.

2.4 스케줄링 및 비용 추정

QuPort 는 추상적 비용 매개변수를 사용하여 실행 시간 (메이스팬) 을 근사하는 토폴로지 인식 추정기를 포함합니다:

• 로컬 비용: 단일 큐비트, 두 큐비트, SWAP 연산에 대한 게이트 실행 시간.
• 원격 비용: 얽힘 생성 비용 ($\tau_E$), 고전적 왕복 비용 ($\tau_C$), 원격 오버헤드 ($\tau_R$) 를 결합한 모델.
• 스케줄링: 원격 연산은 사용 가능한 통신 포트와 링크 용량에 기반하여 "라운드"로 패킹되며, 인터커넥트 토폴로지를 준수합니다.

3. 주요 기여

1. 명시적 3 단계 추상화: 논문은 논리적 상호작용 그래프, 물리적 커플링 맵, QPU 인터커넥트 그래프를 분리하는 컴파일러 수준의 추상화를 제안합니다. 이 분리는 표준 단일 장치 컴파일러에는 보이지 않는 모듈형 특정 비용 (거리, 포트, 혼잡) 의 최적화를 가능하게 합니다.
2. TPCCAP 목적 함수: QPU 거리, 통신 포트 희소성, 링크 혼잡을 별도로 또는 부차적인 문제로 취급하는 대신, 이를 공동으로 최적화하는 새로운 목적 함수입니다.
3. 분산 컴파일 경로: 로컬 회로와 원격 이벤트를 명시적으로 분리하는 중간 표현을 생성하는 메커니즘입니다. 이를 통해 컴파일러는 원격 게이트의 특정 하드웨어 구현에 구애받지 않고 모듈형 인식 스케줄을 생성할 수 있습니다.
4. 오픈 소스 프레임워크: Python/Qiskit 으로 구현된 이러한 알고리즘은 모듈형 컴파일 전략을 연구하기 위한 재현 가능한 환경을 제공합니다.

4. 결과 및 검증

논문은 보정된 하드웨어 런타임 결과 보고보다는 프레임워크의 알고리즘 구조와 정확성에 중점을 둡니다.

• 정확성: 저자들은 파티셔닝 알고리즘 (무거운 간선, 탐욕적, TPCCAP, TPCCAP-SA) 이 QPU 당 용량 제약을 엄격히 준수하고 다중 경로 라우팅 루틴이 트래픽 가중치를 보존함을 증명하는 공식적 증명 (명제 1 및 2) 을 제공합니다.
• 검증: 프레임워크는 파티션 입력, 레이아웃 구성, 트래픽 행렬에 대한 검증 검사를 수행하여 유한하고, 음수가 아니며, 대칭적인 값을 보장합니다.
• 결과 범위: 논문은 특정 하드웨어 프로토콜을 능가하거나 보정된 오류율을 제공한다고 주장하지 않습니다. 대신 프레임워크가 정의된 추상적 제약을 준수하는 유효한 파티션과 분산 프로그램을 성공적으로 생성함을 보여줍니다.

5. 중요성 및 주장

논문은 QuPort 를 하드웨어 구현이 아닌 컴파일러 수준의 추상화로 위치시킵니다. 그 중요성은 다음과 같습니다:

• 컴파일과 하드웨어 프로토콜의 분리: 논리적 파티셔닝 및 원격 이벤트 추출을 원격 게이트의 물리적 실현과 분리함으로써, QuPort 는 연구자들이 특정 인터커넥트 기술 (예: 광학 대 마이크로파) 이 확정되기 전에 모듈형 컴파일의 알고리즘 구조를 연구할 수 있게 합니다.
• 리소스 인식 매핑: 모듈형 컴파일은 SWAP 최소화에서 "컷 거리", "포트 오버플로우", "링크 혼잡" 최소화로의 전환이 필요함을 강조합니다.
• 주장의 겸손함: 저자들은 명시적으로 프레임워크가 보정된 하드웨어 런타임을 주장하지 않으며 물리적 원격 게이트 프로토콜을 구현하지 않는다고 명시합니다. "원격 이벤트"는 백엔드가 프로토콜을 제공해야 하는 위치를 나타내는 중간 표현입니다. 스케줄링 추정기는 검증된 네트워크 제어 스케줄러가 아닌 "레이어 기반 탐욕 모델"로 설명됩니다.

요약하자면, QuPort 는 모듈형 양자 컴퓨팅에 내재된 복잡한 리소스 할당 문제에 대한 구조화된 휴리스틱 기반 접근 방식을 제공하며, 플랫폼에 구애받지 않는 방식으로 토폴로지, 포트 가용성, 혼잡 간의 트레이드오프를 탐색할 수 있는 도구를 제공합니다.