Harmonic sequence state-preparation

논문 제목: Harmonic sequence state-preparation (조화 수열 상태 준비)

저자: Benjamin Rempfer, Parker Kuklinski, Justin Elenewski, Kevin Obenland (MIT Lincoln Laboratory)

1. 문제 정의 (Problem)

양자 알고리즘, 특히 비선형 미분 방정식 솔버 (nonlinear differential equation solvers) 및 양자 선형 시스템 알고리즘에서 조화 수열 (Harmonic Sequence) 상태 $|h\rangle \propto \sum_{x=1}^{N-1} \frac{1}{x}|x\rangle$ 또는 이를 대각선 요소로 갖는 행렬의 블록 인코딩 (block-encoding) 이 필수적입니다.

기존의 일반적인 상태 준비 방법들 (Grover-Rudolph 알고리즘, 거절 샘플링, 양자 신호 처리 등) 은 다음과 같은 한계를 가집니다:

• 높은 리소스 비용: $1/x$ 함수는 $x=0$에서 발산하므로 적분이 불가능하여 Grover-Rudolph 알고리즘 적용이 어렵습니다.
• 복잡한 회로: 다항식 근사 (QSVT 등) 는 특이점 (singularity) 근처에서 실패하며, 뉴턴 방법 등을 이용한 고전적 연산 기반 회로는 오차 허용 범위가 줄어들수록 게이트 비용이 기하급수적으로 증가합니다.
• 기존 연구의 부재: 조화 수열 상태 준비에 대한 구체적인 리소스 추정치가 부족하거나, 거절 샘플링을 사용할 경우 수천 개의 Toffoli 게이트와 큰 보조 큐비트 (ancilla) 레지스터가 필요하다는 보고가 있었습니다 (예: Lemieux et al. 은 22 큐비트 상태 준비에 약 11,000 개의 Toffoli 게이트 소요).

2. 방법론 (Methodology)

저자들은 고전적인 이진 산술 연산에 의존하지 않고, **양자 푸리에 변환 (QFT)**과 수학적 성질을 활용한 근본적인 접근법을 제시합니다.

• 핵심 아이디어:

  • 톱니파 (Sawtooth wave) 와 조화 수열의 관계: 톱니파 함수의 푸리에 계수가 조화 수열 ($1/k$) 을 따릅니다.
  • 선형 상태 (Linear State) 준비: 먼저 선형적으로 스케일링된 진폭을 갖는 양자 상태 $|L\rangle \propto \sum (\frac{N-1}{2} - x)|x\rangle$를 효율적으로 준비합니다.
  • QFT 적용: 준비된 선형 상태 $|L\rangle$에 QFT 를 적용하면, 연속적인 톱니파의 푸리에 변환과 유사하게 코탄젠트 (cotangent) 함수 형태의 진폭을 갖는 상태가 생성됩니다.
  • 점근적 근사: 코탄젠트 함수 $\cot(x)$는 $x \to 0$일 때 $1/x$로 점근합니다. 따라서 보조 큐비트 (ancilla) 를 추가하여 더 큰 코탄젠트 상태를 준비하고, 이를 측정하여 코탄젠트 함수의 점근선 (asymptote) 영역만 선택함으로써 조화 수열 상태를 고효율로 근사합니다.

• 블록 인코딩 (Block-encoding) 확장:

  • 미분 방정식 알고리즘에서는 상태가 아닌 행렬의 대각선에 조화 수열이 필요합니다.
  • 합성곱 정리 (Convolution Theorem) 활용: 시간 영역에서의 합성곱은 주파수 영역에서의 곱셈과 같습니다. 선형 순환 행렬 (linear circulant matrix) 을 QFT 로 대각화하면 그 고유값이 코탄젠트 함수를 따르게 되므로, 이를 통해 대각선 조화 행렬 (diagonal harmonic matrix) 의 블록 인코딩을 구성합니다.
  • 이 대각 행렬을 미분 방정식 알고리즘이 요구하는 아랫대각선 (subdiagonal) 형태로 변환하기 위해 순환 시프트 (cyclic shift) 연산자를 적용합니다.

