기술 요약: COSMA – 모듈형 양자 아키텍처를 위한 페르미온 시뮬레이션 커널의 통신 인지 최적화

1. 문제 정의

양자 시뮬레이션은 양자 컴퓨팅의 주요 응용 분야이며, 특히 계산 화학 및 재료 과학 분야에서 매우 중요합니다. 그러나 화학적으로 유의미한 문제(예: FeMoco 활성 부위 시뮬레이션)를 해결하기 위해 실질적인 양자 이득을 달성하려면, 양자 오류 정정을 고려할 때 수백만 개의 물리적 큐비트가 필요합니다. 단일 코어(Monolithic) 아키텍처는 제어 복잡성, 크로스토크(cross-talk), 열 관리 문제로 인해 이러한 규모로 확장하는 데 큰 어려움을 겪습니다. 결과적으로, 상호 연결된 양자 처리 장치(QPU)로 구성된 모듈형(멀티 코어) 양자 아키텍처가 제안되었습니다.

모듈형 시스템에서는 코어 간 양자 통신(텔레포테이션 또는 분산 얽힘을 통한 통신)이 주요 성능 병목 현상이 됩니다. 상태 전송(state transfer)과 같은 연산은 비용이 많이 들고 노이즈를 유발하며, 최적화되지 않을 경우 실행 시간을 지배할 수 있습니다. 기존의 컴파일 프레임워크는 일반적으로 페르미온-큐비트 매핑, 파울리 스케줄링, 큐비트 할당을 독립적으로 최적화하거나 단일 코어 토폴로지에 대해서만 최적화하므로, 모듈형 시스템 특유의 통신 오버헤드를 해결하지 못합니다.

본 연구가 다루는 핵심 문제는 페르미온 시뮬레이션 커널의 코어 간 상태 전송을 최소화하기 위해 다음의 세 가지 밀접하게 결합된 단계를 **결합 최적화(joint optimization)**하는 것입니다:

1. 페르미온-큐비트(F2Q) 매핑: 페르미온 연산자를 큐비트 연산자로 인코딩합니다.
2. 파울리 스케줄링: 트로터화된 시간 진화 회로(Trotterized time-evolution circuit) 내에서 파울리 항들의 순서를 결정합니다.
3. 큐비트 할당 및 라우팅: 논리 큐비트를 물리적 코어에 할당하고 파울리 가젯(Pauli gadget)을 위한 패리티 트리(parity tree)를 합성합니다.

2. 방법론: COSA 프레임워크

저자들은 교차 계층 공동 설계(cross-layer co-design)를 수행하는 통신 인지 컴파일 프레임워크인 COSMA를 제안합니다. 이 프레임워크는 컴파일 흐름을 독립적인 단계들의 연속이 아닌 하나의 통합된 최적화 문제로 취급합니다.

A. 문제 정식화

입력값은 마요라나(Majorana) 형태의 페르미온 해밀토니안과 특정 코어 용량 및 코어 간 거리를 가진 멀티 코어 하드웨어 그래프입니다. 최적화의 목표는 연속적인 회로 슬라이스 사이에서 논리 큐비트가 이동하는 총 거리의 합으로 정의되는 총 코어 간 전송 비용을 최소화하는 것입니다. 비용 함수는 네 가지 결합된 변수에 의존합니다:

• 매핑 ($M$): 각 파울리 문자열의 서포트(involved qubits)를 결정하는 곱 보존 삼항 트리(Product-Preserving Ternary-Tree, PPTT) 매핑.
• 순서 ($\pi$): 트로터 시퀀스 내 파울리 항들의 순열.
• 패리티 트리 ($\{T_t\}$): 각 파울리 가젯의 CNOT 구조를 정의하는 스패닝 트리(spanning trees).
• 할당 ($\{\ell_l\}$): 각 회로 슬라이스에 대한 논리 큐비트의 코어 할당.

B. 주요 알고리즘 구성 요소

1. 페르미온-큐비트 매핑 최적화

COSMA는 F2Q 매핑을 최적화하기 위해 **유전 알고리즘(Genetic Algorithm, GA)**을 사용합니다.

