Super-Constant Weight Dicke States in Constant Depth Without Fanout

1. 문제 정의 (Problem Statement)

• 디케 상태 (Dicke States): $n$-큐비트 디케 상태 $|D_n^k\rangle$ 는 해밍 무게 (Hamming weight) 가 $k$ 인 모든 $n$-비트 문자열의 균일 중첩 (uniform superposition) 으로 정의됩니다. 이는 양자 계측, 비국소성 테스트, 디코딩 양자 간섭 (DQI) 등 다양한 분야에서 중요한 얽힘 자원입니다. 또한, 모든 대칭 상태 (symmetric state) 는 디케 상태들의 중첩으로 표현될 수 있습니다.
• 회로 복잡도 모델 (QAC0): QAC0 는 상수 깊이 (constant depth) 와 다항식 크기 (polynomial size) 를 가진 양자 회로 모델로, 다중 큐비트 Toffoli 게이트와 단일 큐비트 유니터리 게이트로 구성됩니다. 이는 고전적인 AC0 의 양자 버전입니다.
• 핵심 난제:
  • $k = O(1)$ (상수 무게) 인 디케 상태는 QAC0 에서 준비 가능한 것으로 알려져 있습니다.
  • 그러나 $k = \omega(1)$ (초상수, 예: $k = \text{polylog}(n)$) 인 경우, 기존의 상수 깊이 구성은 FANOUT$_n$ (한 비트를 $n$ 개로 복제하는 연산) 게이트에 의존했습니다.
  • QAC0 가 FANOUT$_n$ 을 구현할 수 있는지 여부는 양자 회로 복잡도에서 열린 문제이며, FANOUT$_n$ 없이는 상수 깊이에서 디케 상태를 만드는 것이 불가능할 것으로 추측되었습니다.
  • 최근 연구 [GGJ26] 는 $k$-무게 디케 상태 준비에 FANOUT$_k$ 가 필요하다는 하한선 (lower bound) 을 증명했으나, FANOUT$_k$ 만으로 $n$-큐비트 디케 상태를 만들 수 있는지 (상한선) 에 대해서는 알려지지 않았습니다.

2. 방법론 (Methodology)

저자들은 FANOUT$_n$ 대신 FANOUT$_k$ 만 사용하여 $n$-큐비트 디케 상태 $|D_n^k\rangle$ 를 상수 깊이로 정확히 (exactly) 준비하는 새로운 구성을 제시합니다. 주요 기술적 접근법은 다음과 같습니다.

2.1. 버킷 (Bucket) 전략 및 확률적 근사

• $n$개의 타겟 큐비트를 $\ell \approx k^3$ 개의 '버킷' (각 버킷 크기 $m = n/\ell$) 으로 분할합니다.
• 먼저 $\ell$개의 보조 큐비트 (ancilla) 위에 $|D_\ell^k\rangle$ 상태를 준비합니다. 이는 각 버킷이 최대 하나의 '1'을 가지는 상태를 의미합니다.
• 각 버킷의 보조 큐비트가 1 일 때, 해당 버킷 내의 $m$개 타겟 큐비트를 $|W_m\rangle$ (W 상태) 로 매핑합니다.
• 생일 역설 (Birthday Paradox) 활용: $\ell = \omega(k^2)$ 이므로, 무작위로 선택된 $k$개의 '1'이 서로 다른 버킷에 분포할 확률이 매우 높습니다. 따라서 이 방법은 $|D_n^k\rangle$ 과 일정한 충실도 (constant fidelity) 를 가지며, 일부 문자열 (같은 버킷에 1 이 두 개 이상 있는 경우) 만 누락됩니다.

2.2. 누락된 문자열 복원 및 진폭 조정

• 위 방법의 한계는 모든 해밍 무게 $k$ 문자열이 균일한 진폭을 갖지 못한다는 점입니다.
• 일반화된 매핑: 각 버킷이 1 개 이상의 '1'을 가질 수 있도록 확률 분포 $s(1), \dots, s(k)$ 를 도입한 매핑을 설계합니다. 이는 이항 분포 (Binomial distribution) 와 유사한 분포를 생성하도록 조정됩니다.
• 진폭 보정 (Amplitude Adjustment):
  • 생성된 상태가 모든 무게 $k$ 문자열에 대해 동일한 진폭을 갖도록 하기 위해, 특정 확률 분포 $t(j)$ (비어 있지 않은 버킷 수 $j$에 대한 분포) 와 $s(i)$ 를 정밀하게 설정합니다.
  • Grover 증폭 (Amplitude Amplification): 생성된 상태가 $|D_n^k\rangle$ 과 일정한 중첩을 가지도록 설계된 후, EXACT$_k$ 게이트를 사용하여 무게가 정확히 $k$인 문자열을 마킹하고 Grover 증폭을 적용하여 $|D_n^k\rangle$ 을 정확히 추출합니다.

