Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization

본 논문은 결정의 품질을 유지하면서 불필요한 계산을 제거하여 큐비트 매핑 및 라우팅을 위한 SABRE 휴리스틱 검색을 크게 가속화하기 위해 위치 그래프 추상화와 메모이제이션 기법을 활용하는 트랩드 이온 QCCD 아키텍처용 컴파일 프레임워크를 소개합니다.

핵심

거대한 좁은 복도 안에서 대규모 고위험 댄스 경연 대회를 조직하려 한다고 상상해 보세요. 댄서들은 큐비트(양자 컴퓨터의 기본 단위) 이며, 목표는 특정 댄서 쌍이 같은 작은 방 ( "트랩") 에서 만나 특별한 듀엣 (양자 게이트) 을 수행하도록 하는 것입니다.

그러나 엄격한 규칙이 있습니다:

1. 복도는 붐빕니다: 댄서들을 순간이동시킬 수 없습니다. 그들은 반드시 복도를 통해 물리적으로 이동해야 합니다.
2. 이중 예약 금지: 한 번에 한 방에 들어갈 수 있는 댄서의 수에는 제한이 있습니다.
3. 교통 체증: 한 댄서가 정지해 있는 다른 댄서 옆을 지나가야 할 경우, 경로가 막힙니다. 먼저 정지해 있는 댄서를 치워야 합니다.

이것은 트랩드 이온 QCCD라는 특정 유형의 양자 컴퓨터를 위한 양자 컴파일의 도전 과제입니다. 제공된 논문은 이 댄스 조직을 훨씬 더 빠르고 효율적으로 만드는 새로운 "교통 통제 시스템"을 설명합니다.

다음은 저자들이 수행한 작업을 간단한 비유로 정리한 것입니다:

1. 옛 지도 vs 새로운 "위치 그래프"

문제: 과거에는 컴퓨터 프로그램이 "커플링 그래프"라는 단순한 지도를 사용했습니다. 이 지도는 어떤 역들이 연결되어 있는지만 보여주는 지하철 도표와 같았습니다. 두 항목을 교환하는 (예: 좌석 교환) 컴퓨터에는 훌륭했지만, 이온을 복잡한 복도와 방의 미로 속에서 물리적으로 이동시켜야 하는 이온 컴퓨터에는 실패했습니다.

해결책: 저자들은 위치 그래프를 도입했습니다.

• 비유: 옛 지도를 지하철 노선도로 생각한다면, 새로운 위치 그래프는 건물의 전체 3D 건축 도면입니다. 이 지도는 어떤 방들이 연결되어 있는지뿐만 아니라 바닥의 모든 타일, 모든 복도, 모든 문, 그리고 한 지점에서 다른 지점까지 이동하는 데 정확히 얼마나 걸리는지까지 보여줍니다.
• 중요성: 이를 통해 컴퓨터는 "그 벽을 통과할 수 없다"거나 "그 방은 두 사람이 들어가기엔 너무 작다"와 같은 실제 물리적 제약을 이해할 수 있게 됩니다.

2. "교통 경찰" 문제 (혼잡)

문제: 컴퓨터가 댄서 (이온) 를 방으로 이동시키려 할 때, 종종 다른 댄서에게 경로가 막혀 있음을 발견합니다. 옛 소프트웨어는 멈추고 지도를 보고 새로운 경로를 계산한 후 다시 시도했습니다. 경로가 다시 막히면 다시 계산했습니다. 이는 빨간불에 걸릴 때마다 GPS 가 전체 경로를 처음부터 다시 계산하는 것과 같았습니다. 이는 극도로 느렸습니다.

해결책: 저자들은 이전 시스템의 "가벼운" 버전인 LightSHAW를 만들었습니다.

• 비유: 메모장을 들고 있는 교통 경찰관을 상상해 보세요.
  • 메모이제이션: A 지점에서 B 지점까지의 거리를 매번 다시 계산하는 대신, 경찰관은 한 번만 적어둡니다. 같은 상황이 다시 발생하면 메모를 확인하기만 하면 됩니다.
  • "차단 프로파일": 시스템은 "1 번 복도에서 5 번 방으로 가려면 항상 3 번 문을 통과해야 한다"는 사실을 기억합니다. 그 문이 막혔을 때의 "페널티"를 미리 계산해 둡니다.
  • 결과: 정체가 발생하면 시스템은 당황하여 모든 것을 다시 계산하지 않습니다. 메모를 빠르게 확인합니다. "아, 이 정체를 알고 있군. 어떻게 해결할지 정확히 알고 있어." 이로 인해 과정이 훨씬 빨라집니다.

