기술 요약: 최적의 T-count를 이용한 양자 상태 준비

문제 정의

본 논문은 결함 허용 양자 컴퓨팅(fault-tolerant quantum computing)에서 임의의 양자 상태 및 연산을 구현하는 데 필요한 "매직"(non-Cliffordness)의 양을 정량화하는 근본적인 문제를 다룬다. 구체적으로, $n$-큐비트 임의의 양자 상태 또는 임의의 대각(diagonal) $n$-큐비트 유니터리를 $\ell_2$ 노름(상태의 경우) 또는 연산자 노름(유니터리의 경우) 내에서 오차 $\varepsilon$로 $\varepsilon$-근사하기 위해 필요한 최소 $T$ 게이트 수($T$-count)를 조사한다.

Low, Kliuchnikov, Schaeffer(LKS)의 선행 연구는 보조 큐비트를 사용한 상태 준비에 대해 $O(\sqrt{2^n n \log(n/\varepsilon)} + \log^2(n/\varepsilon))$의 상한(upper bound)을 확립했다. 저자들은 이 스케일링이 최적인지, 아니면 큐비트 수 $n$과 오차 의존성 $\log(n/\varepsilon)$과 관련된 오버헤드를 줄일 수 있는지 확인하고자 한다.

방법론

본 논문은 구성적 합성 알고리算法(constructive synthesis algorithms)과 정보 이론적 하한(information-theoretic lower bound) 논증을 결합하여 사용한다.

1. 대각 유니터리 합성 (Diagonal Unitary Synthesis)

핵심적인 기술적 혁신은 대각 유니터리를 합성하는 새로운 방법이다. 저자들은 $n$-큐비트 대각 유니터리 $D$를 $n-1$개의 큐비트에 의해 제어되는 단일 큐비트 유니터리 $G_y$로 간주한다.

• 근사 (Approximation): 각 단일 큐비트 유니터리 $G_y$는 기존의 최적 단일 큐비트 합성 기법(Ross-Selinger 등)을 사용하여 $O(\log(1/\varepsilon))$개의 Hadamard 및 $T$ 게이트 시퀀스로 근사된다.
• 오라클 구현 (Oracle Implementation): 제어 비트 $y$에 기반하여 이 게이트 시퀀스의 기술(description)인 비트 문자열 $s_y$를 계산하는 불리언 오라클 $B$가 구축된다. 이 오라클은 Boolean 함수를 위한 LKS 기법을 사용하여 구현되며, $O(\sqrt{2^n \log(1/\varepsilon)})$의 $T$-count를 달성한다.
• 제어 적용 (Controlled Application): 실제 게이트는 계산된 문자열 $s_y$의 비트들에 의해 제어되어 타겟 큐비트에 적용된다. 이 단계의 비용은 $s_y$의 길이에 비례하여 $O(\log(1/\varepsilon))$이다.
• 역계산 (Uncomputation): 보조 큐비트를 제로 상태로 되돌리기 위해 오라클이 역계산된다.

2. 양자 상태 준비 (Quantum State Preparation)

상태 준비 알고리즘은 Grover-Rudolph 방법과 LKS 구성을 정교화한다:

• 거친 근사 (Coarse Approximation): $O(n)$개의 제어 회전(controlled rotations)이 필요한 표준 Grover-Rudolph 방식 대신, 저자들은 문제를 단 $O(1)$개의 대각 유니터리 합성으로 줄이는 최근 방법(Rosenthal, INN+22)의 변형을 사용한다. 두 개의 불리언 대각 유니터리($B_1, B_2$)와 Hadamard 레이어를 사용하여 타겟 $|\psi\rangle$와 상수 수준의 중첩(constant overlap)을 갖는 상태 $|\phi\rangle$를 구축한다.
• 반복적 정교화 (Iterative Refinement): 오차를 상수에서 $\varepsilon$으로 줄이기 위해, 저자들은 동일한 거친 근사 기법을 사용하여 차이 상태 $|\psi\rangle - |\phi\rangle$를 근사하는 반복적 접근 방식을 채택한다. 이는 일련의 상태 $|\phi_k\rangle$를 생성한다.
• 유니터리의 선형 결합 (Linear Combination of Unitaries, LCU): 최종 상태는 LCU 방법을 사용하여 이러한 거친 근사들의 가중치 합으로 준비된다.
• 진폭 증폭 (Amplitude Amplification): 중첩의 "정크(junk)" 성분을 걸러내기 위해 정확한 진폭 증폭이 사용되며, 이를 통해 최종 상태가 타겟에 $\varepsilon$-가깝게 보장된다. 이는 상수 번의 라운드 내에서 정확한 증폭이 가능하도록 "플래그(flagged)"된 상태의 진폭을 특정 값($\sin(\pi/10)$)으로 조정하는 것을 요구한다.

3. 하한 (Lower Bounds)

하한은 중간 회로 측정(mid-circuit measurements)과 고전적 피드포워드(classical feed-forward)를 허용하는 강력한 적응형 Clifford+T 회로(adaptive Clifford+T circuits) 모델에서 확립된다.

