기술 요약: 양자 회로 사전 합성 (Q-PreSyn)

문제 정의

결함 허용 양자 컴퓨팅(FTQC)은 유니터리 연산을 이산적인 게이트 집합(일반적으로 Clifford+T)의 시퀀스로 분해하는 것에 의존합니다. 이 체제에서 T-count(T 게이트의 수)는 T 게이트가 값비싼 매직 상태 주입(magic state injection)이나 합성 절차를 필요로 하기 때문에 지배적인 비용 지표가 됩니다.

전역 합성(전체 $n$-큐비트 유니터리를 직접 분해하는 것)은 대규모 시스템에 대해 지수적 스케일링으로 인해 계산적으로 다루기 힘들지만, 실용적인 컴파일러는 **지역 합성(local synthesis)**에 의존합니다. 이 접근 방식은 회로를 더 작은 서브회로(예: 1 또는 2개의 큐비트에 작용하는 회로)로 분해하고, 이를 독립적으로 합성한 다음 다시 결합합니다. 그러나 결정적인 한계가 존재합니다: 최종 분해의 품질은 실제 합성 전의 회로 표현(즉, 유니터리가 로컬 게이트로 어떻게 인수분해되는지)에 매우 민감합니다.

동등한 회로 표현이라 하더라도 매우 다른 T-count를 생성할 수 있습니다. 예를 들어, 두 개의 연속적인 단일 큐비트 회전 $R_z(\alpha_1)$와 $R_z(\alpha_2)$를 독립적으로 합성하면, 이들을 결합된 회전 $R_z(\alpha_1 + \alpha_2)$로 직접 합성하는 것보다 T-count가 두 배로 늘어나는 경우가 많습니다. 현재의 컴파일러들은 이러한 최적의 표현을 식별하지 못하는 경우가 많으며, 이는 결과적으로 차선의 T-count로 이어집니다. 핵심 질문은 다음과 같습니다: 주어진 양자 회로와 로컬 합성 알고리즘이 있을 때, 더 효율적인 합성을 가능하게 하는 회로 표현을 결정할 수 있는가?

방법론: Q-PreSyn

저자들은 실제 합성 단계 이전에 회로 표현을 최적화하는 사전 합성 프레임워크인 Q-PreSyn을 제안합니다. 이 방법은 최적의 표현을 찾는 과정을 강화 학습(RL)을 통해 해결되는 계획(planning) 문제로 취급합니다.

1. 행동 공간: 유니터리 보존 병합 (Unitary-Preserving Merges)

이 프레임워크는 회로가 구현하는 전역 유니터리는 유지하면서 로컬 구조를 변경하는 "병합(merge)" 연산을 적용하여 작동합니다.

• 단일 큐비트 병합: 단일 큐비트 $i$에 대해서만 작용하는 연속적인 유니터리들은 그 곱 $W = U_{n_k} \dots U_{n_1}$로 대체됩니다.
• 2-큐비트 병합: 큐비트 쌍 $(i, j)$에 대해서만 작용하는 연속적인 유니터리들은 그 곱으로 대체됩니다.
• 제약 조건: 저자들은 병합을 1 또는 2-큐비트로 제한합니다. $K$-큐비트 병합도 이론적으로는 가능하지만, 탐색 공간이 조합론적으로 증가하며($\binom{n}{k}$), 더 큰 서브회로를 합성하는 것은 지수적으로 더 어렵습니다.

2. 순차적 결정 문제로서의 계획 (Planning)

병합의 시퀀스는 하나의 계획 $\pi = (a_1, a_2, \dots, a_m)$으로 정의됩니다. 연산의 순서가 중요합니다. 병합을 적용하는 순서에 따라 매우 다른 최종 표현이 나올 수 있습니다 (예: 서로 상쇄되는 게이트를 병합하는 것 vs. 복잡한 얽힘을 생성하는 게이트를 병합하는 것).
목표는 블랙박스 로컬 알고리즘 $A$에 의해 합성된 후의 회로 T-count인 비용 함수 $L$을 최소화하는 계획 $\pi^*$를 찾는 것입니다:
$$\pi^* = \arg \min_{\pi \in \Pi} L(A(C_\pi))$$

3. 탐색 전략

거대한 조합론적 공간을 탐색하기 위해 저자들은 두 가지 전략을 평가합니다:

• 탐욕적 탐색 (Greedy Search): 즉각적으로 가장 큰 T-count 감소를 가져오는 병합 동작을 반복적으로 선택합니다. 이는 베이스라인 역할을 하지만, 근시안적인 성격 때문에 전역 최적해를 놓칠 수 있습니다.
• 강화 학습 (Reinforcement Learning, RL): 계획 구축은 순차적 결정 과정으로 모델링됩니다.
  • 에이전트: PPO(Proximal Policy Optimization)를 사용하여 구현되었습니다.
  • 상태 (State): T-게이트 수, 잠재적 병합 가능 게이트, 병합 이력을 나타내는 이진 행렬을 인코딩하는 3채널 텐서($n \times n \times 3$)입니다.
  • 보상 (Reward): 합성 시 발생하는 즉각적인 T-count 감소량입니다.
  • 정교화 (Refinement): RL의 확률성을 완화하기 위해, RL 에이전트가 생성한 계획은 그리디 완성 전략(RL 계획의 모든 접두사에 대해 그리디 확장을 평가)을 사용하여 더욱 정교하게 다듬어집니다.

