2-Fold Forrelation is in QAC$^0$

기술 요약: 2-Fold Forrelation은 QAC0에 속한다

문제 정의
본 논문은 얕은 양자 회로 복잡도(shallow quantum circuit complexity)의 핵심적인 미해결 문제인, Parity 함수가 $\mathsf{QAC}^0$(임의의 단일 큐비트 게이트와 일반화된 Toffoli 게이트를 사용하는 상수 깊이 양자 회로)에 속하는지 여부를 다룬다. 이 질문은 $\mathsf{QAC}^0$가 무제한 양자 팬아웃(unbounded quantum fan-out)을 구현할 수 있는지 결정하는 문제와 동치이다. Parity는 고전적 클래스 $\mathsf{AC}^0$(무제한 팬인 AND/OR/NOT 게이트를 사용하는 다항식 크기, 상수 깊이 회로)의 범위를 벗어나는 것으로 알려져 있으나, $\mathsf{QAC}^0$가 자연스러운 결정 문제(natural decision problems)에 대해 $\mathsf{AC}^0$와 분리될 수 있는지는 아직 알려지지 않았다.

저자는 양자 및 무작위 쿼리 복잡도 사이의 큰 격차를 보여주기 위해 도입된 약속 문제(promise problem)인 2-fold Forrelation에 집중한다. 두 개의 $N$-비트 문자열 $x, y$ (여기서 $N=2^m$)가 주어졌을 때, 이 문제는 2-fold Forrelation 값 $\text{Forr}_N(x, y)$가 클 때(적어도 $\delta$)와 작을 때(최대 $\delta/2$)를 구별하는 것을 묻는다. Forrelation을 위한 표준 양자 알고리즘은 이진 주소 지정 위상 오라클(binary-addressed phase oracle)을 사용하는데, 이는 입력 비트의 코히어런트 인덱싱(coherent indexing)을 요구한다. 그러나 입력이 오라클을 통하지 않고 와이어(wires)로서 명시적으로 제공되는 회로 모델에서는, 무제한 팬아웃 없이 이러한 인덱싱을 구현하는 것이 알려진 병목 현상이다.

방법론
저자는 모든 약속된 입력을 만족하는 입력에 대해 유계 오차(bounded error)로 2-fold Forrelation을 해결하는 다항 크기의 상수 깊이 $\mathsf{QAC}^0$ 회로를 구성한다. 이 구성은 이진 주소를 원-핫(one-hot) 표현으로 변환하는 병목 현상(무제한 팬아웃이 필요한 과정)을 피하기 위해, 직접 **원-핫 표현(one-hot representation)**에서 동작한다.

방법론은 크게 두 단계로 진행된다:

1. One-Hot Forrelation 테스트:

   • 이진 주소를 원-핫으로 변환하는 대신, 회로는 $N$-큐비트 W 상태($|W_N\rangle$)가 $\mathsf{QAC}^0$ 내에서 정확하게 준비될 수 있다는 사실을 활용한다.
   • 입력 문자열 $x$에 대하여, 회로는 위상이 인코딩된 W 상태 $|W_x\rangle = \frac{1}{\sqrt{N}} \sum_u (-1)^{x_u} |\text{oh}(u)\rangle$를 준비한다. 이는 코히어런트 룩업(coherent lookup)을 피하기 위해 입력 비트와 W 상태 레지스터 사이의 서로 소인 제어-Z(controlled-Z) 게이트를 사용하여 횡단적으로(transversally) 수행된다.
   • Walsh–Hadamard 간섭 패턴($(-1)^{u \cdot v}$)을 구현하기 위해, 회로는 "원-핫-투-바이너리" 라벨 추출을 수행한다. 정확한 폴리로그 팬아웃(알려진 $\mathsf{QAC}^0$ 프리미티브)을 사용하여, 회로는 원-핫 레지스터 $|\text{oh}(u)\rangle$로부터 이진 라벨 $u$를 보조 레지스터로 추출하고, 도트 곱(dot product) 위상을 계산하기 위해 제어-Z 게이트를 적용한 후 라벨을 다시 되돌린다(uncompute).
   • 결과 상태를 W 상태로 투영하면 수락 확률은 $\text{Forr}_N(x, y)^2 / N$에 비례하게 된다.

