Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles

기술 요약: 보조 큐비트가 필요 없는 무작위화된 토폴리 게이트와 불리언 오라클의 $T$-count

문제 정의
Clifford+$T$ 게이트 세트를 사용하는 결함 허용 양자 컴퓨팅에서, 불리언 오라클(특히 토폴리 게이트 및 일반적인 다중 제어 NOT 게이트)을 구현하는 것은 자원 비용 사이의 트레이드오프를 수반한다: 즉, $T$ 게이트의 수(증류된 매직 상태를 소비함)와 보조 큐비트의 수 사이의 관계이다.

• 정확한 구현: $n \ge 4$ 큐비트의 경우, 결정 조건(determinant constraints)으로 인해 $\text{Toff}_n$을 자체 큐비트만으로는 구현할 수 없다. 정확한 회로는 일반적으로 깨끗한 보조 큐비트(약 $8n$ 개의 $T$ 게이트 소요) 또는 빌려온 큐비트(약 $16n$ 개의 $T$ 게이트 소요)를 필요로 한다.
• 무작위화 접근법: Gosset, Kothari, Zhang(GKZ)은 회로의 무작위 혼합물을 사용하면 $\text{Toff}_n$을 $n$에 독립적인 $T$-count($O(\log(1/\varepsilon))$)로 근사할 수 있음을 입증했다. 그러나 이들의 직접적인 샘플러는 샘플링된 패리티를 새로운 보조 큐비트에 계산하며, 이는 정밀도 비트당 약 하나($\ell \approx \log(1/\varepsilon)$)의 추가 큐비트를 요구한다.

본 논문이 다루는 핵심 문제는, 무작위 회로의 $O(\log(1/\varepsilon))$ $T$-count 이점을 달성하면서도, $n$이 매우 큰 경우에도 보조 큐비트의 필요성을 완전히 제거할 수 있는지 여부이다.

방법론
본 논문은 회로가 유니터리 Clifford+$T$ 분기들의 확률 분포인 "혼합 모델(mixed model)"을 채택한다. 오차는 대상 유니터리와 평균 채널 사이의 다이아몬드 거리(diamond distance)로 정의된다. 방법론은 다음과 같다:

1. 제자리 패리티 계산(In-Place Parity Computation): GKZ의 직접 샘플러처럼 패리티를 새로운 보조 큐비트에 계산하는 대신, 저자는 CNOT 회로($\Gamma$)를 사용하여 게이트 자신의 제어 큐비트 상에서 이러한 패리티를 "제자리(in-place)"에서 계산하는 방식을 제안한다.
2. 유휴 제어 큐비트 빌리기(Borrowing Idle Controls): 이러한 패리티를 확인하기 위해 필요한 MCNOT는 깨끗한 보조 큐비트를 요구하는 대신, 게이트 자체의 유휴 제어 큐비트를 작업 큐비트로 빌려오도록 구성된다.
3. 아핀 분해(Affine Decompositions): 이 접근법은 불리언 함수를 아핀 부분 공간의 지시 함수의 배타적 논리합(XOR) 합으로 분해함으로써 임의의 불리언 함수로 일반화된다. 각 항은 (부분 공간의 코디멘션이 작은 경우) 정확하게 구현되거나 무작위 분기를 통해 구현된다.
4. 하한 분석(Lower Bound Analysis): 본 논문은 무작위 패리티 결정 트리(RPDT)와 계수 논법을 사용하여 $T$-count의 하한을 설정한다. 저자는 구조적 집합(아핀 부분 공간)과 비구조적 집합(무작위 집합)을 구분하여, "아핀으로부터의 거리"만으로는 비용이 결정되지 않음을 보여준다.

주요 기여 및 결과

1. 보조 큐비트가 없는 무작위 토폴리 게이트 (정리 1):

   • 저자는 보조 큐비트가 필요 없고 중간 회로 측정(mid-circuit measurement)이 필요 없는 $\text{Toff}_n$의 혼합물을 구성한다.
   • 비용: 각 분기는 $8\ell - 8$ 개의 $T$ 게이트를 사용한다 (여기서 $\ell = \lceil \log(4/\varepsilon) \rceil$).
   • 조건: 이 최적의 비용은 $n \ge \lceil 3\ell/2 \rceil$일 때 달성된다. 이 영역에서 $n-1-\ell$개의 유휴 제어 큐비트는 (Maslov의 상대 위상 토폴리 게이트에 기반한) MCNOT 구성을 위한 빌려온 작업 큐비트로 충분히 기능한다.
   • 중간 영역: $\ell + 2 \le n < \lceil 3\ell/2 \rceil$인 경우, 이 구성은 여전히 보조 큐비트를 사용하지 않지만, 더 적은 수의 빌려온 큐비트를 활용하기 위해(Zindorf와 Bose의 구성을 기반으로 함) 최대 $16\ell - 32$ 개의 $T$ 게이트를 사용한다.
   • 비교: 이는 하나의 깨끗한 보조 큐비트를 유지하는 최선의 측정 없는 변형보다 회로당 $T$ 게이트를 하나 더 사용하지만, 보조 큐비트 요구 사항을 완전히 제거한다.

