Quantum Circuit Synthesis Using an Exact T Library

본 논문은 클리포드 동치 하에서 불 함수를 표준화하고 사전 계산된 최적 구현을 활용하여 내결함성 양자 회로의 T 게이트 수를 크게 줄이는 정확한 T 합성 방법을 제시하며, 이는 암호 모듈에서 기존 AND 최소화 접근법보다 최대 40%까지 우수한 성능을 보입니다.

핵심

복잡한 기계를 두 가지 유형의 벽돌, 즉 표준 벽돌(클리포드 게이트)과 골드 벽돌(T 게이트)을 사용하여 구축하려고 상상해 보세요.

고장 허용 양자 컴퓨팅 세계에서 표준 벽돌은 저렴하고 사용하기 쉬우며 에너지 비용이 거의 들지 않습니다. 반면 골드 벽돌은 엄청나게 비쌉니다. 단 하나의 골드 벽돌을 생산하기 위해서도 거대하고 복잡한 공장이 필요합니다. 신뢰성 있게 작동하는 양자 컴퓨터를 구축하려면 가능한 한 적은 수의 골드 벽돌을 사용해야 합니다.

구식 방법: 잘못된 것을 세는 것

오랫동안 이러한 양자 회로를 설계하려는 엔지니어들은 단계를 생략했습니다. 그들은 설계도를 보고 "AND" 연산(특정 유형의 논리 단계)의 수를 세었습니다. 그들은 모든 "AND" 연산이 자동으로 일정한 수의 골드 벽돌을 필요로 한다고 가정했습니다.

유추:
당신이 여행 가방을 꾸린다고 상상해 보세요. 구식 방법은 셔츠를 하나씩 쌀 때마다 정확히 10 인치의 공간을 차지한다고 가정했습니다. 따라서 그들은 공간을 절약하기 위해 셔츠의 수를 최소화하려고 했습니다.

하지만 여기에 문제가 있습니다. 어떤 셔츠는 얇고 접히지만, 다른 셔츠는 부피가 크고 뻣뻣합니다. 때로는 두 가지 특정 셔츠를 함께 싸면 예상보다 훨씬 작은 공간으로 압축되기도 합니다. 구식 방법은 이러한 "접기"를 고려하지 않았습니다. 그들은 단순히 셔츠의 수만 세었을 뿐입니다. 그 결과, 그들은 골드 벽돌을 함께 "접을" 기회를 놓쳤기 때문에 종종 필요한 것보다 훨씬 더 큰 여행 가방을 갖게 되었습니다.

새로운 방법: "정확한 T" 라이브러리

이 논문의 저자인 한유 왕과 그의 팀은 추측을 멈추기로 결정했습니다. "AND" 연산을 세는 대신, 그들은 골드 벽돌 라이브러리를 구축했습니다.

1. 라이브러리: 그들은 가능한 모든 작은 논리 함수를 구축하는 데 필요한 절대적이고 가장 효율적인 방법을, 골드 벽돌의 최소 개수를 정확히 사용하여 사전 계산했습니다. 이는 최대 7 개의 입력을 가진 함수에 대해 수행되었습니다. 이는 "이 특정 모양을 구축해야 한다면, 골드 벽돌을 사용하여 이를 수행하는 정확하고 가장 저렴한 방법이 여기 있습니다"라고 말하는 카탈로그를 가지고 있는 것과 같습니다.
2. "접기" 트릭: 그들은 양자 회로에서는 때때로 골드 벽돌을 "상쇄"하거나, 종이 위에서는 다르게 보이지만 양자 세계에서는 실제로 동일한 방식으로 결합할 수 있음을 깨달았습니다. 그들은 이러한 숨겨진 단축경을 찾기 위해 "클리포드 동치성"이라는 수학적 개념을 사용했습니다. 이는 서로 다른 모양의 셔츠 접기 기술이 실제로는 정확히 동일한 컴팩트한 묶음으로 이어진다는 것을 깨닫는 것과 같습니다.
3. 맞춤형 매핑기: 그들은 단순히 라이브러리를 사용한 것이 아니라, 새로운 "패커"(매핑 알고리즘) 를 구축했습니다. 이 패커는 설계도를 보고 라이브러리와 일치하는 특정 모양을 찾아 "접기" 트릭을 사용하여 공간을 절약할 정도로 똑똑합니다. 이는 "AND" 게이트를 맹목적으로 세는 구식 실수를 피합니다.

결과

그들이 이 새로운 시스템을 표준 수학 문제와 복잡한 암호화 작업 (암호화에 사용되는 것과 같은) 에 테스트했을 때:

• 표준 수학 벤치마크에서: 필요한 골드 벽돌의 수를 최대 **14.3%**까지 줄였습니다.
• 암호화 모듈에서: 골드 벽돌 수를 최대 **40%**까지 줄였습니다.

이것이 중요한 이유

이 논문은 "대략적인 추정"(AND 연산 세기) 에서 "정확한 계산"(라이브러리 사용) 으로 전환함으로써 훨씬 더 효율적인 양자 회로를 구축할 수 있음을 설명합니다.

또한 그들은 새로운 방법이 계획하는 데 아주 조금 더 많은 시간이 걸린다는 점 (설계 단계 동안 컴퓨터 시간이 약 11% 더 소요됨) 을 지적했지만, 그 보상은 엄청납니다. 최종 기계는 훨씬 적은 수의 비싼 골드 벽돌을 사용한다는 것입니다. 이러한 설계는 종종 다양한 실험에서 여러 번 재사용되므로, 작은 계획 시간은 실제 구축 비용의 막대한 절감에 가치가 있습니다.

간단히 말해: 그들은 얼마나 많은 비싼 벽돌이 필요한지 추측하는 것을 멈추고, 훨씬 더 날렵하고 효율적인 양자 회로를 구축하기 위해 정밀하고 사전 계산된 카탈로그를 사용하기 시작했습니다.

기술 요약

기술 요약: 정밀 T 라이브러리를 활용한 양자 회로 합성

문제 제기
고장 허용 양자 컴퓨팅 (FTQC) 에서 비-클리포드 게이트, 특히 T 게이트의 실행은 마법 상태 증류 및 주입의 오버헤드로 인해 시공간 비용을 지배합니다. 클리포드 게이트는 무시할 수 있는 오버헤드로 횡단적으로 실행될 수 있지만, T 게이트는 비용이 많이 드는 상태 양육을 필요로 합니다. 따라서 실용적인 응용을 위해 T 게이트 수 (T count) 를 최소화하는 것이 중요합니다.

기존 합성 흐름은 일반적으로 부울 함수를 $\{XOR, AND, NOT\}$ 기저 (XAG) 에 매핑하고 T 게이트 수의 대리 지표로 AND 게이트 수를 최소화합니다. 이 접근법은 고전적 비선형성을 측정하는 곱셈 복잡도 (Multiplicative Complexity, MC) 에 의존합니다. 그러나 본 논문은 MC 가 위상 상쇄와 양자 회로 고유의 구조적 단순화 (예: T 최적화를 차단하는 Hadamard 게이트) 를 고려하지 못하기 때문에 양자 T 비용에 대한 부정확한 대리 지표라고 주장합니다. 그 결과, 기존 흐름은 종종 구조적 기회를 놓친 비최적 회로를 생성하며, 이러한 기회는 매핑 후 최적화로는 복구할 수 없습니다.

방법론
저자들은 MC 를 대리 지표로 사용하는 대신 정밀 T 게이트 수를 직접 최적화하는 합성 프레임워크를 제안합니다. 방법론은 세 가지 주요 구성 요소로 이루어집니다:

1. 클리포드 동등성 기반 표준화 (Clifford-Equivalent Canonicalization):
   논문은 클리포드 동등성 하에서 이차 형식 함수 (bilinear functions) 를 위한 표준형을 도입합니다. 입력 - 출력 결합을 나타내기 위해 곱셈 텐서를 사용하는 고전적 MC 와 달리, 저자들은 **위상 다항식 텐서 (phase polynomial tensor)**를 활용합니다. 이 텐서는 가역적 설정에서 모든 와이어 (입력 및 출력) 간의 삼중 패리티 결합을 포착합니다. 이 공식화는 양자 연산이 입력과 출력을 얽히게 하여 3 차 상호작용을 생성하며, 이로 인해 분해 과정에서 '단축 경로'가 가능해져 고전적 MC 추정치보다 낮은 T 비용을 초래할 수 있음을 보여줍니다.

