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

양자 컴퓨터(Quantum computers)는 암호학, 화학, 최적화 분야의 문제들에 대해 지수적인 속도 향상을 약속합니다. 이러한 약속을 실현하기 위해서는 결함 허용(Fault tolerance)이 필요합니다. 물리적 큐비트(Physical qubits)는 노이즈가 발생하므로, 양자 오류 수정 코드(Quantum error-correcting codes)를 사용하여 여러 물리적 큐비트에 걸쳐 논리적 큐비트(Logical qubits)를 중복하여 인코딩해야 합니다. 대부분의 실질적인 결함 허용 방식에서 T 게이트(T gates)는 가로지르기 방식(Transversally)으로 구현될 수 없으며, 대신 복잡한 연산 세트를 포함하는 비용이 많이 드는 매직 상태 증류(Magic-state distillation) 프로토콜을 필요로 합니다. 결과적으로, T-게이트 개수(T-gate count)는 대규모 양자 계산의 자원 예산을 지배할 수 있으며, 이는 T-개수(T-count) 최소화가 양자 우위(Quantum advantage)로 가는 길의 핵심적인 병목 현상이 되게 합니다. 그러나 기존의 T-개수 최적화 도구들은 양자 우위가 요구하는 회로 규모로 확장되지 못합니다. 본 논문에서는 T-게이트 최적화에 관한 이론적 및 실무적 결과를 제시합니다. 이론적인 측면에서는, 새로운 무작위 정적 분석(Randomized static analysis)에 기반하여 위상 폴딩(Phase folding)을 위한 선형 시간 무작위 알고리즘(Linear-time randomized algorithm)을 제공합니다. 우리의 정적 분석은 임의로 높은 확률로 도달 가능한 양자 상태(Reachable quantum states) 집합을 건전하게(Soundly) 근사합니다. 우리의 핵심 통찰은 기호 표현식(Symbolic expressions)을 추적하는 대신, 회로를 따라 일정한 너비의 비트 문자열(Bitstrings)을 전파하는 정적 분석입니다. 실무적인 측면에서, 우리의 구현체인 TZAP는 PyZX, VOQC, Feynman과 같은 최첨단 도구들보다 수 차례 더 빠르며, 표준 벤치마크에서 이들의 T-개수 감소량과 밀접하게 일치하고, 노트북 컴퓨터에서 단 몇 초 만에 수백만 개의 게이트를 가진 회로를 최적화할 수 있습니다.