Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$

기술 요약: $\mathsf{QAC}^0$ 내 대칭적 불리언 함수의 팬아웃 복잡도

문제 정의
$\mathsf{QAC}^0$ (임의의 단일 큐비트 게이트와 다중 제어 Toffoli 게이트를 사용하는 상수 깊이, 다항 크기 양자 회로) 클래스의 핵심 미해결 질문은 이 클래스가 $\mathsf{FANOUT}_n$ 연산을 구현할 수 있는지 여부이다. 고전 회로에서 팬아웃은 비용이 들지 않지만, 양자 회로에서 하나의 큐비트로부터 $n$개의 타겟으로 고전 정보를 복사하는 것은 비자명한 자원이다. $\mathsf{FANOUT}_n$은 Hadamard 공액(conjugation) 하에서 $\mathsf{PARITY}_n$ 함수와 동등하므로, $\mathsf{QAC}^0 = \mathsf{QAC}^0_f$ (여기서 $\mathsf{QAC}^0_f := \mathsf{QAC}^0[\mathsf{FANOUT}_n]$)인지 결정하는 것은 $\mathsf{PARITY}_n \in \mathsf{QAC}^0$인지를 결정하는 것과 같다.

일반적인 경우에 대해서는 여전히 열려 있으나, 최근 Dicke 상태 준비에 관한 연구는 대칭적 함수를 계산하는 난이도가 필요한 팬아웃 게이트의 크기와 상관관계가 있을 수 있다는 더 세밀한 관점을 제시했다. 본 논문은 다음의 일반적인 질문을 다룬다: 임의의 대칭 불리언 함수 $f$에 대하여, $\mathsf{QAC}^0$ 내에서 이를 계산하기 위해 필요한 팬아웃 크기는 얼마인가?

방법론
저자들은 대칭 함수를 위한 구조적 파라미터인 전이 반경(transition radius), $\rho(f)$를 도입한다. 대칭 함수 $f$에 대하여, $\Delta f$를 해밍 가중치(Hamming weight) $i$와 $i+1$ 사이에서 함수의 값이 변하는 인덱스들의 집합이라고 하자. 전이 반경은 다음과 같이 정의된다:
$$\rho(f) := \max_{i \in \Delta f} \min\{i + 1, n - i\}$$
직관적으로, $\rho(f)$는 가장 "안쪽"에 있는 전이가 해밍 가중치 구간의 가장 가까운 끝단으로부터 떨어진 거리를 측정한다.

본 논문은 $\mathsf{QAC}^0$ 환원(reduction) 하에서 대칭 함수 $f$를 계산하는 것과 $\mathsf{FANOUT}_{\rho(f)}$를 구현하는 것 사이의 정밀한 동등성을 확립한다. 증명은 두 방향으로 진행된다:

1. 팬아웃에서 대칭 함수로:
   저자들은 $\rho(f) = k$인 모든 대칭 함수를 계산하기 위해 $\mathsf{FANOUT}_k$가 충분하다는 것을 보여준다. 이러한 함수의 모든 전이는 처음 $k$개 또는 마지막 $k$개 해밍 가중치 층 이내에서 발생하므로, 이 함수는 최대 $2k$개의 "정확한 가중치" 술어($\mathsf{EXACT}_j$)의 논리합(OR)으로 표현될 수 있다. $\mathsf{FANOUT}_k$를 사용하여, 회로는 입력의 $2k$개 복사본을 병렬로 생성하고, 필요한 $\mathsf{EXACT}_j$ 술어들을 평가하며($이들은$\mathsf{QAC}^0[\mathsf{FANOUT}_k]$에 속함이 알려져 있음), 이를 단일 OR 게이트로 결합할 수 있다.

