Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform

1. 연구 배경 및 문제 제기 (Problem)

• 배경: 양자 컴퓨팅에서 QFT 는 쇼어 알고리즘, 위상 추정, HHL 알고리즘 등 핵심 알고리즘의 필수 구성 요소입니다.
• 문제: 양자 하드웨어의 오류를 검증하는 것은 일반적으로 매우 어렵습니다. 특히 '최악의 경우 (worst-case)' 검증은 지수적으로 어렵지만, '평균 사례 (average-case)' 검증은 상대적으로 쉽습니다.
• 선행 연구 (Linden & de Wolf, 2022): Linden 과 de Wolf 는 QFT 가 평균적으로 정확하면 위상 추정, 주기 찾기 등 특정 작업에서 최악의 경우에도 좋은 성능을 보장할 수 있음을 증명했습니다.
• 한계: 그러나 HHL 알고리즘은 단순히 고유값 (eigenvalues) 을 출력하는 것을 넘어, 고유값과 고유벡터에 의존하는 양자 상태 (quantum state) 를 출력해야 합니다.
  • 기존 평균 사례 검증 프로토콜을 통과하는 QFT 는 최종 상태에 통제 불가능한 국소 위상 (uncontrollable local phases) 을 도입할 수 있습니다.
  • 예: $C = D F_N^{-1}$ (여기서 $D$는 대각 유니터리 행렬) 인 경우, 평균 fidelity 는 1 에 가까울 수 있지만, 입력 상태 $\sum \alpha_k |k\rangle|u_k\rangle$에 적용 시 각 항마다 다른 위상 $e^{i\theta_k}$가 붙어 원하는 상태와 크게 달라질 수 있습니다. 이는 HHL 알고리즘의 정확성을 해칩니다.

2. 방법론 (Methodology)

저자는 HHL 알고리즘을 평균 사례 QFT 로 실행하기 위해 Linden-de Wolf 프로토콜을 강화하고 새로운 검증 집합을 정의했습니다.

2.1 강화된 검증 집합 정의

기존의 $S_1(\eta)$ (푸리에 기저에서의 평균 근사) 만으로는 부족하므로, 다음과 같은 새로운 조건을 도입했습니다.

• $S_1(\eta)$: 푸리에 기저 $|\hat{k}\rangle$에서 $F_N^{-1}$에 평균적으로 근사.
• $S_2(\eta)$: 계산 기저 $|k\rangle$에서 $F_N$에 평균적으로 근사 (역변환 성질).
• $S_3(\eta)$ (핵심 제안):
  $$\mathbb{E}_{k,l} \langle k | C(|\hat{k}\rangle\langle\hat{l}|) | l \rangle \ge 1 - \eta$$
  이 조건은 채널 $C$가 푸리에 기저의 비대각 성분 (off-diagonal terms) 까지 포함하여 전체적으로 $F_N^{-1}$에 가깝고, 위상 일관성을 유지함을 의미합니다. 유니터리 채널의 경우, 이는 $C \approx e^{i\theta} F_N^{-1}$ (전체 위상만 다름) 임을 보장합니다.

2.2 경량 검증 프로토콜 (Lightweight Protocols)

$S_3(\eta)$를 직접 검증하는 것은 어렵지만, 다음 두 가지 프로토콜을 조합하여 간접적으로 검증할 수 있음을 증명했습니다.

1. TA1 (Testing Algorithm 1): $C$가 $S_1(\eta)$에 속하는지 검증 (기존 Linden-de Wolf 방식).
2. TA2 (Testing Algorithm 2): $C$가 $S_2(\eta)$에 속하는지 검증 (계산 기저에서 역변환 성질 확인).

주요 정리 (Theorem 4): $C \in S_1(\eta_1) \cap S_2(\eta_2)$이면 $C \in S_3(\eta_1 + \eta_2)$입니다. 즉, 두 가지 가벼운 테스트를 통과하면 HHL 알고리즘에 필요한 강력한 조건 ($S_3$) 을 만족합니다.

2.3 HHL 알고리즘 적용

HHL 알고리즘의 핵심 단계인 위상 추정 과정에서 $F_N^{-1}$을 $C$로, $F_N$을 $P$로 대체하여 실행합니다.