2. 정밀 T 라이브러리 합성:
   저자들은 정밀 T 합성 문제를 제약 정수 계획 문제로 공식화합니다.

   • 입력: $n$개의 입력과 $m$개의 출력을 가진 이차 형식 함수 $f$를 $N = n+m$개의 큐비트에 매핑합니다.
   • 제약 조건: 문제는 목표 함수의 위상 다항식을 2 모듈로로 따르는 위상 다항식을 생성하도록 T 후보 (패리티 항) 의 선택 벡터 $s$를 찾습니다.
   • 최적화: 목적은 $s$의 크기 (T 게이트 수) 를 최소화하는 것입니다.
   • 무관 조건 (Don't-Care Conditions): 이 공식화는 $|0\rangle$로 초기화된 '깨끗한 안시라 (clean ancilla)' 큐비트를 무관 조건으로 활용합니다. 이러한 안시라 상태의 위상은 관측 불가능하므로, T 게이트 수를 추가로 줄이기 위해 특정 T 조합을 무료 S 게이트로 대체하는 등 비용 없는 클리포드 재작성이 가능합니다.
   • 알고리즘: 효율적인 라이브러리 합성 알고리즘은 매핑 행렬과 영공간 (null-space) 기저를 사전 계산합니다. 이는 CUDA 가속 검색을 사용하여 7 개 이하의 변수 ($N \le 7$) 를 가진 함수에 대한 정확한 해를 찾고, 더 큰 입력에 대해서는 준최적 해를 찾습니다.

3. 맞춤형 라이브러리 매핑:
   정밀 T 라이브러리를 완전히 활용하기 위해 저자들은 XAG 흐름과 통합된 맞춤형 매핑기를 개발했습니다.

   • 이차 형식 컷 열거 (Bilinear Cut Enumeration): 매핑기는 대수적 정규형 (ANF) 에서 2 차 항을 나타내는 이차 형식 구조를 드러내는 컷을 우선시합니다. 라이브러리가 지원하지 않는 3 차 이상의 단항을 도입하는 컷은 제거합니다.
   • 비용 모델: AND 개수를 통해 비용을 추정하는 대신, 매핑기는 사전 계산된 정밀 T 라이브러리를 쿼리하여 각 유효한 컷에 대한 정확한 T 비용을 검색합니다.
   • 동적 계획법: 매핑기는 컷에 대한 표준 면적 지향 동적 계획을 수행하지만, 구현을 선택할 때 정밀 T 점수를 사용하여 기본 논리 네트워크 구조를 유지합니다.

주요 기여

• 정밀 T 공식화: 위상 다항식 텐서를 사용하여 클리포드 동등성 하에서 부울 함수를 표준화함으로써 AND 개수 (MC) 최소화에서 정밀 T 게이트 수 최소화로 전환합니다.
• 사전 계산 라이브러리: 깨끗한 안시라 무관 조건을 고려한 정수 계획 접근법으로 합성된, 최대 7 개 변수를 가진 이차 형식 함수에 대한 T 최적 구현 라이브러리입니다.
• 맞춤형 매핑기: 컷 열거 및 순위 매핑 동안 이차 형식 구조를 명시적으로 유지하며, 최적화 결정을 안내하기 위해 정밀 T 라이브러리를 활용하는 매핑 알고리즘입니다.

실험 결과
저자들은 EPFL 산술 벤치마크, 무작위 QLUT 오라클, 모듈러 지수화 (쇼어 알고리즘), AES 용 GF($2^n$) 승산기 등 여러 벤치마크 계열에서 접근 방식을 평가했습니다.

• EPFL 벤치마크: 정밀 MC 에 기반한 기존 XAG 매핑 흐름과 비교하여, 제안된 방법은 산술 벤치마크 (예: 승산기) 에서 T 게이트 수를 최대 14.3% 감소시켰습니다. 벤치마크 전체의 기하평균 감소율은 5.3% 였습니다.
• 암호화 모듈: 전체 합성 흐름 (재합성 포함) 에 통합되었을 때, 이 접근법은 여러 암호화 모듈에 대해 기존 최고 T 게이트 수를 최대 40% 감소시켰습니다.
• 최첨단 기술과의 비교: 이 방법은 AlphaTensor 및 FastTODD 와 같은 독립형 T 최적화뿐만 아니라 기존 QROM 및 SelectSwap 구현보다 우수했으며, 특히 높은 이차 형식 구조를 가진 시나리오에서 두드러졌습니다.
• 실행 시간 오버헤드: 정밀 T 라이브러리 조회 및 맞춤형 매핑으로 인한 추가 계산은 총 실행 시간의 최대 **11.7%**를 차지했으며, 저자들은 이는 양자 모듈 설계의 재사용에 걸쳐 분산되는 일회성 비용이라고 지적했습니다.

의의
논문에 따르면, AND 게이트를 고정된 수의 T 게이트로 균일하게 변환한다고 가정하는 것은 최적성에서 되돌릴 수 없는 손실을 초래합니다. 정밀 T 비용을 고려하면서 XAG 구조를 유지함으로써, 제안된 접근 방식은 회로 품질에서 실질적인 개선을 이룹니다. 이 연구는 클리포드 동등성 기반 표준형과 맞춤형 매핑기를 통해 T 게이트 수를 직접 최적화하는 것이 고전적 비선형성 대리 지표의 한계를 넘어 고장 허용 양자 응용을 위한 리소스 오버헤드를 크게 줄일 수 있음을 보여줍니다.