2. 대칭 함수에서 팬아웃으로:
   역으로, 저자들은 만약 $\mathsf{QAC}^0$ 회로가 최악의 경우 확률 $1/2 + 1/\text{polylog}(n)$ 이상으로 대칭 함수 $f$를 계산한다면, $\mathsf{FANOUT}_k$를 구현할 수 있음을 입증한다.

   • 증명은 해밍 가중치 스펙트럼의 중심부에서의 전이를 격리하기 위해 $m = 2k-1$개의 입력 비트로 회로를 제한한다.
   • 제한된 회로의 연관 실수 함수 $g$를 분석한다. 회로가 높은 확률로 $f$를 계산한다는 조건은 인접한 해밍 가중치를 가진 입력 $x, y$에 대해 $|g(x) - g(y)|$의 하한을 의미한다.
   • 이 차이는 함수의 총 영향력(total influence)에 대한 하한으로 이어지며, 이는 Parseval의 항등식과 Fact 6을 통해 고차수(high degree)에서의 유의미한 "푸리에 꼬리(Fourier tail)"(고차수에서의 질량)를 함의한다.
   • 저자들은 충분한 고차수 푸리에 질량을 가진 회로를 $\mathsf{FANOUT}_\ell$ 회로로 변환할 수 있다는 Gretta, Gupta, Joshi [GGJ26a]의 푸리에 꼬리 환원 결과를 활용한다.
   • 마지막으로, 유도된 팬아웃 크기 $\ell$이 상수 깊이 트리(constant-depth tree)를 통해 $\mathsf{FANOUT}_k$를 구성하기에 충분함을 보여준다.

주요 결과
주요 정리는 임의의 대칭 불리언 함수 $f$에 대해 다음의 동등성을 확립한다:
$$f \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_{\rho(f)} \in \mathsf{QAC}^0$$
더 구체적으로:

1. 만약 $f$가 확률 $1/2 + 1/\log^c n$으로 $\mathsf{QAC}^0$ 회로에 의해 계산될 수 있다면, $\mathsf{FANOUT}_{\rho(f)}$는 $\mathsf{QAC}^0$ 회로에 의해 구현될 수 있다.
2. 만약 $\mathsf{FANOUT}_{\rho(f)}$가 $\mathsf{QAC}^0$ 회로에 의해 구현될 수 있다면, $f$는 $\mathsf{QAC}^0$ 회로에 의해 정확하게 계산될 수 있다.

따름정리 및 시사점

• 큰 전이 반경에 대한 완전성: 만약 어떤 상수 $\delta > 0$에 대하여 $\rho(f) \ge n^\delta$라면, $f$를 계산하는 것(지정된 확률로)은 $\mathsf{QAC}^0_f$-완전(complete)이다. 이는 $\mathsf{FANOUT}_{\rho(f)}$를 상수 깊이 트리로 반복하여 $\mathsf{FANOUT}_n$을 구현할 수 있기 때문이다. 이 결과는 $\mathsf{PARITY}$, $\mathsf{MAJORITY}$, $\mathsf{THRESHOLD}$, $\mathsf{MOD}_q$에 대한 기존의 완전성 결과들을 통합하고 일반화한다.
• 근사 차수(Approximate Degree)와 대칭성: 근사 차수에 관한 Paturi의 정리($\widetilde{\deg}(f) = \Theta(\sqrt{n\rho(f)})$)와 본 결과의 결합을 통해, 저자들은 $\mathsf{QAC}^0$ 내의 함수들에 대한 제약 조건을 도출한다. 구체적으로, 만약 $\mathsf{PARITY}_n \notin \mathsf{QAC}^0$라면, 근사 차수가 $\Omega(n^{1/2+\eta})$인 $\mathsf{QAC}^0$ 내의 모든 함수는 **비대칭적(nonsymmetric)**이어야 한다. 이는 그러한 차수를 가진 대칭 함수는 다항식 크기의 전이 반경을 가지게 되어 $\mathsf{QAC}^0_f$-완전(즉, $\mathsf{PARITY}_n$과 동등)해지기 때문이다.

의의
본 논문은 $\mathsf{QAC}^0$ 내 전체 대칭 불리언 함수 클래스에 대한 팬아웃 복잡도를 완전히 규명한다. 이는 전이 반경을 정확한 임계값으로 식별함으로써 대칭 함수에 대한 팬아웃 문제의 "전부 아니면 전무(all-or-nothing)" 성격을 해결한다. 이 연구는 특정 함수들($\mathsf{PARITY}$ 및 $\mathsf{MAJORITY}$ 등)에 대한 알려진 결과들을 특수한 경우로 회복하며, 근사적 계산(확률 $1/2 + 1/\text{polylog}(n)$)조차도 큰 전이 반경을 가진 함수들에 대해 팬아웃 문제의 완전성을 촉발하기에 충분하다는 점을 보여줌으로써 이전의 결과들을 강화한다. 나아가, $\mathsf{PARITY}$ 문제를 대칭 함수의 구조적 특성과 직접 연결함으로써 $\mathsf{QAC}^0$의 고차수 대칭 함수에 대한 한계에 대한 새로운 관점을 제공한다.