3. "스마트 필터" (가지치기)

문제: 댄서 그룹이 어느 방으로 가야 할지 결정할 때, 컴퓨터는 과거에 건물 내의 모든 가능한 방을 확인하며 각각에 대해 완전한 계산을 수행했습니다.

• 비유: 도시의 모든 식당에 들어가서 주문하고 맛본 후 가장 좋은 식당을 고르려고 시도하는 것과 같습니다.

해결책: 그들은 가지치기 단계를 추가했습니다.

• 비유: 식당에 들어가기 전에 시스템이 "메뉴 미리보기" (하한 점수) 를 확인합니다. 미리보기가 "이곳은 확실히 너무 비싸다"고 말하면, 시스템은 절대 안으로 들어가지 않고 즉시 건너뜁니다. 시스템은 유망해 보이는 소수의 식당에만 비싼 전체 검사를 수행합니다. 이는 막대한 시간을 절약해 줍니다.

4. 큰 놀라움: 단순한 시스템에서도 작동합니다

주장: 일반적으로 지도를 더 자세하게 만들 때 (지하철 도면에서 3D 건축 도면으로 변경하는 것처럼), 컴퓨터는 더 많은 데이터를 처리해야 하므로 느려집니다.

• 결과: 저자들은 복잡한 3D 도면이 필요하지 않은 단순한 시스템 (초전도 컴퓨터) 에서 새로운 "위치 그래프"를 테스트했습니다. 그 결과, 새로운 시스템은 기존 단순 시스템과 동일한 속도로 작동했습니다.
• 비유: 종이 지도에서 GPS 앱으로 업그레이드하는 것과 같습니다. GPS 가 더 많은 데이터를 가지고 있어 더 느릴 것이라고 생각할 수 있지만, 이를 매우 잘 최적화했기 때문에 간단한 이동에는 종이 지도만큼 빠르게 실행되면서도 필요할 때 복잡한 우회로를 처리할 수 있습니다.

결과 요약

논문은 이 새로운 "위치 그래프"와 "LightSHAW" 메모리 기법을 사용함으로써 다음과 같은 성과를 거두었다고 주장합니다:

1. 속도: 이전보다 훨씬 빠르게 대규모 복잡한 이온 컴퓨터를 위한 양자 회로를 컴파일 (조직) 할 수 있습니다.
2. 확장성: 댄서 (큐비트) 의 수가 증가함에 따라 조직하는 데 걸리는 시간이 이전보다 훨씬 느리게 증가합니다.
3. 신뢰성: 이 시스템은 다른 시스템이 완전히 실패하는 "더 빽빽한" 건물 (더 붐비는 방) 을 처리할 수 있습니다.
4. 범용성: 이 단일 시스템은 이제 속도를 늦추지 않고 단순한 "교환" 컴퓨터와 복잡한 "셔틀링" 컴퓨터 모두를 처리할 수 있습니다.

간단히 말해, 그들은 과거의 정체를 기억하고 나쁜 경로를 건너뛰는 더 똑똑하고 빠른 교통 통제 시스템을 구축하여, 양자 컴퓨터가 교통 체증에 갇히지 않고 복잡한 춤을 추도록 했습니다.

기술 요약

기술 요약: 위치 그래프 추상화와 메모이제이션을 통한 큐비트 매핑 및 라우팅 확장

문제 제기

확장 가능한 큐비트 매핑 및 라우팅은 양자 컴파일링, 특히 트랩드 이온 양자 전하 결합 장치 (TI-QCCD) 아키텍처에서 여전히 중요한 병목 현상입니다. 정적 결합 그래프에서 SWAP 연산을 통해 라우팅을 모델링하는 초전도 시스템과 달리, TI-QCCD 는 이온을 세그먼트와 접합부를 통해 물리적으로 이동시켜야 합니다. 이 과정은 이동의 합법성, 트랩 용량 제한, 그리고 중간 위치가 점유되어 발생하는 혼잡 (congestion) 에 의해 제약받습니다.