4. 구현 세부 사항

• 메모이제이션 (Memoization): 계산 오버헤드를 줄이기 위해, 시스템은 탐색 중에 발견되는 유니터리 블록의 합성된 분해본을 캐싱합니다.
• 합성 알고리즘: 이 프레임워크는 합성 방식에 구애받지 않습니다(synthesis-agnostic). 실험에는 KAK, BQSKit과 같은 분해 도구와 Solovay-Kitaev, Gridsynth와 같은 합성 알고리즘의 조합이 사용되었습니다.

주요 기여

1. Q-PreSyn 프레임워크: 실제 합성 알고리즘 자체와는 구별되는, 양자 회로의 표현 수준 최적화를 위한 새로운 접근 방식입니다. 이는 다운스트림 합성 효율을 높이기 위해 유니터리 보존 병합을 통해 회로 구조를 수정합니다.
2. 계획 최적화의 공식화: 유리한 병합 시퀀스를 식별하는 문제를 계획 최적화 작업으로 공식화했습니다. 저자들은 RL이 이 공간을 효과적으로 탐색하여 그리디 전략이 놓치는 장기적 의존성을 찾아낼 수 있음을 입증했습니다.
3. 보편적 전처리: 이 방법은 모든 로컬 합성 파이프라인(예: Gridsynth, Solovay-Kitaev, matchgate synthesis)과 호환되는 보편적인 전처리 단계로 설계되었습니다.
4. 오픈 소스: 저자들은 이 방법과 실험을 재현하는 데 필요한 모든 코드를 제공합니다.

실험 결과

저자들은 무작위 회로, 선형 연결성 회로, 양자 이징 모델(Quantum Ising model)의 실시간 역학, 그리고 매치게이트(matchgate) 회로를 포함한 다양한 작업에 대해 Q-PreSyn을 평가했습니다.

• T-count 감소: 다양한 합성 프레임워크와 회로 유형에 걸쳐, Q-PreSyn은 10%에서 25% 사이의 T-count 감소를 달ей했습니다.
  • 무작위 회로: Gridsynth+BQSKit의 경우 최대 20% 감소, KAK 기반 방식의 경우 10~18% 감소를 기록했습니다.
  • 확장성: 이 방법은 최대 25 큐비트의 회로까지 테스트되었습니다. RL 에이전트는 더 작은 회로에서 그리디 에이전트보다 더 나은 감소를 제공했지만, 더 큰 규모(25 큐비트)에서는 그리디 에이전트가 여전히 효과적이며 계산 비용이 더 저렴했습니다.
• 근사 오차 (Approximation Error): 사전 합성 과정은 추가적인 근사 오차를 도입하지 않습니다. 오히려, 합성 단계를 줄임으로써(합성 전 게이트를 병합함으로써), 직접 합성하는 것보다 총 누적 근사 오차가 감소하는 경우가 많습니다.
• 전략 비교: RL 기반 전략은 특히 더 큰 감소를 이끌어내는 긴 병합 시퀀스를 가진 계획을 찾는 데 있어 그리디 베이스라인보다 일반적으로 우수한 성능을 보였습니다. 그러나 RL 에이전트를 훈련하는 데 드는 계산 비용(수 시간)은 그리디 탐색(수 분)보다 현저히 높습니다.

의의 및 한계

본 논문은 Q-PreSyn을 결함 허용 구현의 비용을 낮추기 위한, 합성 알고리즘을 변경하지 않고도 적용 가능한 실용적이고 합성 불가지론적인(synthesis-agnostic) 기술로 포지셔닝합니다. 회로 표현을 최적화 가능한 객체로 다룸으로써, 이 연구는 고수준 알고리즘 기술과 저수준 하드웨어 제약 사이의 간극을 메웁니다.

저자들이 언급한 한계 및 향후 방향:

• 탐색 공간 복잡도: 2개 이상의 큐비트에서 병합을 탐색하면 추가적인 절감이 가능할 수 있으나, 현재는 지수적으로 증가하는 탐색 공간과 합성의 어려움으로 인해 제한됩니다.
• RL의 확장성: 매우 큰 회로를 위해 RL 에이전트를 훈련하는 것은 여전히 많은 계산량을 요구합니다. 저자들은 확장성을 개선하기 위해 (몬테카를로 트리 탐색이나 커리큘럼 학습과 결합된) 하이브리드 전략을 제안합니다.
• 토폴로지 및 벤치마크: 향후 연구에서는 더 넓은 비교와 엔드 투 엔드 컴파일러 배포를 용이하게 하기 위해 토폴로지 인식 및 표준화된 벤치마크 제품군을 통합해야 합니다.

요약하자면, 저자들은 학습 유도형 구조적 변환이 비네이티브 게이트 비용을 줄이기 위한 실행 가능하고 효과적인 방법임을 주장하며, 이를 통해 기존의 표준 컴파일 파이프라인보다 유의미한 개선을 제공한다고 밝히고 있습니다.