• 게놈 인코딩: 후보 매핑은 두 가지 구성 요소의 게놈으로 인코딩됩니다: 트리 형태 염색체(삼항 트리의 전위 차수 수열)와 모드 할당 염색체(페르미온 모드의 순열).
• 진화: GA는 토너먼트 선택, 서브트리 스왑 교차(subtree-swap crossover), 서브트리 교체 변이(subtree-replacement mutation)를 사용합니다.
• 적합도(Fitness): 적합도 함수는 특정 매핑을 고정한 상태에서 다운스트림 스케줄링 및 할당 단계를 실행하여 얻은 총 코어 간 전송 비용입니다. 이를 통해 매핑이 모듈형 아키텍처의 통신 제약 조건에 맞춰 구체적으로 최적화될 수 있도록 합니다.

2. 파울리 스케줄링

매핑이 고정되면, 연속적인 가젯 사이의 서포트 변화를 최소화하도록 파울리 항들의 순서를 결정합니다. COSMA는 세 가지 전략을 평가합니다:

• 계수 크기 기반 순서(Magnitude Ordering): 계수의 크기에 따라 정렬합니다 (오류 감소를 위한 표준 방식).
• 사전식 순서(Lexicographic Ordering): 게이트 상쇄를 극대화하기 위해 알파벳 순으로 정렬합니다.
• 그레이 코드 기반 순서(Gray-Inspired Ordering): 서포트 마스크의 그레이 코드 변환을 기반으로 정렬합니다. 이는 연속된 항들이 유사한 서포트를 갖도록 하여, 연속적인 서포트 간의 해밍 거리를 최소화하고 결과적으로 큐비트 이동을 줄이는 것을 목표로 합니다.

3. 패리티 트리 합성 및 멀티 코어 할당

이 단계에서는 각 파울리 가젯에 대한 CNOT 패리티 트리를 합성하는 동시에 큐비트 배치를 결정합니다. 여기에는 **룩어헤드 휴리스틱(lookahead heuristic)**이 사용됩니다:

• 미배치 점수(Misplacement Score): 룩어헤드 윈도우 내의 미래 상호작용 파트너와의 거리를 기준으로 각 큐비트에 대한 점수를 계산합니다.
• 패리티 포레스트 구축: 현재 코어 할당을 기준으로 서포트 큐비트들을 그룹화하여 코어 내의 로컬 CNOT 체인을 형성합니다.
• 만남 코어(Meeting Core) 선택: 모든 서포트 큐비트와의 가중치 거리를 최소화하는 "만남 코어"를 식별하여 공간적 끌림점(spatial attractor) 역할을 하게 합니다.
• 전방 및 후방 병합(Forward and Backward Merge): 서로 다른 코어로부터의 불연절된 서브트리들을 하나의 패리티 트리로 반복적으로 병합합니다. 알고리즘은 미래의 상호작용 거리와 코어 용량 제약을 고려하여, 대표 큐비트를 이동시킬지 아니면 거주 중인 큐비트와 교체할지를 결정합니다. 이 과정을 통해 필요한 회로 슬라이스 시퀀스와 코어 간 전송이 생성됩니다.

3. 주요 기여

1. 최초의 공동 설계 연구: 저자들이 아는 바에 따르면, 이는 모듈형 아키텍처 상의 양자 시뮬레이션 커널을 위해 F2Q 매핑, 파울리 스케줄링, 큐비트 할당을 공동으로 최적화하는 최초의 연구입니다.
2. 매핑을 위한 유전 알고리즘: 고정된 인코딩(Jordan-Wigner 또는 Bravyi-Kitaev 등)을 넘어, 코어 간 통신 비용에 대해 삼항 트리 F2Q 매핑을 최적화하는 새로운 GA 접근 방식을 제공합니다.
3. 휴리스틱 합성 및 할당: 미래의 통신 압박을 최소화하기 위해 룩어헤드 윈도우를 활용하여 파울리 가젯 시퀀스에 맞춤화된 빠른 패리티 트리 합성 및 큐비트 할당 휴리스틱을 제공합니다.
4. 오픈 소스 프레임워크: 이러한 전략들을 평가할 수 있는 GPU 가속 기반의 오픈 소스 C++ 프레임워크(COSMA)를 제공합니다.

4. 실험 결과

