SpiderLS: Leveraging Full ZX Reduction for Lattice Surgery Compilation

기술 요약: "SpiderLS: 격자 수술 컴파일을 위한 전체 ZX 축소 활용"

문제 정의

결함 허용 양자 컴퓨팅(FTQC)은 표면 코드(surface code)에 크게 의존하며, 여기서 논리적 연산은 파울리 곱 측정(PPM)을 통해 인코딩된 큐비트 패치들을 병합하고 분리하는 격자 수술(lattice surgery)을 통해 구현됩니다. 이 패러다임의 핵심적인 병목 현상은 논리 회로를 효율적인 격자 수술 실현 모델로 컴파일하여 시공간 비용(공간 면적과 시간 단계의 곱)을 최소화하는 것입니다.

최근의 접근 방식들은 의미론적 보존 변환을 가능하게 하기 위해 ZX-계산법(ZX-calculus)을 중간 표현(IR)으로 활용해 왔습니다. 그러나 TopoLS와 같은 기존의 ZX 기반 컴파일러들은 ZX 스파이더(spider)와 격자 수술 정션(junction) 사이의 일대일 대응 관계를 유지하기 위해 ZX 축소를 제한합니다. 논리 패치의 평면 기하 구조로 인해, 단일 정션은 최대 4개의 연결(2개의 공간적, 2개의 시간적 연결)만을 지원할 수 있습니다. 결과적으로, 이러한 컴파일러들은 하부의 격자 수술 모델이 다중 패치 측정을 통해 고차수(higher-arity) 상호작용을 지원함에도 불구하고, 만약 축소 결과가 차수가 4보다 큰 스파이더를 생성할 경우 "전체(full)" ZX 축소를 수행할 수 없습니다. 이러한 제한은 컴파일러가 ZX-계산법의 전체 최적화 잠재력을 활용하는 것을 방해하며, 복잡한 임베딩 탐색으로 인한 높은 컴파일 오버헤드와 하위 최적의 시공간 부피를 초래합니다.

방법론

저자들은 ZX 스파이더 표현을 물리적 정션 제약으로부터 분리함으로써 차수-4 제약을 극복하는 격자 수술 컴파일러인 SpiderLS를 제안합니다. 컴파일 파이프라인은 다음 네 가지 주요 단계로 진행됩니다:

1. 전체 ZX 축소 및 실행 순서 결정:
   SpiderLS는 입력된 Clifford+T 회로를 ZX-다이어그램으로 변환하고 PyZX의 full_reduce() 루틴을 적용합니다. 이전 연구와 달리, 이 과정은 4-에지 정션 제한에 의해 제한되지 않으므로 고차수 스파이더 생성을 허용합니다. 컴파일러는 축소된 그래프로부터 직접 실행 순서를 도출합니다. 이는 활성 "프런티어(frontier)" 스파이더 집합을 유지하면서, 실행 가능한 상호작용(CZ 연산)과 Hadamard 이동을 반복적으로 추출하여 축소된 그래프를 일련의 연산으로 효과적으로 선형화합니다.

2. 대상 코드 생성:
   실행 순서는 대상 프로그램으로 그룹화됩니다. SpiderLS는 공통 제어 큐비트를 공유하는 여러 CZ 게이트가 단일 다중 타겟 연산(예: $CZ^{(k)}(q_c; q_1, \dots, q_k)$)으로 결합될 수 있다는 관찰을 활용합니다. 위상 연산(S 및 T 게이트)은 스파이더 위상으로부터 추출되며, T 게이트는 매직 상태 주입을 통해 처리됩니다. 이 단계는 다중 타겟 CZ, 단일 큐비트 게이트, 그리고 Hadamard로 구성된 압축된 대상 프로그램을 생성합니다.

3. PPM 하향 변환(Lowering) 및 논리적 스케줄링:
   대상 프로그램은 단위 시간 PPM 시퀀스로 하향 변환됩니다. 결정적으로, 고차수 CZ 연산은 다중 패치 측정(예: 3-타겟 CZ는 4-패치 $M_{ZZZX}$ 측정과 표준 $M_{ZZ}$ 측정으로 분해됨)으로 분해됩니다. 컴파일러는 그 후 논리적 스케줄링을 수행하여 이러한 PPM들을 논리적 레이어에 패킹합니다. 이는 무제한 안실라(ancilla) 스케줄의 깊이를 보존하면서 필요한 내부 안실라 큐비트 수를 최소화하는 전략을 채택합니다.

