The power of constant-depth quantum circuits of unbounded size

기술 요약: 무제한 크기의 상수 깊이 양자 회로의 위력

문제 정의
본 논문은 회로 크기와 보조 공간(ancillary space)에 대한 제한을 제거했을 때 양자 회로가 갖는 계산 능력을 조사한다. 고전적 복잡도 이론에서 $AC^0$ 클래스(무제한 팬인(fan-in) AND/OR 게이트를 가진 상수 깊이 회로)는 패리티(parity)를 계산할 수 없다. 그러나 다항식 크기 제한이 해제된다면, 디스정규형(Disjunctive Normal Form, DNF) 구성을 통해 모든 불리언 함수를 상수 깊이 내에서 계산할 수 있다. 저자들은 이와 유사한 현상이 임의의 단일 큐비트 게이트와 일반화된 토폴리(Toffoli) 게이트로 구성된 양자 회로($QAC^0$)에서도 발생하는지 묻는다. 즉, 회로 크기와 보조 큐비트의 수가 제한되지 않는다면 모든 유니터리 연산을 상수 깊이 내에서 정확하게 구현할 수 있는가?

저자들은 다음의 네 가지 단계적으로 일반화된 과제를 통해 이 질문을 탐구한다:

1. 임의의 집합 $L \subseteq \{0, 1\}^n$에 대한 멤버십 계산.
2. 계산 기저 상태(computational basis states)의 임의의 치환(permutation) 구현.
3. 임의의 순수 양자 상태 준비.
4. 모든 입력 상태에 대해 임의의 유니터리 연산 구현.

방법론
저자들은 가역적 고전 회로 구성, 양자 영역으로 적응된 확률적 고전 기법, 그리고 양자 텔레포테이션 프로토콜의 조합을 사용한다.

• 가역적 고전 구성: 저자들은 먼저 임의의 비트열 치환이 토폴리 및 팬아웃(fanout) 게이트를 사용하여 상수 깊이 내에서 구현될 수 있음을 입증한다. 이는 "지표 인코딩(indicator encoding)" 방식을 통해 달성된다: 입력은 정확히 하나의 엔트리만이 1인 $2^n$ 차원의 지표 벡터로 매핑되고, 조작된 후, 다시 원래의 문자열로 디코딩된다. 이를 통해 가능한 모든 입력 문자열을 병렬적으로 평가할 수 있다.
• 확률적 기법의 양자적 적응: 임의의 확률 분포와 순수 양자 상태를 준비하기 위해, 저자들은 고전적인 확률적 구성을 채택한다. 이는 첫 번째 '1'의 위치에 따라 분포를 인코딩하도록 비트들을 독립적으로 샘플링하는 과정을 포함한다. 양자 설정에서, 이는 중첩을 파괴하지 않으면서 첫 번째 '1' 이후의 큐비트들을 $|0\rangle$로 되돌리기 위해 역회전(inverse rotations)을 적용함으로써 코히어런트(coherent)하게 만들어진다.
• 게이트 세트 확장: 주요 게이트 세트는 단일 큐비트 게이트와 일반화된 토폴리 게이트를 포함하지만, 저자들은 개념적 도구로서 팬아웃 게이트를 활용한다. 저자들은 Grier, Morris, Wu [GMW26] 및 Rosenthal [Ros20]의 결과를 인용하여, 팬아웃이 기본 게이트 세트만을 사용하여 상수 깊이 내에서 정확하게 구현될 수 있음을 보여준다. 다만, 이 과정에서 회로 크기가 이중 지수(doubly exponential) 경계까지 증가할 수 있다.
• 유니터리 구현을 위한 축약(Reductions): 임의의 유니터리 구현을 위해, 저자들은 직접적인 구성을 제공하는 대신 여러 동등한 정식화와 축약을 제안한다. 여기에는 다음을 유니터리 구현으로 축약하는 것이 포함된다:
  • 특정 직교 기저 벡터들의 클로닝(cloning).
  • 기저 벡터 리스트의 치환.
  • 기저 레이블의 디코딩.
  • 단위 행 및 열 합을 갖는 유니터리 구현 (Idel-Wolf normal form을 통해).
  • 무트레이스(traceless) 유니터리 인볼루션 구현 (하나의 추가적인 클린 큐비트 사용).
• 포트 기반 텔레포테이션 (PBT): 특정 게이트에 의존적인 유니터리 보정을 피하며 임의의 유니터리를 구현하기 위해, 저자들은 포트 기반 텔레포테이션(PBT)을 활용한다. 저자들은 최대 얽힘 상태(또는 대상 유니터리의 Choi 상태)와 결합 측정, 그리고 포트 선택을 사용하여 PBT를 수행하는 유니터리 회로를 구축한다.

주요 기여 및 결과