2. 위상-상태 반복을 통한 증폭 (Amplification via Phase-State Repetition):

   • 단일 테스트의 성공 확률은 $N$에 따라 소멸한다. 일정한 간격(constant gap)을 확보하기 위해, 회로는 $R = \Theta(N/\delta^2)$개의 복사본을 병렬로 실행해야 한다.
   • $|W_x\rangle^{\otimes R}$을 직접 준비하는 방식은 각 입력 비트가 $R$개의 게이트로 팬아웃되어야 하므로, 무제한 팬아웃 없이는 $\mathsf{QAC}^0$에서 불가능하다.
   • 저자는 위상-상태 반복 구성(Grier–Morris–Wu에서 변형됨)을 채택한다. 이 기법은 만약 $C_a$개의 복사본이 주소 $a$를 점유하고 있다면, 입력 비트 $x_a$의 총 위상 기여도가 $(-1)^{x_a (C_a \mod 2)}$가 된다는 점을 관찰한다.
   • 회로는 절단된 패리티(truncated parity) 함수(해밍 무게가 폴리로그 차단값 미만일 때만 패리티를 계산하는 함수)를 사용하여 점유 횟수 $C_a$의 패리티를 계산한다. 이 차단 범위를 초과할 확률은 무시할 수 있을 정도로 작기 때문에, 절단된 패리티는 오류를 최소화하면서 올바른 위상을 재현하는 데 충분하다. 이를 통해 회로는 단 하나의 입력 복사본만을 사용하여 $R$개의 유효한 테스트를 시뮬레이션함으로써 상수 깊이를 유지할 수 있다.

주요 기여 및 결과

• 상한선 (Upper Bound): 본 논문은 역-폴리로그 약속 간격($\delta \ge \text{polylog}^{-c}(N)$)을 가진 2-fold Forrelation이 $\mathsf{Promise\text{-}BQAC}^0$에 속함을 증명한다. 이 회로는 상수 깊이를 가지며 $N$에 대한 다항 크기를 갖는다 (단, 주소 길이 $m = \log N$에 대해서는 지수적이다).
• 분리 (Separation): 알려진 고전적 하한선(Bansal–Sinha, Tal)과 결합하여, 저자는 다음과 같은 결정 분리를 확립한다:
  $$\text{ConstGap2Forr} \in (\mathsf{Promise\text{-}BQAC}^0 \cap \mathsf{Promise\text{-}TC}^0) \setminus \mathsf{Promise\text{-}AC}^0$$
  이는 $\mathsf{QAC}^0$가 동일한 명시적 입력 형태를 받을 때, 상수 깊이 무작위 $\mathsf{AC}^0$ 회로에 대해 지수적 크기를 요구하는 문제를 해결할 수 있음을 보여준다.
• 기술적 참신함: 본 연구는 원-핫 기저에서 작업하고 절단된 패리티 증폭을 활용함으로써, 명시적 입력 모델에서 Forrelation 해결을 가로막는 "팬아웃 병목 현상"을 우회할 수 있음을 입증한다.

의의
본 논문은 표준적인 단일 복사 입력 모델(single-copy input model) 하에서 $\mathsf{QAC}^0$와 $\mathsf{AC}^0$ 사이의 자연스러운 약속 문제 분리를 제공한다. 복제된 입력(replicated inputs)을 사용하여 (사실상 팬아웃 자원을 공급하는 것과 같은) 분포적 보장을 활용했던 이전의 분리들과 달리, 이 결과는 정형화된 문제(Forrelation)에 대해 점별(pointwise) 분리를 제공한다.

저자는 자신의 결과를 Grier–Morris–Wu(복제된 입력을 사용하여 $\mathsf{QAC}^0$와 $\mathsf{AC}^0[p]$를 분리함) 및 Gretta–Gupta–Joshi(단일 복사 입력에 대해 Majority의 높은 상관관계를 보여줌)의 최근 연구와 대조하며 위치시킨다. 본 연구는 Forrelation을 위해 단일 복사 입력을 사용하여 모든 약속된 입력에 대해 유계 오차의 정확성을 달 achieve 함으로써 이를 보완한다. 이 결과는 $\mathsf{QAC}^0$가 아직 Parity(또는 무제한 팬아웃)를 포함한다고 확언할 수는 없더라도, 문제 구조가 원-핫 인코딩과 절단된 패리티 증폭을 허용한다면 특정 상관 관계 기반 문제들을 해결할 수 있는 충분한 능력을 갖추고 있음을 시사한다.