Sparse Quantum State Preparation with Sublinear T-Count

기술 요약: 하위 선형 T-count를 갖는 희소 양자 상태 준비

문제 정의
본 논문은 Clifford+T 모델 내에서 희소 양자 상태(sparse quantum states)를 준비하는 데 드는 결함 허용 비용(fault-tolerant cost)을 다룹다. $n$-큐비트 상태는 그 계산 기저(computational basis)에서의 서포트(support)가 최대 $s$개의 0이 아닌 진폭을 가질 때 $s$-희소(s-sparse)하다고 정의된다. 일반적인 $n$-큐비트 상태 준비의 경우 $\Theta(\sqrt{2^n} \log(1/\epsilon) + \log(1/\epsilon))$라는 알려진 최적 T-count를 갖지만, 희소 상태에 대한 이전 연구들은 $s$에 대한 선형 의존성에 의해 제한되었다. 구체적으로, 최근 연구들은 $s$-희소 상태에 대해 $O(s)$ T 게이트의 상한을 확립했다. 본 연구에서 조사된 핵심 질문은, 특히 서포트 크기 $s$가 큐비트 수 $n$에 비해 클 때, $s$-희소 상태를 준비하기 위한 T-count를 $s$에 대해 하위 선형(sublinear)으로 만들 수 있는가 하는 점이다.

방법론
저자들은 상태 준비를 세 가지 주요 단계로 분해하여 접근한다:

1. 레이블 상태 준비 (Label State Preparation): $\lceil \log s \rceil$-큐비트 인덱스 레지스터 상에 조밀한 중첩(dense superposition)을 준비한다.
2. 코히어런트 로딩 (Coherent Loading): 불리언 함수(Boolean function)를 사용하여 인덱스 $i$를 $n$-큐비트 데이터 레지스터의 대응하는 기저 문자열 $x^{(i)}$로 매핑한다.
3. 레이블 삭제 (Label Erasure): 레이블링 맵의 역함수를 적용하여 인덱스 레지스터를 언컴퓨트(uncompute)함으로써, 데이터 레지스터를 타겟 상태로 남긴다.

핵-기술적 혁신은 레이블 삭제 단계의 합성(synthesis)에 있으며, 이는 지원되는 입력 $x^{(i)}$를 그들의 인덱스 $i$로 다시 매핑하고 나머지 모든 입력은 0으로 매핑하는 희소 불리언 함수 $L: \{0, 1\}^n \to \{0, 1\}^{\lceil \log s \rceil}$를 구현하는 것을 포함한다. 저자들은 서포트 크기 $s$에 따라 전략을 조정하는 희소 불리언 함수를 위한 **서포트 인식 합성 정리(support-aware synthesis theorem)**를 개발하였다:

• 작은 서포트 영역 ($s \leq n^{3/2} \log n$): 이 방법은 $s$개의 지원되는 입력을 단사 함수(injection)를 통해 로그 크기의 레이블 레지스터로 압축한다. 문제는 $O(\log s)$ 비트에 대한 불리언 함수를 합성하는 문제로 환원되며, 이는 $O(s+n)$ Toffoli 게이트로 수행될 수 있다.
• 큰 서포트 영역 ($s > n^{3/2} \log n$): 저자들은 고정된 접두사(prefix) 길이 $r$을 사용하는 재귀적 알고리즘을 채택한다. 각 단계에서 알고리즘은 현재 서포트의 활성 $r$-비트 접두사를 분석한다:
  • 적은 수의 접두사가 활성화되어 있는 경우, **접두사 압축(prefix compression)**을 수행하여, 서포트 크기를 변경하지 않으면서 활성 접두사를 단사적으로 재레이블링하여 입력 길이를 줄인다.
  • 많은 수의 접두사가 활성화되어 있는 경우, **서포트 필링(support peeling)**을 수행하여, 각 활성 접두사로부터 하나의 지원되는 입력을 제거한다. 이 "필링된(peeled)" 슬라이스는 저렴하게 구현되는 반면, 남은 재귀적 인스턴스는 상당한 비율의 서포트 포인트를 잃게 된다.
    이 두 연산을 균형 있게 조절함으로써, 알고리즘은 $s$에 대해 하위 선형적으로 스케일링되는 Toffoli count를 달erm한다.