기존의 SABRE 와 같은 휴리스틱 방법은 결합 그래프 (Coupling Graph) 와 같은 추상화에 의존하는데, 이는 물리적 수송, 중간 점유, 경로 차단과 같은 복잡한 제약을 표현할 수 없어 TI-QCCD 에는 부적합합니다. 이전 연구에서 실행 가능한 위치, 이동 경로, 라우팅 제약을 통합하는 위치 그래프 (Position Graph) 추상화를 도입했으나, 초기 구현은 휴리스틱 검색 및 혼잡 해결 중 발생하는 중복 계산으로 인해 심각한 확장성 문제를 겪었습니다. 예를 들어, 180 이온 장치에서 128 큐비트 회로를 컴파일하는 데 중복 계산으로 인해 하루가 소요되기도 했습니다.

방법론

본 논문은 라우팅 결정을 변경하지 않으면서 중복 계산을 제거하기 위해 캐싱 및 메모이제이션 전략으로 위치 그래프 추상화를 강화하는 컴파일 프레임워크를 제안합니다.

1. 위치 그래프 추상화

본 프레임워크는 라벨이 지정된 그래프인 위치 그래프 ($G_p$) 를 활용합니다. 여기서:

• 정점 (Vertices) 은 점유 가능한 물리적 위치 (트랩, 중간 수송 영역) 를 나타냅니다.
• 간선 (Edges) 은 유효한 전이 (트랩 내 스왑, 트랩과 수송 간의 병합/분할, 또는 수송 내 이동) 를 나타냅니다.
• 라벨 (Labels) 은 연산 유형 (스왑, 병합/분할, 이동) 을 구분합니다.
  이 추상화는 TI-QCCD 의 더 풍부한 위상 구조를 지원하기 위해 초전도 시스템에 사용되는 결합 그래프를 일반화합니다.

2. 아키텍처 수준 캐싱

오버헤드를 줄이기 위해 저자들은 컴파일 실행 중 정적으로 유지되는 아키텍처 의존적 양들을 사전에 계산하여 캐시합니다:

• 모든 쌍 최단 경로 및 거리 행렬.
• 간선 라벨에서 파생된 실행 가능 서브그래프.
• 경로 차단 프로파일: 임의의 소스 - 타겟 이동에 대해, 차단을 일으킬 수 있는 중간 위치의 캐시된 목록과 이를 해결하기 위한 고정 페널티.

3. LightSHAW: 메모이제이션된 혼잡 해결

핵심 기여는 LightSHAW로, SHAW(SHuttling-AWare) 휴리스틱의 캐시된 변형입니다. SHAW 는 이동하는 이온이 점유된 위치에 의해 차단될 때 재귀적으로 혼잡을 해결합니다. LightSHAW 는 2 단계 캐시를 통해 이를 최적화합니다:

• 로컬 스코어링 세트 캐시: 주어진 후보 제거 이동에 대해 검사할 인접 위치 집합을 캐시하여 검색 영역을 정의하기 위한 반복적인 그래프 탐색을 방지합니다.
• 구성 키 기반 혼잡 메모이제이션: "로컬 점유 서명"($\sigma$) 을 기반으로 혼잡 점수를 메모이제이션합니다. 키는 $(p, t, b, d, \sigma)$이며, 여기서 $p$는 후보 위치, $t$는 타겟, $b$는 차단, $d$는 검색 깊이, $\sigma$는 로컬 스코어링 세트의 점유를 나타냅니다. 이를 통해 시스템은 전체 장치를 다시 스캔하지 않고도 반복되는 로컬 혼잡 패턴에 대해 점수를 재사용할 수 있습니다.

4. 트랩 선택 가지치기

다중 큐비트 게이트에 대한 목표 트랩 선택을 최적화하기 위해 저자들은 하한 가지치기 전략을 구현합니다. 각 트랩에 대한 라우팅 비용의 낙관적 하한을 계산합니다 (혼잡 및 서로 다른 슬롯 요구 사항을 무시). 트랩은 이 하한이 증가하는 순서로 평가되며, 다음 후보의 하한이 지금까지 찾은 최상의 정확한 점수를 초과하면 정확한 점수 계산이 중단됩니다.

5. 초전도 아키텍처에서의 검증

