Optimised T counts and active volume estimates for high- and low- level arithmetic subroutines

제목: 고수준 및 저수준 산술 서브루틴을 위한 최적화된 T-계수 및 활성 부피 추정

저자: Sam Heavey (임페리얼 칼리지 런던)

문제 정의

표면 코드 기반 양자 컴퓨터는 결함 허용 양자 컴퓨팅을 위한 유력한 후보입니다. 그러나 2차원 국소 연결 큐비트 배열에 의존하는 전통적인 "베이스라인" 아키텍처는 상당한 비효리성을 겪습니다. 계산의 시공간 부피 중 상당 부분이 "유휴(idle)" 상태이며, 이는 특정 연산 중에 사용되지 않고 놓여 있는 논리 큐비트에 해당합니다. 이러한 유휴 부피는 논리적 계산에 기여하지 않으면서 전체 자원 비용(시공간 부피)을 증가시킵니다.

반면 "활성 부피(active volume, AV)" 아키텍처는 연산을 병렬화하기 위해 장거리 연결성을 활용함으로써 이 유휴 부피를 제거하는 것을 목표로 하지만, 정확한 활성 부피 추정치를 가진 최적화된 산술 서브루틴의 종합적인 카탈로그가 부족한 실정입니다. 기존 문헌은 종종 상태 주입(state injection) 및 반응적 측정(reactive measurements)이 관여할 때 회로 구조가 활성 부피에 어떻게 영향을 미치는지 완전히 고려하지 않은 채, 베이스라인 아키텍처에서의 T-계수 감소에만 초점을 맞춥니다.

방법론

본 논문은 저수준(예: 증분, 시프트, 덧셈) 및 고수준(예: 제곱근, 삼각함수, 로그) 산술 서브루틴에 대한 활성 부피와 T-계수를 도출하고 최적화하기 위한 방법론을 제안합니다.

1. 최적성 가정: 본 연구는 베이스라인 아키텍처에서 T-계수와 큐비트 수를 최소화하는 회로 설계가 가장 작은 활성 부피를 산출할 것이라는 가정하에 작동합니다. 이를 통해 저자는 모든 가능한 설계 변형에 대해 활성 부피를 계산하는 대신, T-계수(특히 Toffoli 및 임시 AND 게이트)를 최소화하는 데 집중할 수 있습니다.
2. 게이트 세트 최적화: 저자는 특정 연산의 T-계수를 절반으로 줄이기 위해 "임시 AND" 게이트(Gidney가 도입)를 활용합니다. 또한, CCZ 마법 상태(magic state)의 디스틸레이션(distillation)이 활성 부피 모델에서 종종 더 저렴하기 때문에, To even 및 임시 AND 게이트를 T 상태 대신 CCZ 마법 상태를 사용하여 구현하는 방식을 선택합니다.
3. 지향성 ZX 다이어그램을 통한 활성 부피 계산:
   • 저자는 표준 회로 다이어그램을 ZX 다이어그램으로 변환한 후, 다시 지향성 ZX(OZX) 다이어그램으로 변환합니다.
   • OZX 다이어그램은 공간적 인지 능력을 포함하여, 스파이더(spider)를 3D 시공간 블록의 특정 포트(U, D, N, S, E, W)에 매핑합니다.
   • OZX 연결성 제약 내에서 ZX 계산 규칙(예: 스파이더 병합)을 적용함으로써, 저자는 다이어그램을 단순화하여 필요한 최소한의 논리 블록(스파이더) 수를 계산합니다.
   • 전체 활성 부피는 스파이더의 블록 수를 합산하고, 요구되는 마법 상태(예: CCZ 상태)에 대한 디스틸레이션 비용을 더하여 계산됩니다.
4. 반응 깊이 분석: 논문은 비-클리포드(non-Clifford) 게이트에 대한 교정 연산을 결정하기 위한 측정 결과의 클래식 프로세싱에 소요되는 시간인 "반응 깊이(reaction depth)"를 고려합니다. 전체 반응 깊이는 순차적 구성 요소들의 깊이 합계로 계산되며, 이는 계산 시간의 상한을 제공합니다.

주요 기여 및 결과

1. 저수준 산술 서브루틴
본 논문은 Qiskit 시뮬레이션을 통해 검증된 최적화된 기초 연산들을 제시합니다:

• 증분(Increment) 및 제어 증분(Controlled Increment): 임시 AND 게이트를 사용하도록 수정되어, 증분의 경우 $7n - 14$, 제어 증분의 경우 $7n - 7$로 T-계수를 줄였습니다.
• 시프트(Shifts): 활성 부피 아키텍처에서 제어되지 않은 시프트는 리레이블링(relabeling)을 통해 "무료"(논리 블록 비용 0)임을 입증했습니다. 제어된 시프트는 ZX 스파이더 병합을 통해 최적화되었으나, 최적화되지 않은 버전과 비교했을 때 블록 수 감소는 미미합니다.
• 제어 덧셈/뺄셈(CAS): 새로운 Gidney 스타일의 제어 가산기가 설계되었습니다. 이는 단순한 비용 합계에 비해 약 8%의 활성 부피 감소를 달야하며, T-계수는 $7n - 7$입니다.
• 곱셈(Multiplication): Toffoli 배열과 제어 오버플로우 Gidney(COG) 가산기를 사용하는 새로운 곱셈기를 제안합니다. 이는 Muñoz-Coreas & Thapliyal [21]의 최첨단 설계와 비교했을 때 T-계수의 선행 계수를 62% 감소시킵니다.
• 제곱(Squaring): 큐비트 수를 CNOT 게이트와 교환함으로써 최적화되었으며, 곱셈을 위한 큐비트 요구량을 $6n+2$에서 $5n$으로 줄였습니다.

2. 고수준 산술 서브루틴
저자는 이러한 저수준 구성 요소들을 복잡한 함수로 확장합니다:

• 제곱근(Square Root): 최적화된 비복원(non-restoring) 제곱근 알고리즘이 제시됩니다. 이는 기존 설계[19]에 비해 T-계수를 크게 줄이지만, 큐비트가 약간 더 많이 필요합니다($3n$ vs $2n+1$).
• 삼각함수(Piecewise Polynomial Evaluation - PPE): 본 논문은 Häner의 PPE 회로를 적응시킵니다. 원래의 가산기와 곱셈기를 저자의 최적화된 버전(OG 가산기, COG 곱셈기) 및 새로운 비교기로 교체함으로써, 원래 구현[20]에 비해 선행 항의 T-계수를 약 2/3 감소시켰습니다.
• 역삼각함수(Arcsine): 다항식 평가와 제곱근을 결합한 회로가 구축되었습니다. 새로운 설계는 Häner의 구현[20]과 비교했을 때 $n^2$ 항의 T-계수를 거의 6배 감소시킵니다.
• 로그(Logarithm): Wang 등의 qFBE 방법이 활성 부피 컴퓨팅에 맞게 적응되었습니다. 본 논문은 이 방법에 대한 최초의 활성 부피 및 T-계수 추정치를 제공하며, 양자 연산에서 $O(n^3)$임을 명시합니다.

3. 활성 부피의 구조적 민감도
핵심적인 발견은 회로 구조가 게이트 수와 독립적으로 활성 부피에 영향을 미친다는 점입니다. 저자는 동일한 게이트 수를 가진 논리적으로 동등한 회로들이 제어(control)와 타겟(target)의 배치로 인해 서로 다른 활성 부피를 가질 수 있음을 보여줍니다. 특히, 제어와 타겟의 중단 없는 라인을 최대화하는 설계는 ZX 계산 내에서 더 효율적인 스파이더 병합을 가능하게 하여 블록 수를 줄여줍니다. 이는 활성 부피 아키텍처를 위한 설계 시 게이트 수만을 최적화하는 것은 불충분함을 시사합니다.

의의 및 주장

본 논문은 지향성 ZX 다이어그램을 사용하여 활성 부피를 추정하고 최적화하는 "간단한 방법론"을 제공한다고 주장합니다. 주요 의의는 다음과 같습니다:

• 자원 감소: 주요 양자 알고리즘(예: 인수분해, HHL)의 빌딩 블록인 광범위한 산술 서브루틴에 대해 T-계수와 활성 부피를 크게 감소시켰습니다.
• 아키텍처 인식: "활성 부피" 지표가 단순히 게이트 복잡성뿐만 아니라 회로 토폴로지에도 민로하다는 점을 강조합니다. 이는 장거리 연결성을 가진 아키텍처를 위한 회로 설계 방식의 변화를 요구합니다.
• 카탈로그 확장: 활성 부피 컴퓨팅의 맥락에서 이전에 부족했던 최적화된 서브루틴(로그 $x$, 아크사인 $x$와 같은 고수준 함수 포함)에 대한 필수적인 자원을 제공합니다.

저자는 자신의 작업이 T-계수와 활성 부피에 초점을 맞추고 있지만, 향후 연구에서는 클리포드 게이트 최적화와 캐리 룩어헤드(carry look-ahead) 가산기 및 나눗셈 회로와 같은 다른 저수준 서브루틴의 포함을 고려해야 한다고 결론짓습니다. 저자는 모든 자원 추정 문제를 해결했다고 주장하는 것이 아니라, AV 인식 회로 설계에 대한 추가 조사를 촉구하는 것을 목표로 합니다.