• 상태 준비로의 환원 (Reduction to State Preparation): 유니터리 합성에 대해, 회로가 최대 얽힘 상태(Choi state)에 작용하는 것을 고려함으로써 문제를 상태 준비로 환원한다.
• 계수 논증 (Counting Argument): 저자들은 구형 충전(sphere-packing) 논증을 사용한다. 그들은 오차 $\varepsilon$ 내에서 구별 가능한 상태(또는 유니터리)의 수가 $(1/\varepsilon)^{\Theta(2^n)}$으로 스케일링됨을 보여준다.
• 정형(Canonical Form): 주어진 $T$-count $t$로 달성 가능한 구별되는 회로의 수를 제한하기 위해 Pauli 사후 선택(postselection)이 포함된 Clifford 회로의 정형(Beverland 등의 연구 일반화)을 활용한다. 가용한 회로의 수와 구별 가능한 타겟의 수를 일치시킴으로써, 저자들은 하한 $t = \Omega(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon))$을 도출한다.

주요 기여 및 결과

주요 정리 (Main Theorems)

1. 최적 상태 준비 (Theorem 1.1):
   임의의 $n$-큐비트 상태는 $T$-count가 다음인 Clifford+T 회로를 사용하여 오차 $\varepsilon$까지 준비될 수 있다:
   $$\Theta\left(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon)\right)$$
   이 바운드는 측정이 있는 적응형 모델에서도 최적이다.

2. 최적 대각 유니터리 합성 (Theorem 1.2):
   임의의 $n$-큐비트 대각 유니터리는 동일한 최적 $T$-count를 사용하여 오차 $\varepsilon$까지 구현될 수 있다:
   $$\Theta\left(\sqrt{2^n \log(1/\varepsilon)} + \log(1/\varepsilon)\right)$$

3. 배치 합성 (Batched Synthesis, Theorem 1.3):
   $m = O(\log \log(1/\varepsilon))$개의 단일 큐비트 유니터리의 텐서 곱은 $T$-count $O(\log(1/\varepsilon))$로 구현될 수 있다. 이는 소수의 유니터리를 합성하는 것이 단일 유니터리의 비용을 초과하여 점근적 비용을 증가시키지 않음을 의미한다.

4. 대량 생산 (Mass Production, Theorem 1.4):
   단일 큐비트 유니터리 $U^{\otimes m}$의 $m$개 복사본을 구현하는 데는 $T$-count $O(m + \log(1/\varepsilon))$이 필요하다. 이는 이전 전략들이 $\log(m)$ 인자를 발생시켰던 것에 비해 개선된 최적의 결과이다.

선행 연구 대비 개선 사항

• 본 논문은 LKS 상태 준비 바운드에 존재하던 $O(\sqrt{n})$ 및 $O(\log n)$ 오버헤드를 제거하여 정보 이론적 하한을 달성했다.
• 대각 유니터리에 대한 $T$-count가 $O(\sqrt{2^n} \log(n/\varepsilon))$에서 $O(\sqrt{2^n \log(1/\varepsilon)})$로 개선되었다.

의의 및 주장

저자들은 양자 상태 준비 및 대 diagonal 유니터리 합성을 위한 최악의 경우(worst-case) $T$-count를 규명하였으며, 기존에 알려진 상한이 불필요한 오버헤드로 인해 타이트하지 않았음을 입증하였다.

• 최적성 (Optimality): 이 결과는 약한(유니터리) 모델에서의 상한과 강한(적응형) 모델에서의 일치하는 하한을 모두 제공하는 "양쪽의 장점(best of both worlds)"을 나타낸다.
• 자원 트레이드오프 (Resource Trade-offs): 이 구성은 보조 큐비트 수와 $T$-count 사이의 거의 최적의 트레이드오프를 달성하지만, 정확한 최적의 트레이드오프는 여전히 미해결 과제로 남아 있다.
• 응용 분야 (Applications): 개선된 바운드는 매직 상태의 스테빌라이저 랭크(stabilizer rank) 및 불리언 함수의 분해에 대한 하한을 약간 개선한다. "대량 생산" 결과는 서로 다른 유니터리를 합성하는 것보다 동일한 유니터리를 합성하는 것이 훨씬 더 저렴하다는 점을 강조하는 특정 응용 사례로 제시된다.

본 논문은 $T$-count는 이제 최적이지만, Clifford 게이트의 수는 여전히 $O(2^n \log(1/\varepsilon))$이며, 이는 최적인 $\Omega(2^n/n)$에는 가깝지만 아직 일치하지는 않는다고 명시한다. 또한, 일반적인 (비-대각) $n$-큐비트 유니터리에 대한 최적의 $T$-count는 하한 $\tilde{\Omega}(2^n)$과 최선의 알려진 상한 $\tilde{O}(2^{1.5n})$ 사이의 간극이 존재하는 미해결 문제로 남아 있다.