Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations

이 논문은 양자 알고리즘의 핵심 연산인 유한체 $GF(2^m)$의 곱셈과 나눗셈을 수행하는 양자 회로를 최적화하는 방법을 제시합니다. 저자들은 보조 큐비트 (ancilla) 를 사용하지 않는 (ancilla-free) 환경에서 게이트 수 복잡도를 이론적 (asymptotic) 으로 개선하고, 실제 암호학적 매개변수에 대해 실질적인 성능 향상을 달성했습니다.

주요 내용은 다음과 같습니다.

1. 문제 정의 (Problem)

• 배경: 이산 로그 문제, 양자 증명 (proofs of quantumness), 타원곡선 암호 등 다양한 양자 알고리즘은 $GF(2^m)$ 연산에 의존합니다.
• 현재의 한계: 기존 $GF(2^m)$ 곱셈 회로 (특히 Karatsuba 기반) 는 CNOT 게이트 수의 점근적 복잡도가 $O(m^2)$으로, 실제 구현에서 병목 현상을 일으켰습니다. 특히 상수 다항식 $1 + x^{\lceil m/2 \rceil}$에 의한 곱셈/나눗셈 구현이 비효율적이었습니다.
• 목표: 보조 큐비트 없이 CNOT 및 Toffoli 게이트 수를 최소화하면서, 점근적 복잡도를 개선하고 실제 암호학적 크기 (예: $m=163, 256, 571$ 등) 에서 게이트 수를 획기적으로 줄이는 회로를 설계하는 것.

2. 방법론 (Methodology)

A. 곱셈 최적화 (Multiplication)

• Karatsuba 알고리즘 개선: 기존 Karatsuba 기반 회로의 병목이었던 상수 다항식 $1 + x^{\lceil m/2 \rceil}$에 의한 곱셈을 효율적으로 구현하는 새로운 회로를 개발했습니다.
• 선형 복잡도 달성: 특정 형태의 기약 다항식 (Irreducible Polynomial) 을 선택하여, 이 상수 곱셈 회로의 CNOT 게이트 수를 $O(m^2)$에서 $O(m)$으로 줄였습니다.
  • 짝수 $m$의 경우: 삼항식 (trinomial) 또는 특정 조건을 만족하는 일반 기약 다항식을 사용하여 $O(m)$ 회로 구성.
  • 홀수 $m$의 경우: $x^{n+1}+1$ 형태의 곱셈을 순환 행렬 (circulant matrix) 합성 문제로 변환하여 $O(m)$ 회로 구성.
• 결과: 전체 곱셈 회로의 CNOT 게이트 수 복잡도를 $O(m^2)$에서 $O(m \log_2 3)$으로 낮추었습니다. 이는 Toffoli 게이트 수 복잡도와 일치합니다.

B. 나눗셈 최적화 (Division)

• 이토 - 쓰지 (Itoh-Tsujii) 알고리즘 개선: $GF(2^m)$ 나눗셈은 역원 계산 ($b^{-1}$) 을 통해 수행되며, 이는 제곱 (squaring) 과 곱셈의 반복으로 이루어집니다.
• 효율적인 제곱 회로: 선형 가역 변환인 제곱 연산을 $O(m \log m)$ 게이트로 구현할 수 있는 기약 다항식을 선택했습니다.
• 덧셈 체인 (Addition Chains): 역원 계산을 위한 지수 연산 시 필요한 곱셈 횟수를 줄이기 위해 Dimitrov 와 Järvinen 의 덧셈 체인을 활용하여 곱셈 횟수를 최대 22% 감소시켰습니다.
• 복잡도 개선: 나눗셈 회로의 CNOT 게이트 수 복잡도를 $O(m^2 \log m)$에서 $O(m^2 \log \log m / \log m)$으로 개선했습니다.

C. 기타 최적화 기법

• 동시 최적화: 곱셈과 나눗셈 모두에 효율적인 기약 다항식을 동시에 선택하여 전체 시스템 비용을 최소화했습니다.
• Parity Controlled Toffoli (PCTOF): Toffoli 게이트의 수를 줄이기 위해 PCTOF 게이트 표현과 순위 축소 (rank reduction) 기법을 적용했습니다.
• $\sqrt{U}$의 복잡도 분석: 선형 가역 변환 $U$와 그 제곱근 $\sqrt{U}$의 회로 깊이 관계를 분석하여, $\sqrt{U}$가 $U$보다 점근적으로 더 깊은 회로가 필요할 수 있음을 증명했습니다.

3. 주요 결과 (Key Results)

• 게이트 수 감소:
  • CNOT 게이트: 암호학적으로 중요한 $m$ 값 (예: $m=163, 256$) 에서 기존 방법 대비 최대 20.9% 감소.
  • Toffoli 게이트: 최대 18.06% 감소.
  • 상수 곱셈 회로: $m=6159$와 같은 큰 규모에서 기존 LU 분해 기반 구현 대비 357 배 이상의 CNOT 게이트 감소 효과 (6,158 개 vs 2,201,876 개).
• 보조 큐비트: 곱셈 연산은 완전히 보조 큐비트 없이 (ancilla-free) 수행 가능하며, 나눗셈 연산에서도 보조 큐비트 사용량을 기존보다 줄이거나 유지하면서 성능을 개선했습니다.
• 실제 데이터: $m=2$부터 $m=1024$까지 다양한 크기에 대한 구체적인 게이트 수 (Toffoli, CNOT) 와 보조 레지스터 수를 표 (Table I, II) 로 제시하여 기존 연구 ([46], [21], [3] 등) 와 비교했습니다.

4. 의의 및 중요성 (Significance)

1. 이론적 한계 돌파: $GF(2^m)$ 곱셈의 CNOT 게이트 수 점근적 복잡도를 $O(m^2)$에서 $O(m \log_2 3)$으로 낮추어, 양자 회로 설계의 이론적 한계를 확장했습니다.
2. 실용적 최적화: 단순한 점근적 개선에 그치지 않고, 실제 양자 암호 분석 및 양자 우위 증명에 사용되는 구체적인 매개변수 ($m$) 에서 100 배 이상의 게이트 수 감소를 실현했습니다. 이는 오류 정정이 필요한 초기 내결함성 양자 컴퓨터 (FTQC) 에서 연산 비용을 크게 절감할 수 있음을 의미합니다.
3. 고전 컴퓨팅과의 연관성: 이 연구는 양자 회로 최적화뿐만 아니라, $m$ 비트 레지스터 간의 곱셈을 $O(m \log_2 3)$ 복잡도와 $3m$ 비트의 메모리만으로 수행하는 고전 알고리즘의 존재를 시사합니다.
4. 암호학적 영향: 타원곡선 이산 로그 문제 (ECDLP) 와 같은 암호 체계에 대한 양자 공격의 실용성을 높이는 동시에, 양자 내성 암호 (PQC) 설계에 필요한 기본 연산의 효율성을 증대시킵니다.

결론적으로, 이 논문은 보조 큐비트 제약 하에서 $GF(2^m)$ 연산을 수행하는 양자 회로의 효율성을 이론적, 실용적 측면 모두에서 획기적으로 개선한 중요한 연구입니다.