2. 구조적 오라클로의 확장 (정리 2):

   • 이 기술은 $J$개의 아핀 부분 공간 지시 함수의 배타적 논리합으로 분해 가능한 임의의 불리언 함수 $f$로 확장된다 (예: 등가성 테스트, 선형 방정식 체크, 결정 트리).
   • 만약 큐비트 수 $n$이 부분 공간의 코디멘션에 비해 충분히 크다면, 해당 오라클은 보조 큐비트 없이 $n$에 독립적인 $T$-count인 최대 $8J\ell_J$를 사용하여 구현될 수 있다.

3. 하한 및 최적성 (정리 3 & 4):

   • 본 논문은 다이아몬드 오차 $\varepsilon$로 $\text{Toff}_n$을 근사하는 모든 혼합물은 일부 분기에서 최소 $\min\{n-1, \log((1-\varepsilon)/\varepsilon)\} - 2$ 개의 $T$ 게이트를 필요로 함을 증명한다.
   • 제안된 구성은 이 하한의 8배 이내의 범위에 있다.
   • 결정적으로, 모든 혼합물이 정확한 불리언 오라클을 구현하는 경우, 상한($8\ell$)과 하한($\approx \ell$) 사이의 간극을 좁히는 것은 제어당 8개 미만의 $T$ 게이트를 갖는 정확한 다중 제어 NOT를 찾는 문제와 동일함을 밝힌다.

4. 구조 vs 무작위성 (정리 5):

   • 본 논문은 $T$-count가 가장 가까운 아핀 함수로부터의 함수적 거리에 의해서만 결정되는 것이 아님을 입증한다.
   • 아핀 부분 공간: 코디멘션이 $k$인 아핀 부분 공간의 지시 함수는 $O(1)$ 개의 $T$ 게이트(구체적으로 상수 오차에 대해 $\le 24$)를 소모한다.
   • 무작위 집합: 동일한 밀도($2^{-k}$)를 가진 무작위 집합은 깨끗한 보조 큐비트가 있을 때 $\approx 2^{(n-k)/2}$ 개의 $T$ 게이트를, 없을 때 $\approx 2^{n-k}$ 개의 $T$ 게이트를 필요로 하며, 이는 지수적으로 많다.
   • 이는 구조화된 오라클(아핀 부분 공간)은 제안된 보조 큐비트 없는 무작위화 접근법의 혜택을 크게 받는 반면, 비구조적 오라클은 추가 큐비트가 있더라도 무작위화를 통해 저렴해질 수 없음을 강조한다.

의의 및 주장
저자는 논리 큐비트의 수가 제한적인 계산(초기 결함 허용 장치에서 흔한 제약)에서, 제안된 보조 큐비트 없는 무작위 회로가 정확한 구성의 실행 가능한 대안을 제공한다고 주장한다.

• 자원 효율성: 기존의 무작위 샘플러가 가진 "정밀도 비트당 하나의 추가 큐비트" 오버헤드를 제거하여, 회로가 게이트 자체의 큐비트 상에서 완전히 실행될 수 있게 한다.
• 확장성: 원하는 정밀도 $\varepsilon$에 대해 $n$이 충분히 커지면 $T$-count는 제어 수 $n$에 독립적이 된다.
• 이론적 통찰: 본 논문은 무작위 오라클 분기의 비용과 정확한 다중 제어 NOT 최적화 사이의 긴밀한 연결 고리를 확립한다. 또한, 무작위화가 구조화된 함수에 대해서는 $n$에 대한 선형 의존성을 제거할 수 있지만, 비구조적 함수에 대해서는 지수적 비용을 극복할 수 없음을 명확히 한다.

저자는 무작위 토폴리 게이트의 최적 $T$-count에 대한 상수 계수(현재 8 대 하한 $\approx 1$)를 알지 못하며, 이 간극을 좁히는 것은 정확한 다중 제어 NOT 합성의 향후 개선에 달려 있음을 언급한다. 또한 특정 아키텍처에 대한 시공간 볼륨(space-time volume)에 대한 추정치는 제시하지 않았다.