A log-depth in-place quantum Fourier transform that rarely needs ancillas

기술 요약: 보조 큐비트가 거의 필요 없는 로그 깊이의 인플레이스 양자 푸리에 변환

문제 정의
특정 유니터리를 위한 양자 회로를 설계할 때는 자원 제약(깊이, 큐비트 수, 국소성)과 근사 오차 사이의 균형을 맞추는 것이 중요하다. 전통적인 접근 방식은 모든 가능한 입력 상태에 대해 낮은 오차로 유니터리를 근사하도록 요구된다. 그러나 이러한 "최악의 경우(worst-case)" 보장을 달성하려면 많은 수의 보조 큐비트, 장거리 게이트 또는 깊은 회로와 같은 상당한 자원이 필요하다. 예를 들어, 이전의 로그 깊이 양자 푸리에 변환(QFT) 구조들은 $O(n)$ 개의 보조 큐비트, 장거리 연결성 또는 측정 기반 피드포워드(measurement-based feedforward)를 요구했다. 저자들은 더 큰 알고리즘 내의 많은 응용 분야에서는 모든 입력에 대해 완벽한 보장을 달하는 것보다, "나쁜" 입력(오차가 높은 입력)이 드물거나 축소를 통해 처리될 수 있다면 대부분의 입력에 대해 좋은 근사를 달성하는 것으로 충분하다고 주장한다.

방법론
본 논문은 "낙관적 양자 회로(optimistic quantum circuits)"를 위한 프레임워크를 도입하고, 이를 QFT에 적용한 뒤, 최악의 경우 입력을 처리하기 위한 축소 기법을 제시한다.

1. 낙관적 양자 회로:
   저자들은 대상 유니터리 $U$에 대해 평균 제곱 오차가 $\epsilon$ 이하인 낙관적 양자 회로 $C$ (유니터리 $\tilde{U}$를 유도함)를 정의한다. 형식적으로, 이는 임의의 정규 직교 기저에 대해 $\frac{1}{\dim \mathcal{H}} \sum_i \|\tilde{U}|\phi_i\rangle - U|\phi_i\rangle\|^2 < \epsilon$를 만족한다. 이 정의는 기저에 독립적이며, 오차 연산자의 프로베니우스 노름(Frobenius norm)을 바운딩하는 것과 동등하다. 결정적으로, 이는 오차가 $O(1)$인 "나쁜" 입력의 부분 공간이 힐베르트 공간의 $O(\epsilon)$ 분량만을 차지한다면, 해당 부분 공간에서 오차가 커지는 것을 허용한다.

2. 낙관적 QFT 구조:
   저자들은 $n$ 큐비트에 대한 오차 파라미터 $\epsilon$을 가진 낙관적 QFT($\widetilde{\text{QFT}}$)를 구성한다.

• 블록별 접근 방식: 입력 레지스터를 $m = O(\log(n/\epsilon))$ 크기의 블록들로 나눈다.
• 위상 추정 트릭(Phase Estimation Trick): 이 회로는 블록에 역 QFT를 적용하는 것이 위상 인자(phase factor)의 위상 추정을 근사한다는 사실을 활용한다. 블록에 $\text{QFT}^\dagger$를 적용함으로써, 회로는 인접한 블록들의 위상 기여를 추정한다.
• 가환성(Commutation): 이 구조는 $\text{QFT}^\dagger \text{QFT}$ 형태의 항들을 삽입하고 가환하는 블록들을 서로 통과시켜 이동시킨다. 이는 표준 근사 QFT의 선형 의존성 체인을 끊어낸다.
• 실패 모드: 위상 추정은 블록 상의 입력 상태가 $0$또는$2^m$근처에 있을 때(즉,$0$또는$1$이 길게 늘어선 경우) 실패한다(modulo $2^m$으로 되돌아감). 이것들이 "나쁜" 부분 공간을 구성한다.
• 자원: 결과적인 회로는 깊이 O(\log(n/\epsilon}))를 가지며, 정확히 $n$개의 큐비트를 사용하고(보조 큐비트 없음), 1차원 큐비트 배치에 대해 국소적(범위 $O(\log(n/\epsilon))$)이며, 측정이 필요 없다.

3. 평균-최악 사례 축소(Worst-to-Average Case Reduction):
   입력이 "나쁜" 부분 공간에 집중될 수 있는 시나리오를 해결하기 위해, 저자들은 낙관적 회로를 일반적인 근사 회로로 변환하기 위한 축소 기법을 제안한다.

