Numerical Evaluation of ZX Calculus Optimization for Solovay Kitaev Quantum Circuit Synthesis

기술 요약: Solovay–Kitaev 양자 회로 합성을 위한 ZX-Calculus 최적화의 수치적 평가

문제 정의
결함 허용 양자 컴퓨팅(fault-tolerant quantum computing)에서 논리 연산의 물리적 비용은 값비싼 매직 상태 증류(magic-state distillation)를 요구하는 비-클리포드(non-Clifford) T 게이트 구현에 의해 지배됩니다. 결과적으로, 합성된 회로의 T-count는 컴파일 효율성을 결정하는 주요 엔지니어링 지표가 됩니다. Solovay–Kitaev 정리는 유한한 게이트 집합(특히 Clifford+T)으로부터 임의의 단일 큐비트 유니터리를 근사하기 위한 일반적인 재귀적 방법을 제공하며, 이때 시퀀스 길이는 목표 오차의 역수에 대해 다항 로그(polylogarithmically) 단위로 성장합니다. 그러나 이 알고리즘은 수치적 수렴보다는 회로의 경제성을 최적화합니다. 중첩된 군 교환자(group commutators)에 기반한 이 알고리즘의 재귀적 구조는 상당한 구조적 중복성을 도입합니다. 즉, 전체를 보았을 때는 상쇄되지만 선형 시퀀스 내에는 그대로 남아 있는 게이트들이 존재합니다. 그래프로서 회로를 다루어 선형 목록이 아닌 방식으로 중복성을 식별하고 제거하는 ZX-calculus 기반의 다이어그램 최적화가 이러한 기법을 제공하지만, Solovay–Kitaev 출력물에 대한 이 접근 방식의 구체적인 효용성은 실증적 연구가 거의 이루어지지 않았습니다. 본 논문은 다음과 같은 질문을 다룹니다: 일반적인 재귀적 군 교환자 구성이 얼마나 많은 회복 가능한 구조적 중복성을 남겨두며, 자동화된 ZX rewriting은 이를 얼마나 회복할 수 있는가?

방법론
본 연구는 Solovay–Kitaev로 합성된 회로에 대한 ZX-calculus 후처리(post-processing)의 영향을 측정하기 위해 4단계 파이프라인을 채택합니다:

1. 합성(Synthesis): 네 가지 계열(Pauli 회전 $R_x, R_y, R_z$ 및 일반 유니터리 $U(\theta, \phi, \lambda)$)에 걸쳐 1,200개의 무작위 단일 큐비트 타겟을 생성했습니다. 이들은 세 가지 재귀 깊이($d=2, 3, 4$)에 대해 $\{H, S, S^\dagger, T, T^\dagger, Z\}$ 게이트 집합을 사용하는 Qiskit Solovay–Kitaev 트랜스파일러를 통해 합성되었습니다.
2. 매핑(Mapping): 생성된 게이트 문자열을 QASM으로 내보내고, 이를 ZX-다이어그램으로 파싱한 뒤, 클리포드 및 비-클리포드 게이트가 스파이더(spider)와 에지(edge)로 표현되는 "그래프 유사(graph-like)" 형태로 변환했습니다.
3. 단순화(Simplification): 변환된 다이어그램은 PyZX(v0.10.5)의 full_reduce 전략을 사용하여 단순화되었습니다. 이는 구현된 선형 맵을 전역 스칼라까지 보존하는 건전한 rewrite 규칙(스파이더 퓨전, 항등식 제거, 로컬 컴플리멘테이션, 피보팅)을 적용합니다.
4. 추출 및 측정(Extraction and Measurement): 단순화된 다이어그램을 다시 회로로 추출했습니다. 본 연구에서는 최적화 전후의 총 게이트 수, T-count, 그리고 실행 시간(wall-clock time)을 측정했습니다. rewrite 규칙은 의미론적으로 보존(semantics-preserving)되므로, 추적 오차 노름(trace error norm)이 변하지 않음을 확인하여 정확도를 검증했습니다.

주요 기여 및 결과
본 논문은 새로운 합성 방법을 제안하기보다, Solovay–Kitaev 합성와 ZX-calculus 최적화 사이의 결합(composition)을 정량적으로 측정하는 데 초점을 맞춥니다. 주요 결과는 다음과 같습니다:

• 게이트 감소(Gate Reduction): 후처리를 통해 총 게이트 수의 26.6%에서 30.1%, T-count의 **18.5%에서 22.2%**를 제거했습니다.
• 재귀 깊이에 따른 분율적 절감의 독립성(Depth Independence of Fractional Savings): 핵심적인 발견은 분율적 감소량이 재귀 깊이에 관계없이 거의 일정하게 유지된다는 점입니다. $d=2$에서 $d=4$로 갈수록 절대적인 회로 길이는 25배 증가하지만, rewriting에 의해 제거되는 게이트의 비율은 평탄하게 유지됩니다(가장 얕은 설정에서 약간 상승한 후 안정화됨). 이는 중복성이 중첩 깊이와 함께 누적되는 것이 아니라, 베이스 워드(base words)의 접점에서 국부적으로 생성되는 고정된 몫임을 시사합니다.
• 타겟 계열 독립성(Target Family Independence): 감소 비율은 네 가지 타겟 계열 전반에 걸쳐 일관되게 나타납니다. 가장 깊은 재귀 수준($d=4$)에서 네 가지 계열은 통계적으로 구분이 불가능하며, 개별 타겟 간의 분산 또한 크게 감소합니다. 이는 회복 가능한 중복성이 특정 타겟 유니터리의 속성이 아니라 Solovay–Kitaev 구성 자체의 속성임을 나타냅니다.
• 절대적 절감 vs 분율적 절감(Absolute vs. Fractional Savings): 백분율 절감량은 일정하지만, 절대적 절감량은 회로 크기에 따라 증가하여 $d=2$일 때 약 60개에서 $d=4$일 때 약 1,600개 게이트에 달합니다.
• 컴파일 시간 비용(Compile-Time Cost): 리라이팅 레이어의 비용은 회로 깊이에 따라 초선형(superlinearly)으로 증가합니다. 얕은 깊이에서는 리라이팅 비용이 합성 단계에 비해 무시할 수 있는 수준이지만, $d=4$에서는 리라이 de layer가 전체 파이프라인 시간의 99% 이상을 차지하며 합성 단계 자체를 압도합니다.
• 정확도 보존(Accuracy Preservation): 최적화는 정확도 손실을 초래하지 않습니다. 추출된 회로는 합성된 회로와 동일한 선형 맵을 구현함을 확인하였으며, 편차는 부동 소수점 누적($< 5.8 \times 10^{-13}$)에 국한되었습니다.

의의 및 주장
본 논문은 자신의 기여를 다이어그램적 관점에서 바라본 Solovay–Kitaev 알고리즘의 "회복 가능한 구조적 중복성"을 측정하는 것으로 겸손하게 규정합니다. 저자들은 Solovay–Kitaev가 (z-회전을 위해 수론적 방법을 사용하는 일반적인 프로덕션 컴파일러와 경쟁할 만한) 경쟁력 있는 합성 경로가 아님을 명시적으로 밝히며, 따라서 보고된 T-count 역시 최첨단 근사 합성법과 경쟁적이지 않음을 인정합니다.

본 연구의 의의는 다이어그램적 최적화를 재귀적 합성 출력물에 사용할 때의 트레이드오프를 규명하는 데 있습니다:

1. 예측 가능성: 분율적 절감은 타겟이나 깊이에 독립적인, 구성의 안정적인 속성입니다.
2. 트레이드오프: 이 혜택은 "공짜"가 아닙니다. 이 결합 모델은 특정 작동 범위를 가집니다. 절대적인 게이트 절감량은 깊은 회로에서 상당하지만, 이를 얻기 위한 컴파일 시간 비용이 높은 재귀 깊이에서는 지배적인 요소가 됩니다.
3. 메커니즘: 이 감소는 선형 게이트 목록 내의 기저 변화(basis changes)에 의해 분리된 페이즈 노드(phase nodes)를 병합할 수 있는 ZX-calculus의 능력에 의해 주도됩니다.

저자들은 이 결합 방식이 균일한 게이트 수 감소를 제공하지만, 특히 급격한 컴파일 시간 증가를 고려할 때, 보편적인 개선이라기보다는 특정 작동 범위를 가진 트레이드오프로 간주되어야 한다고 결론짓습니다. 향-비다이어그램적 최적화 도구와의 비교 및 다중 큐비트 환경에 대한 연구를 향후 과제로 제시하였습니다.