위치 그래프가 더 단순한 아키텍처에 불필요한 오버헤드를 부과하지 않는지 확인하기 위해, 저자들은 전통적인 결합 그래프 백엔드와 위치 그래프 백엔드를 모두 사용하여 LightSABRE(SABRE 변형) 를 구현했습니다. 두 구현 모두 동일한 라우팅 결정을 내리도록 구성하여 추상화 자체의 비용을 격리했습니다.

주요 기여

1. 중복 계산 제거: SHAW 에서 최단 이동 (MOVE) 경로, 이동 시간 거리, 차단 관련 경로 정보를 식별하고 캐싱합니다.
2. LightSHAW 알고리즘: 아키텍처 의존 정보 (이동 경로, 로컬 제거 영역) 와 로컬 점유 점수를 재사용하는 메모이제이션된 혼잡 해결 절차를 도입하여 재귀적 차단 해결 중 반복 작업을 크게 줄입니다.
3. 추상화 오버헤드 분석: LightSABRE 라우팅을 위해 결합 그래프를 위치 그래프로 대체할 때 실행 시간 오버헤드가 미미함을 입증하여, 더 풍부한 아키텍처 모델이 본질적으로 컴파일 속도를 저해하지 않음을 보여줍니다.
4. 오픈 소스 프레임워크: 초전도 및 TI-QCCD 워크플로우를 모두 지원하는 구현을 제공하여 이종 양자 아키텍처 전반의 실험을 용이하게 합니다.

실험 결과

저자들은 16 에서 512 큐비트에 이르는 QAOA, QFT, 해밀토니안 시뮬레이션 회로 (TFIM, TFXY) 를 포함한 벤치마크를 사용하여 프레임워크를 평가했습니다.

• 컴파일 시간 확장: LightSHAW 는 확장성 측면에서 기존 SHAW 와 최첨단 QCCDSim 시뮬레이터를 크게 능가합니다.
  • SHAW: $O(x^{3.91})$로 확장됩니다.
  • QCCDSim: $O(x^{3.04})$로 확장됩니다.
  • LightSHAW: $O(x^{1.72})$로 확장됩니다.
  • LightSHAW 는 매우 작은 회로의 경우 QCCDSim 에 비해 오버헤드가 더 높지만, 더 큰 회로 (예: 180 이온 아키텍처) 에서는 QCCDSim 성능과 일치하거나 능가하며 훨씬 더 유리하게 확장됩니다.
• 연산 시간 (품질): LightSHAW 는 QCCDSim 에 비해 총 연산 시간 (게이트 실행 + 수송) 이 현저히 낮은 스케줄을 생성합니다. 예를 들어, 512 큐비트 QAOA 회로에서 LightSHAW 는 QCCDSim 대비 0.171 의 연산 시간 비율을 달성하여 실행 시간을 약 6 배 줄였습니다.
• 강건성: 엄격한 자원 제약 시나리오 (트랩당 높은 이온 활용도) 에서 QCCDSim 은 유효한 컴파일을 생성하지 못하는 경우가 빈번했습니다 (결과에서 'X'로 표시). 반면 LightSHAW 는 모든 인스턴스를 성공적으로 완료했습니다.
• 초전도 호환성: 초전도 라우팅 (LightSABRE) 에 적용될 때, 위치 그래프 백엔드는 전통적인 결합 그래프 백엔드와 실행 시간을 일치시켜, 이 추상화가 더 단순한 아키텍처에 대해 상당한 페널티를 부과하지 않음을 확인했습니다.

의의

본 논문은 위치 그래프 추상화가 이종 양자 아키텍처 전반에 걸쳐 확장 가능한 큐비트 매핑 및 라우팅을 위한 실용적이고 효과적인 경로를 제공한다고 주장합니다. 아키텍처 인식 표현과 메모이제이션된 휴리스틱 평가를 결합함으로써, 이 프레임워크는 초전도 시스템의 성능을 희생하지 않으면서 TI-QCCD 컴파일의 확장성 병목 현상을 해결합니다. 결과는 컴파일러 인프라가 최소 인접성 모델을 넘어 수송과 같은 복잡한 물리적 제약을 지원하면서도 대규모 양자 컴파일에 필요한 효율성을 유지할 수 있음을 시사합니다. 이 연구는 통합된 표현이 SWAP 기반 및 수송 기반 아키텍처 모두에 사용할 수 있음을 입증하여, 단일 프레임워크가 다양한 하드웨어 제약을 처리할 수 있게 합니다.