Resource-Efficient Synthesis of Sparse Quantum States

기술 요약: 희소 양자 상태의 자원 효율적 합성

문제 정의
양자 상태 준비는 해밀토니안 시뮬레이션, 선형 솔버, 머신러닝을 포함한 수많은 양자 알고리즘의 근본적인 서브루틴입니다. 그러나 임의의 $n$-큐비트 상태를 준비하는 것은 일반적으로 $\Omega(2^n)$의 회로 크기를 요구하므로, 대규모 시스템에 대해서는 자원 효율성이 떨어집니다. 많은 실용적인 응용 분야에서 희소 상태(비제로 엔트리가 적은 벡터)만을 필요로 하지만, 기존의 희소 상태 합성 방법들은 결함 허용 양자 컴퓨팅(FTQC)을 위한 핵심 지표를 최적화하는 데 실패하는 경우가 많습니다. 특히 FTQC에서는 비클리포드(non-Clifford) 게이트(예: T 게이트)를 구현하는 비용이 클리포드(Clifford) 게이트보다 훨씬 높습니다. 현재의 희소 상태 합성 방식은 종종 높은 비클리포드 카운트를 보이거나 과도한 회로 깊이를 나타내며, 비클리포드 자원을 최소화하면서 선형 깊이를 유지하는 접근 방식은 거의 없습니다.

방법론
저자들은 $s$-희소, $n$-큐비트 상태의 합성을 두 가지 별개의 최적화된 작업으로 분해하는 새로운 방법론을 제안합니다:

1. 가중 W-상태 생성 (Weighted W-State Generation): 첫 번째 단계는 희소 상태의 진폭을 인코딩하는 일반화된 W-상태 $|W(\vec{\alpha})\rangle = \sum \alpha_i |e_i\rangle$를 준비하는 것입니다. 논문은 두 가지 구성 전략을 제시합니다:

   • 트리 기반 구성 (Tree-based Construction): 이진 트리 구조에 기반한 귀납적 정의를 사용하는 보조 큐비트가 없는 정확한 방식입니다. 이 방식은 $RY(\theta)$ 게이트를 활용하며 $O(n)$ 크기와 $O(\log n)$ 깊이를 달성합니다. 저자들은 이러한 회전(rotations)이 Clifford+T 세트로 컴파일될 수 있는 조건을 분석하며, 균일한 W-상태의 경우 상당한 T-게이트 감소가 가능함을 언급합니다.
   • 전체 상태 구성 (Full-State Construction): 다른 방식은 $\lceil \log_2 n \rceil$개의 큐비트 상에서 전체 상태를 준비하고 기저 상태를 W-상태 기저로 매핑합니다. 이 방법은 전 상태 준비(full state preparation)에 관한 최근의 최적화된 결과(Gosset et al.)를 활용하여 결함 허용 환경에서 더 나은 T-카운트를 달-성하지만, 더 높은 보조 큐비트 요구량을 가집니다.

2. 고전적 가역 회로를 통한 치환 (Permutation via Classical Reversible Circuits): 두 번째 단계는 W-상태의 기저 상태 $|e_i\rangle$를 희소 벡터의 특정 타겟 기저 상태로 매핑하는 것입니다. 이는 이진 문자열에 대한 치환 문제로 모델링됩니다.

   • 저자들은 이를 고전적 가역 게이트(X, CX, CCX)에 대응하는 기본 행 연산을 사용하여 이진 행렬 $M_\chi$를 대각화하는 문제로 환원합니다.
   • 저자들은 회로 깊이를 최소화하기 위해 병렬 제거 단계를 사용하는 새로운 변형 가우스-조르단 소거법(Gauss-Jordan elimination)을 도입합니다.
   • 핵심 최적화는 타겟 큐비트가 연산 후 $|0\rangle$임이 보장되는 경우, 값비싼 토폴리(Toffoli, CCX) 게이트를 대체하기 위해 적응형 클리포드 회로(측정과 클래식하게 제어되는 게이트 포함)를 사용하는 것입니다. 이를 통해 치환 회로를 $O(s)$의 T-카운트(또는 측정을 통한 제로 T-카운트)와 $O(s+n)$의 깊이로 구현할 수 있습니다.

주요 기여 및 결과

• 자원 효율성: 제안된 알고리즘은 비클리포드 카운트가 희소도 $s$에 선형적($O(s)$)이고, 회로 깊이가 희소도와 큐비트 수 모두에 선형적($O(s+n)$)인 희소 상태를 합성합니다. 이는 깊이가 $O(sn)$이거나 비클리포드 카운트가 초선형(super-linear)인 기존의 최첨단 방식들을 개선한 것입니다.
• 결함 허용 컴파일: Clifford+T 게이트 세트로 컴파일할 때, 저자들은 T-카운트, 깊이, 보조 큐비트 수 사이의 트레이드오프를 제공하는 세 가지 구성을 제시합니다.
  • 가장 T-최적화된 구성은 $O(\sqrt{s \log_2(1/\epsilon)} + \log_2(1/\epsilon))$의 T-카운트를 달성합니다. 저자들은 이것이 Gosset et al.의 전체 상태 준비에 대한 최적성 경계와 일치함을 언급하며, 이 구성이 희소 상태에 대해서도 최적일 가능성이 높음을 시사합니다.
• 특수 사례 최적화: "T-균일(T-uniform)" 희소 상태(즉, 비제로 엔트리가 $\{e^{ik\pi/4}\}$ 집합에 있는 경우)에 대해, 저자들은 더티 보조 큐비트(dirty ancillae)를 사용하여 성공 확률 $> 1/2$로 $O(\sqrt{s})$개의 T-게이트만을 사용하는 정확한 합성을 입증합니다.
• 행렬 대각화 기술: 본 논문은 병렬 CX 및 CCX 연산을 사용하여 이진 행렬을 대각화하는 특정 알고리즘을 기여하며, 이는 치환 회로의 핵심 엔진 역할을 합니다.

의의
본 논문은 주로 결함 허용 양자 컴퓨팅에서 비클리포드 게이트의 자원 병목 현상을 해결한다는 점에서 의의를 갖습니다. 진폭 준비(W-상태)와 기저 치환을 분리함으로써, 저자들은 비클리포드 자원이 총 큐비트 수가 아닌 희소도에 따라 선형적으로 스케일링되는 합성 방법을 달성했습니다. 회로 깊이 또한 $s$와 $n$에 대해 곱셈적 의존성이 아닌 가산적(additive) 관계로 개선되었습니다.

저자들은 자신들의 방법이 T-카운트와 깊이 면에서 매우 효율적이지만, 일부 기존 방식에 비해 더 많은 수의 보조 큐비트($\max(s, n) - n$)를 요구할 수 있다고 겸허히 밝힙니다. 또한, 클리포드 친화적인 연산을 극대화하기 위해 트리 구조를 최적화하는 것이 파티션 문제(partition problem)와 관련된 클래식 NP-난해 문제임을 식별하였으며, 향후 연구에서 특정 하드웨어 연결성 제약에 맞게 가역 회로 로직을 조정하거나 디케 상태(Dicke states)로 일반화하는 방안을 탐구할 수 있다고 제안하였습니다.