• 랜덤화 기법: 입력 행렬 $A$의 고유값이 $n$비트로 정확히 표현되지 않는 일반적 경우를 처리하기 위해, 고유값에 무작위 오프셋 $l/N$을 더하는 기법 (Linden-de Wolf 방식) 을 도입했습니다.
• 오차 분석: $C \in S_3(\eta_1)$과 $P \in T_3(\eta_2)$ (QFT 에 대한 대응 집합) 일 때, 최종 출력 상태와 이상적인 상태 간의 평균 fidelity 하한을 유도했습니다.

3. 주요 결과 (Key Results)

3.1 이상적인 경우 (고유값이 $n$비트 정확)

• Theorem 10: $C \in S_3(\eta_1)$, $P \in T_3(\eta_2)$일 때, 평균 fidelity 는 다음과 같이 하한을 가집니다.
  $$\mathbb{E}_l [F(\rho_{7,l}, |\phi_{7,l}\rangle\langle\phi_{7,l}|)] \ge 1 - \sqrt{\eta_1} - \sqrt{\eta_2}$$
  이는 평균 사례 QFT 가 HHL 알고리즘의 최악의 경우 성능을 보장함을 의미합니다.

3.2 일반적 경우 (고유값이 $n$비트보다 정밀)

• Theorem 13: 고유값이 $n$비트보다 정밀한 경우, 근사 오차 $K$를 도입하여 분석했습니다.
  $$\text{Fidelity} \ge 1 - (\eta_1^{1/2} + \eta_2^{1/2}) - 2\sqrt{K}(\eta_1^{1/4} + \eta_2^{1/4}) - \frac{4\sqrt{5}}{(K-1)^{1/4}}$$
  $\eta_1, \eta_2$가 충분히 작으면 ($O(K^{-2})$), HHL 알고리즘은 높은 정확도로 동작합니다.

3.3 특수한 유니터리 채널 경우

• Theorem 14, 15: $C$가 가역적 (역채널 $C^{-1}$ 사용 가능) 인 유니터리 채널이고 $S_1(\eta)$만 만족할 때도 HHL 이 작동함을 보였습니다.
• Theorem 17, 18: $C \in S_1(\eta_1)$, $P \in T_2(\eta_2)$이고 $C \circ P$의 평균 대각 성분이 1 에 가까울 때 ($|E[\langle k|C \circ P|k\rangle]| \ge 1-\eta_3$), 위상 불일치 문제가 해결되어 HHL 이 성공함을 증명했습니다.

4. 의의 및 결론 (Significance)

1. 최악의 경우 - 평균 사례 축소 (Worst-case to Average-case Reduction) 의 확장:
   기존에 위상 추정 등 일부 작업에 국한되었던 이 개념을, 더 복잡하고 민감한 선형 방정식 풀이 (HHL) 알고리즘으로 확장했습니다.
2. 실용적 검증 가능성:
   HHL 알고리즘을 실행하기 위해 QFT 가 완벽할 필요는 없으며, 두 가지 간단한 테스트 (TA1, TA2) 를 통과하는 평균적으로 정확한 QFT 만으로도 신뢰할 수 있는 결과를 얻을 수 있음을 보였습니다. 이는 노이즈가 있는 양자 컴퓨터 (NISQ) 환경에서 알고리즘 실행의 타당성을 높입니다.
3. 위상 제어 문제 해결:
   평균 사례 검증이 단순히 진폭 (amplitude) 만 맞추는 것이 아니라, 위상 (phase) 일관성까지 보장해야 HHL 이 작동한다는 점을 명확히 하고, 이를 검증하는 강화된 프로토콜을 제시했습니다.
4. 미래 전망:
   이 아이디어는 QFT 기반의 다른 양자 알고리즘 (양자 토모그래피 등) 으로도 확장 가능할 것으로 기대됩니다.

요약: 이 논문은 "QFT 가 평균적으로 정확하다면, 강화된 검증 프로토콜을 통해 HHL 알고리즘이 최악의 경우에도 올바르게 작동한다"는 것을 수학적으로 증명함으로써, 양자 오류 검증 및 알고리즘 신뢰성 확보에 중요한 기여를 했습니다.