1. 특정 과제에 대한 정확한 상수 깊이 구성:

   • 치환: 임의의 비트열 치환은 $O(n2^n)$개의 게이트와 보조 큐비트를 사용하여 상수 깊이(깊이 $\le 20$) 내에서 구현 가능하다.
   • 대각 유니터리 (Diagonal Unitaries): 임의의 대각 유니터리는 지표를 계산하고, 병렬로 위상을 적용한 뒤, 언컴퓨팅(uncomputing) 과정을 거쳐 상수 깊이(깊이 7) 내에서 구현 가능하다.
   • 상태 준비: 임의의 순수 양자 상태는 $O(4^n)$개의 큐비트와 $O(n2^n)$개의 게이트를 사용하여 상수 깊이(깊이 $\le 37$) 내에서 준비될 수 있다. 모든 보조 큐비트는 제로 상태로 되돌려진다.
   • 팬아웃 구현: 팬아웃은 단일 큐비트 및 일반화된 토폴리 게이트만을 사용하여 상수 깊이 내에서 정확하게 구현될 수 있으나, 이는 이중 지수 크기를 요구할 수 있다.

2. 임의의 유니터리를 위한 축약:
   본 논문은 임의의 유니터리를 상수 깊이 내에서 구현하는 것이 여러 특정 연산(예: 기저 벡터 클로닝, 레이블 디코딩, 또는 무트레이스 인볼루션 구현)을 구현하는 것과 동등함을 입증한다. 이는 임의의 유니터리 구현이라는 미해결 문제를 일련의 동등한 구조적 과제로 재구성한다.

3. 적응형 측정 및 게이트 텔레포테이션:
   저자들은 적응형 중간 측정이 허용될 경우, 클리퍼드 계층(Clifford hierarchy)의 레벨 $\ell$에 있는 임의의 게이트가 깊이 $O(\ell)$ 내에서 구현될 수 있음을 보여준다. 또한, 적응형 모델에서 임의의 유니터리 구현은 무트레이스 유니터리 인볼루션을 구현하는 문제로 축약된다.

4. 포트 기반 텔레포테이션 근사:
   저자들은 입력 차원 $d$와 $M \ge d^2 - 1$개의 포트에 대한 포트 기반 텔레포테이션(PBT)을 위한 유니터리 회로를 구축한다.

   • 깊이: 회로 깊이는 $O(\sqrt{d})$이며, 이는 포트의 수 $M$과는 독립적이다.
   • 충실도 (Fidelity): 얽힘 충실도는 $F_e \ge (1 - \frac{d^2-1}{2M})^2$로 제한된다.
   • 정확도 vs 깊이: 고정된 입력 차원 $d$에 대해, $M$을 늘림으로써 회로 깊이를 증가시키지 않고도 근사를 임의의 정밀도로 높일 수 있다. 그러나 입력 차원 $d$에 대한 의존성은 여전히 남아 있다. 즉, $d$에 독립적인 깊이 경계를 달성할 수 있는지 여부는 미해결 과제로 남아 있다.
   • 구현: 이 회로는 단일 큐비트 및 일반화된 토폴리 게이트만을 사용하며, 중간 측정을 필요로 하지 않는다.

의의 및 주장
본 논문은 크기와 보조 공간의 제한을 제거하면 상수 깊이 양자 회로가 다항식 크기의 상수 깊이 모델에서는 일반적으로 불가능한 작업들(예: 임의의 상태 준비 및 기저 상태의 치환)을 수행할 수 있음을 확립한다. 이는 양자 상태 준비를 가역적 고전 계산 및 확률 분포 준비와 직접 연결한다.

그러나 임의의 유니터리 구현에 대해서는 신중한 입장을 유지한다. 저자들은 치환, 대각 유니터리, 상태 준비에 대한 정확한 상수 깊이 구성을 제공하지만, 일반적인 유니터리 구현은 여전히 미해결 문제로 남겨둔다. 저자들은 이 문제에 대한 동등한 특징들을 제공하지만 이를 해결하지는 않는다.

일반적인 유니터리에 관한 주요 기여는 PBT 구성이다. 저자들은 고정된 입력 차원 $d$에 대해, 포트의 수를 늘림으로써 회로 깊이를 증가시키지 않고도 임의의 유니터리를 임의의 정밀도로 근사할 수 있음을 보여준다. 그러나 이 구성의 깊이는 $d$에 따라 $O(\sqrt{d})$로 스케일링된다. 저자들은 $d$에 대한 이러한 의존성을 제거할 수 있는지(즉, $d$에 독립적인 깊이 경계를 달성할 수 있는지)가 여전히 미해결 과제임을 명시한다. 본 연구는 상수 깊이 유니터리 구현의 근본적인 어려움이 고정된 입력으로부터 임의의 출력을 만들어내는 데 있는 것이 아니라, 유니터리성을 유지하면서 모든 입력 상태에 대한 작용을 규정하는 데 있음을 강조한다.