• 무작위 축소(Randomized Reduction): 낙관적 회로를 적용하기 전에, 유니터리 1-디자인(unitary 1-design)으로부터 추출된 무작위 유니터리 $V$를 적용한다. 그 후, $\hat{V}^\dagger = U V^\dagger U^\dagger$를 적용한다. 이는 입력 상태를 무작위화하여, 고오차 부분 공간에 도달할 확률을 낮춘다.
• 결정론적 축소(Derandomized Reduction): 무작위 과정은 $V$의 선택을 제어 레지스터에 인코딩함으로써 유니터리 연산으로 순수화(purify)될 수 있다.
• 특정 1-디자인: QFT의 경우, 저자들은 Weyl-Heisenberg 군(Pauli-like shift 및 위상 구배의 균등 샘플링)을 1-디자인으로 활용한다. 이 선택은 필요한 무작위화 및 비무작위화 연산이 효율적임을 보장한다.

주요 기여 및 결과

• 낙관적 QFT: 본 논문은 다음을 동시에 달성하는 최초의 QFT 구조를 제시한다:
  • 깊이: $O(\log(n/\epsilon))$.
  • 큐비트 수: $n$ (보조 큐비트 없음).
  • 국소성: $O(\log(n/\epsilon))$ 범위 (1D에 대해 국소적).
  • 측정 불필요.
  • 오차: 힐베르트 공간의 $O(\epsilon)$ 분량을 제외한 모든 상태에 대해 $\epsilon$으로 제한됨.
• 낙관적 곱셈 및 인수분해: 저자들은 낙관적 QFT가 쇼어(Shor) 알고리즘의 정수 인수분해에 직접 사용될 수 있음을 보여준다. 최근의 QFT 기반 빠른 산술 구조(구체적으로 낙관적 곱셈기)에 낙관적 QFT를 통합함으로써, 총 $2n + O(n/\log n)$ 큐비트만을 사용하여 깊이 $O(n^{1+\delta})$ (조절 가능한 $\delta > 0$에 대해)의 인수분해 회로를 달성한다. 이는 $O(n)$의 보조 큐비트나 더 깊은 회로를 필요로 했던 이전 방법들에 비해 깊이 및 큐비트 효율성 면에서 상당한 개선을 나타낸다.
• 일반 근사 QFT: 축소 기법을 적용하여, 임의의 입력에 대해 낮은 오차로 작동하는 근사 QFT를 도출한다.
  • 무작위 버전: $n + O(n/\log(n/\epsilon))$ 총 큐비트를 사용하여 깊이 $O(\log(n/\epsilon))$를 달성한다 (아선형 보조 큐비트).
  • 결정론적(유니터리) 버전: $3n + O(n/\log(n/\epsilon))$ 총 큐비트를 사용하여 깊이 $O(\log(n/\epsilon))$를 달성한다.
  • 이들은 측정이나 피드포워드 없이(결정론적 버전) 또는 아선형 보조 큐비트를 사용하여(무작위 버전) 점근적으로 최적인 로그 깊이를 달성하는 최초의 구조라고 주장된다.

의의
본 논문은 "낙관적 양자 회로"가 양자 알고리즘 설계에 있어 실질적인 패러다임 전환을 제공한다고 주장한다. (쇼어 알고리즘과 같은) 전형적인 알고리즘 맥락에서 통계적으로 발생하기 어려운 드문 실패 모드를 수용함으로써, 자원 오버헤드(깊이 및 보조 큐비트 수)를 획기적으로 줄일 수 있다. 특정 QFT 구조는 인수분해 회로의 병목 현상을 제거하여, 최소한의 큐비트 오버헤드로 거의 선형 깊이의 인수분해를 가능하게 한다. 또한, 제공된 축소 기법은 필요한 경우 낙관적 회로를 견고한 최악의 경우 보장으로 변환하는 일반적인 방법을 제공하며, 휴리스틱한 효율성과 엄격한 정확성 사이의 간극을 메운다. 이 연구는 양자 하드웨어가 성숙해짐에 따라 시공간 볼륨(space-time volume)과 깊이 사이의 트레이드오프가 매우 중요해질 것이며, 이러한 구조들이 그에 대한 경로를 제공함을 시사한다.