하한(lower bounds)의 경우, 논문은 두 가지 별개의 기술을 활용한다:

• 작은 $s$ ($s = O(n)$): 스테빌라이저 영점(stabilizer nullity) 논증의 확장. 저자들은 상태가 $|W_s\rangle \otimes |0^{n-s}\rangle$에 가까울 때 스테빌라이저 부분군 랭크(rank)가 제한됨을 증명하며, 이는 $\Omega(s)$의 선형 하한을 함의한다.
• 큰 $s$ ($s = \Omega(n)$): [GKW26]의 카운팅 렘마와 결합된 패킹 논증(packing argument). 서로 잘 분리된(pairwise well-separated) $s$-희소 상태들의 큰 패밀리를 구성하고, $t$개의 T 게이트로 준비 가능한 상태의 수를 제한함으로써, $\Omega(\sqrt{ns})$의 하한을 도출한다.

주요 기여 및 결과

1. 하위 선형 상한: 본 논문은 임의의 $n$-큐비트 $s$-희소 상태를 오차 $\epsilon$까지 다음의 T 게이트를 사용하여 준비할 수 있음을 입증한다:
   $$\tilde{O}\left(\min\left\{s, n^{3/4}\sqrt{s}\right\} + \sqrt{s}\log(1/\epsilon) + \log(1/\epsilon)\right)$$
   이는 충분히 큰 서포트(구체적으로 $s \gtrsim n^{3/2}$)에 대해 $s$에 대한 하위 선형 의존성을 보여주는 최초의 결과이다. 보조 큐비트(ancilla) 요구량은 $\tilde{O}(\sqrt{ns})$이다.

2. 타이트한 하한: 저자들은 $0 < \epsilon \leq 1/6$ 및 $2 \leq s \leq 2^{n/2}$에 대해 T-count가 다음과 같이 하한을 가짐을 증명한다:
   $$\Omega(\min\{s, \sqrt{ns}\})$$
   이 결과는 작은 서포트 영역($s = O(n)$)에서는 $s$에 대한 선형 의존성이 피할 수 없으며, 큰 서포트 영역에서는 $n$에 대한 의존성을 완전히 제거할 수 없음을 보여준다.

3. 서포트 인식 합성 정리: 서포트 크기 $s$를 갖는 희소 불리언 함수 $F: \{0, 1\}^n \to \{0, 1\}^b$를 합성하기 위한 일반적인 정리. Toffoli 복잡도는 작은 $s$에 대해서는 $O(s+n)$이며, 큰 $s$에 대해서는 $\tilde{O}(n^{3/4}\sqrt{s} + n^{1/4}\sqrt{bs})$이다. 저자들은 이 결과가 상태 준비 이외에도 독립적인 관심사가 될 수 있음을 언급한다.

의의 및 주장
본 논문은 희소 상태 준비가 $s$에 대해 하위 선형이 될 수 있는지에 대한 질문을 해결했다고 주장한다. 결과는 이전에 알려진 선형 $O(s)$ 상한이 큰 서포트에 대해서는 본질적인 것이 아님을 보여준다; 즉, 비용을 $\tilde{O}(n^{3/4}\sqrt{s})$로 줄일 수 있다. 그러나 저자들은 자신들의 상한 $\tilde{O}(n^{3/4}\sqrt{s})$과 하한 $\Omega(\sqrt{ns})$ 사이의 남아있는 간극에 대해 겸손한 입장을 취한다.

논문은 $s \approx n^{3/2}$에서의 교차점과 $n^{3/4}$ 인자가 그들의 특정 알고리즘의 산물인지, 아니면 결함 허용 희소 양자 상태 준비의 본질적인 한계를 반영하는 것인지 불분명하다고 명시적으로 밝힌다. 또한, 작은 서포트 영역에서 불리언 함수의 부분적 성질(partial nature)을 활용하였으나, 이러한 완화를 큰 서포트 구조에 통합하는 것이 현재로서는 점근적 상한을 개선하지 못한다는 점을 언급하며, 부분 함수 구조(partial-function structure)의 활용 가능성을 향후 과제로 남겨두었다.