무작위 추상화(Random Abstraction)를 통한 선형 시간 T-Gate 최적화

요약

본 논문은 양자 컴퓨팅의 결함 허용 구현 시 병목 현상이 되는 T-게이트 개수를 최적화하기 위한 새로운 방법을 제안합니다. 무작위 정적 분석을 기반으로 한 선형 시간 무작위 알고리즘을 통해 위상 폴딩(Phase folding)을 수행하며, 이를 구현한 TZAP는 기존 도구들보다 훨씬 빠른 속도로 대규모 회로를 최적화할 수 있습니다.

핵심 포인트

• T-게이트 개수 최소화는 양자 우위 달성을 위한 핵심적인 자원 최적화 과제임
• 기호 표현식 대신 일정한 너비의 비트 문자열을 전파하는 새로운 무작위 정적 분석 방식 도입
• 위상 폴딩을 위한 선형 시간 무작위 알고리즘을 통해 이론적 효율성 확보
• 구현체 TZAP는 기존 PyZX, VOQC 등과 비교해 수 배 빠른 속도로 수백만 개의 게이트 최적화 가능