프레임워크는 2D 그리드 멀티 코어 아키텍처를 사용하여 14개의 분자 워크로드(14개에서 90개의 페르미온 모드 범위)에 대해 평가되었습니다.

• 베이스라인 대비 성능: 최첨단 베이스라인(JW, BK, PE, JKMN과 같은 고정 매핑 및 Hungarian assignment, 표준 스케줄링 조합)과 비교했을 때, COSMA는 다음과 같은 성과를 거두었습니다:
  • 그레이 기반 스케줄링 사용 시 통신 비용 중앙값 1.7배 감소 (59.7% 감소).
  • 크기 기반 순서 사용 시 통신 비용 중앙값 1.4배 감소 (42.8% 감소).
  • 특정 워크로드에서는 통신 비용이 최대 2.5배 감소.
• 절제 연구(Ablation Studies):
  • 매핑의 영향: 고정된 스케줄링/할당 환경에서 매핑만을 최적화했을 때, 최적의 고정 매핑보다 중앙값 11.4%의 개선을 보였습니다. 다만, GA의 고정된 탐색 예산으로 인해 시스템 규모가 커질수록 이득은 감소했습니다.
  • 스케줄링의 영향: 그레이 기반 스케줄링은 크기 기반 순서(중앙값 46.0% 감소) 및 사전식 순서(중앙값 10.5% 감소)보다 크게 우수했으며, 이는 서포트 전이를 완만하게 만드는 것이 모듈형 시스템에서 매우 중요하다는 것을 확인시켜 줍니다.
• 실행 시간: 프레임워크는 CUDA 가속을 포함한 C++로 구현되었습니다. 합성 및 할당 단계가 병목 구간이지만, 모드 수에 따라 대략 4차(quartically)로 스케일링됩니다(파울리 항의 수에 의해 결정됨). 멀티스레딩과 CUDA는 단일 스레드 실행 대비 각각 5.0배 및 9.4배의 속도 향상을 제공했습니다.

5. 의의 및 주장

본 논문은 교차 계층 공동 설계가 멀티 코어 하드웨어 상에서 효율적이고 확장 가능한 양자 시뮬레이션을 위해 필수적이라고 주장합니다. 결과는 매핑, 스케줄링, 할당을 독립적으로 최적화하는 것이 최선이 아님을 보여줍니다. 왜냐로 이 단계들은 서로 밀접하게 결합되어 있어, 한 단계에서의 최적이 아닌 선택이 다른 단계들을 제약하기 때문입니다.

저자들은 통합된 프레임워크를 통해 코어 간 통신을 명시적으로 타겟팅함으로써, 모듈형 양자 컴퓨터의 실행 시간을 지배할 수 있는 통신 오버해드를 크게 줄일 수 있다고 주장합니다. 이러한 접근 방식은 모듈형 아키텍처의 주요 병목 현상을 완화함으로써 화학적으로 유의미한 문제를 향한 양자 시뮬레이션의 확장 경로를 제공합니다.

6. 한계 및 향 향후 과제

저자들은 몇 가지 한계점을 인정합니다:

• 비용 모델: 전송 비용 모델은 최단 경로 거리에 기반하며, 링크 용량, 혼잡도 또는 지연 시간의 비대칭성을 고려하지 않습니다.
• Trotter 오차: 본 프레임워크는 비가환(non-commuting) 항들의 재정렬로 인해 발생하는 Trotter 오차를 명시적으로 최적화하지 않고, 오직 통신에만 집중합니다.
• 매핑 패밀리: 현재 접근 방식은 PPTT 매핑(N 모드에서 N 큐비트로)으로 제한됩니다. LDPC 코드 등에 기반한 다른 스케일링 비율을 가진 매핑은 아직 탐구되지 않았습니다.
• 파이프라인 중첩: 본 목적 함수는 통신과 로컬 연산을 중첩할 가능성을 고려하지 않고 전송 횟수 자체를 최소화합니다.

향후 과제로는 하드웨어 비용 모델의 정교화, Trotter 오차와의 트레이드오프 포함, 더 표현력이 풍부한 진화 연산자 탐색, 그리고 다른 모듈형 토폴로지 및 변분 알고리즘(variational algorithms)으로의 확장이 포함됩니다.