• 오차 보정 및 최적화:

  • 생성된 코탄젠트 상태에는 상수 실수 부분이 존재하고 두 개의 점근선 (asymptote) 이 혼재되어 있습니다.
  • 저자들은 다중 제어 X 게이트, CNOT 게이트, 증분기 (incrementer) 를 사용하여 원치 않는 진폭을 제거하고 두 점근선을 간섭시켜 (constructive interference) 실수 부분을 상쇄하는 회로를 설계했습니다. 이를 통해 보조 큐비트 수를 줄이고 정확도를 높였습니다.

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

• 효율적인 회로 설계:

  • 상태 준비: $n$개의 데이터 큐비트와 $m$개의 보조 큐비트를 사용하여 조화 수열 상태를 준비하는 회로를 제안했습니다.
  • 리소스 비교 (22 큐비트, 오차 $\epsilon=10^{-9}$ 기준):
    • 기존 방법 (Lemieux et al., 거절 샘플링): 약 11,000 개의 Toffoli 게이트.
    • 본 논문 (QFT 기반): 약 5,400 개의 T 게이트 (T-count), 1,700 의 T 깊이 (T-depth).
    • 성능 향상: 기존 방법 대비 T 게이트 수와 깊이가 크게 감소했습니다.
  • 주요 비용 요소: 전체 회로 비용의 **80~90%**가 QFT 구현에 소요되며, 이는 QFT 기술의 발전에 따라 즉시 개선될 수 있는 잠재력을 가집니다.

• 블록 인코딩 비용 분석:

  • 대각선 조화 행렬의 블록 인코딩 회로도 제안되었으며, 이 역시 QFT 비용이 지배적입니다 (약 70~80%).
  • 서브노멀라이제이션 (subnormalization) 인자 $\alpha \approx 0.1061$을 달성하여, 성공 확률이 낮아 반복 실행이 필요한 상황을 최소화했습니다.

• 미분 방정식 알고리즘 적용성 검증:

  • 비선형 미분 방정식 솔버 (Carleman 선형화 기반) 에 이 블록 인코딩을 적용한 시나리오를 분석했습니다.
  • 결과적으로, 조화 수열 블록 인코딩에 소요되는 리소스는 전체 알고리즘 비용 (특히 $F$-행렬 블록 인코딩 비용) 에 비해 미미하여, 전체 알고리즘의 병목 현상이 되지 않음을 입증했습니다.

4. 의의 (Significance)

1. 실용적인 리소스 절감: 조화 수열 상태 준비에 필요한 게이트 비용과 보조 큐비트 수를 기존 방법 대비 획기적으로 줄여, 양자 미분 방정식 솔버 및 관련 알고리즘의 실현 가능성을 높였습니다.
2. 수학적 구조의 활용: 복잡한 고전적 연산 (Newton's method 등) 대신 양자 알고리즘의 고유한 특성 (QFT, 푸리에 계수) 을 활용하여 문제를 해결하는 새로운 패러다임을 제시했습니다.
3. 확장성: 이 QFT 기반 접근법은 $x^{-n}$ (역수 멱함수) 이나 sinc 함수 등 다른 특이점을 가진 함수의 상태 준비에도 확장 적용 가능함을 시사합니다.
4. 정밀한 리소스 추정: 기존 문헌에서 간과되었던 조화 수열 블록 인코딩에 대한 구체적인 T 게이트 수, 깊이, 보조 큐비트 수를 제시하여 향후 오류 정정 양자 컴퓨터 구현에 중요한 기준을 마련했습니다.

결론적으로, 이 논문은 조화 수열 상태 준비라는 특정 문제를 해결하기 위해 QFT 를 핵심 도구로 활용함으로써, 기존 방법론의 비효율성을 극복하고 양자 알고리즘의 전체적인 실행 비용을 크게 낮출 수 있음을 증명했습니다.