2.3. 제어된 연산 및 FANOUT 활용

• 제한된 FANOUT primitives: FANOUT$_k$ 게이트를 사용하여 제어된 유니터리 연산 (Controlled-unitaries) 과 진폭 조절을 수행하는 새로운 원시 연산자 (primitives) 를 개발했습니다.
• 대칭 상태 일반화: 이 기법은 특정 무게 $k$의 디케 상태뿐만 아니라, 해밍 무게가 $k$ 이하인 임의의 대칭 상태 (Dicke 상태들의 중첩) 로 확장됩니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

3.1. FANOUT$_k$ 를 이용한 디케 상태 준비

• 정리 1.1: 모든 $n$과 $k \le n/2$에 대해, $|D_n^k\rangle$ 및 $|D_n^{n-k}\rangle$ 는 FANOUT$_k$ 게이트를 가진 QAC0 회로 (QAC0[FANOUT$_k$]) 로 상수 깊이와 다항식 보조 큐비트를 사용하여 정확히 준비할 수 있습니다.
• 다항식 로그 무게 (Poly-log weight): $k = \text{polylog}(n)$ 인 경우, FANOUT$_k$ 는 QAC0 내에서 구현 가능하므로, FANOUT$_n$ 없이도 $|D_n^k\rangle$ 을 순수 QAC0 (다중 Toffoli 게이트 및 단일 큐비트 유니터리만 사용) 로 상수 깊이에 준비할 수 있습니다. (Corollary 1.2)

3.2. 디케 상태와 FANOUT 의 동치성

• 정리 1.3 (동치성): 임의의 $n$과 $k \le n/2$에 대해, $|D_n^k\rangle$ 이 QAC0 에서 준비 가능한 것은 FANOUT$_k \in \text{QAC0}$ 일 때와 동치입니다.
  • 이는 기존 연구 [GGJ26] 의 하한선 (FANOUT$_k$ 필요) 과 본 논문의 상한선 (FANOUT$_k$ 만으로 충분) 을 결합하여, 디케 상태 준비의 복잡도가 FANOUT 게이트의 폭 (width) 에 의해 완전히 결정됨을 보여줍니다.

3.3. 임의의 대칭 상태 준비

• 정리 1.4: 해밍 무게가 $k$ 이하인 임의의 $n$-큐비트 대칭 상태 $|\psi\rangle$ 는 FANOUT$_k$ 를 가진 QAC0 회로로 상수 깊이에 정확히 준비 가능합니다.
• Corollary 1.5: FANOUT$_n$ 을 지원하는 하드웨어 (예: 트랩드 이온의 전역 얽힘 연산) 에서는 임의의 대칭 상태를 상수 깊이로 준비할 수 있는 최초의 단위 (unitary) 구성을 제공합니다.

4. 의의 및 중요성 (Significance)

1. 복잡도 이론적 기여: QAC0 와 QAC0$^f$ (FANOUT 포함) 의 관계를 명확히 했습니다. 특히, 디케 상태 준비가 FANOUT$_k$ 의 구현 가능성과 동치임을 증명함으로써, 얽힘 자원 생성의 복잡도가 고전적 복사 연산 (Fanout) 의 복잡도와 밀접하게 연결됨을 보여주었습니다.
2. NISQ 및 양자 하드웨어:
   • 트랩드 이온 (Trapped Ions) 등 전역 얽힘 (Global Entangling) 연산을 지원하는 하드웨어는 FANOUT$_n$ 을 자연스럽게 구현할 수 있습니다. 이 논문은 이러한 하드웨어에서 임의의 대칭 상태를 상수 깊이로 준비할 수 있음을 보여주어, NISQ 시대의 알고리즘 구현에 중요한 통찰을 제공합니다.
   • FANOUT$_n$ 이 제한된 아키텍처에서도 $k = \text{polylog}(n)$ 인 디케 상태를 효율적으로 생성할 수 있는 방법을 제시했습니다.
3. 기술적 혁신: 기존의 Grover 증폭이나 병렬 증폭 기법의 한계를 극복하고, '버킷' 분할 전략과 정교한 진폭 조정을 결합하여 상수 깊이 회로를 설계한 것은 양자 회로 설계 분야에서 중요한 기술적 진전입니다.

결론

이 논문은 FANOUT$_n$ 없이도 FANOUT$_k$ 만으로 $n$-큐비트 디케 상태와 임의의 대칭 상태를 상수 깊이에 준비할 수 있음을 증명했습니다. 이는 양자 회로 복잡도 이론에서 FANOUT 게이트의 역할을 재정의하며, 특정 하드웨어 아키텍처에서 복잡한 얽힘 상태를 효율적으로 생성하는 새로운 길을 열었습니다.