4. 계층적 시공간 라우팅:
   레이어별로 전역 임베딩 문제를 해결하기 위해 몬테카를로 트리 탐색(MCTS)을 사용하는 대신(TopoLS의 방식), SpiderLS는 **구조 인식 로컬 라우팅(structure-aware local routing)*을 수행합니다. 논리적 스케줄이 고정되면, 컴파일러는 호환 가능한 파울리 경계를 선택하고 A 탐색을 사용하여 경로를 구축함으로써 각 PPM을 라우팅합니다. 유효한 경로를 제한된 로컬 탐색 내에서 찾을 수 없는 경우, 해당 연산은 이후의 물리적 레이어로 연기됩니다. 이 "확정 또는 연기(commit-or-defer)" 전략은 전역 레이어 임베딩의 지수적 탐색 공간을 피함으로써 컴파일 시간을 대폭 단축합니다.

주요 기여

• 격자 수술을 위한 전체 ZX 축소: 본 논문은 ZX 스파이더가 반드시 제한된 차수의 정션과 일대일 매핑될 필요가 없음을 입증합니다. 다중 패치 측정을 활용함으로써, SpiderLS는 전체 ZX 축소를 허용하여 기존에 정션 제약을 만족시키기 위해 파편화되었던 상호작용들을 통합할 수 있게 합니다.
• 다중 타겟 연산 그룹화: 컴파일러는 공유 제어 상호작용을 식별하고 이를 단일 다중 타겟 연산으로 그룹화하여, 총 논리 연산 수를 줄이고 더 효율적인 시공간 패킹을 가능하게 합니다.
• 구조 인식 라우팅: 논리적 스케줄링과 기하학적 라우팅을 분리하고, 전역 MCTS 대신 제한된 로컬 탐색을 사용함으로써, SpiderLS는 컴파일 복잡성을 획기적으로 감소시킵니다.
• 구현 및 평가: 저자들은 SpiderLS의 전체 구현을 제공하며, 이를 최신 컴파일러들(Liblsqecc, DASCOT, TopoLS)과 비교 평가합니다.

결과

다양한 알고리즘(예: Bernstein-Vazirani, QAOA, QFT) 및 무작위 Clifford+T 회로에 대해 평가한 결과:

• 시공간 부피: SpiderLS는 TopoLS 대비 시공간 부피에서 평균 **49.2%**의 감소를 달 achieves 했습니다. 이 감소는 주로 상호작용의 그룹화와 다중 패치 측정을 통해 달성된 시간 단계 수의 감소에 기인합니다.
• 컴파일 시간: SpiderLS는 TopoLS 대비 컴파일 시간을 99.8% 단축했습니다. MCTS 기반 임베딩에서 제한된 로컬 라우팅으로의 전환은 기존 ZX 기반 컴파일러의 주요 병목 현상을 제거했습니다.
• 확장성: SpiderLS는 회로 기반 컴파일러(Liblsqecc, DASCOT)와 유사한 낮은 컴파일 오버헤를 유지하면서도, 시공간 효율성 측면에서는 이들을 능가합니다. 문제 규모가 커짐에 따라 일관된 부피 감소를 보이며 회로 폭에 따라 효과적으로 확장됩니다.
• 매직 상태 요구량: 시간적 깊이를 압축함에도 불구하고, SpiderLS는 TopoLS와 비슷하거나 더 낮은 T-포트 밀도를 유지하여, 시간적 압축이 매직 상태 요구량을 관리 불가능한 수준으로 집중시키지 않음을 보여줍니다.

의의

본 논문은 격자 수술 컴파일을 위해 ZX-계산법의 전체 표현력을 활용하는 것의 실질적인 이점을 SpiderLS가 입증한다고 주장합니다. ZX 스파이더가 물리적 정션에 직접 매핑되어야 한다는 인위적인 제약을 완화함으로써, 컴파일러는 더 압축된 시공간 실현체를 생성할 수 있습니다. 이 연구는 이전에 매핑하기 어렵다고 여겨졌던 고차수 상호작용이 다중 패치 측정을 통해 효율적으로 실현될 수 있음을 확립합니다. 또한, 제안된 구조 인식 라우팅 방식은 전역 임베딩 탐색의 과도한 계산 비용 없이도 고품질의 격자 수술 컴파일이 가능하다는 것을 증명하며, 이를 통해 효율적인 컴파일을 대규모 양자 프로그램에 대해서도 가능하게 만듭니다.