A mixed-precision quantum-classical algorithm for solving linear systems

1. 문제 정의 (Problem)

• 핵심 문제: 주어진 비특이 행렬 $A$와 벡터 $b$에 대해 선형 방정식 $Ax = b$를 푸는 것.
• 기존 양자 알고리즘의 한계:
  • 선형 시스템 해결을 위한 양자 알고리즘 (HHL, QSVT 등) 은 이론적으로 지수적 가속을 약속하지만, 현재 기술 수준에서는 **높은 정확도 (예: $10^{-5}$ 이상)**를 달성하기 위해 막대한 양자 자원 (회로 깊이, 게이트 수) 이 필요합니다.
  • 특히 **QSVT(Quantum Singular Value Transformation)**는 역함수를 다항식으로 근사해야 하는데, 높은 정확도를 요구할수록 다항식의 차수가 급격히 증가하여 양자 회로의 깊이가 비현실적으로 길어집니다.
  • 이는 NISQ(Noisy Intermediate-Scale Quantum) 장비를 넘어 대규모 양자 (LSQ) 환경에서도 정확도와 비용 간의 트레이드오프를 발생시킵니다.

2. 방법론 (Methodology)

저자들은 혼합 정밀도 (Mixed-Precision) 반복 정제 (Iterative Refinement) 기법을 QSVT 알고리즘에 적용하는 하이브리드 양자 - 고전 알고리즘을 제안했습니다.

• 기본 아이디어:

  1. 저정밀도 양자 솔버 (QPU): QSVT 를 사용하여 낮은 정밀도 ($\epsilon_l$) 로 초기 해 $\tilde{x}_0$를 빠르게 계산합니다. 이때 다항식 근사의 차수를 낮춰 양자 자원을 절약합니다.
  2. 고정밀도 고전 정제 (CPU): 계산된 해의 오차 (잔차, Residual) 를 고정밀도 (Double precision 등) 로 계산하고, 이를 보정 벡터로 사용하여 해를 업데이트합니다.
  3. 반복 과정: 잔차가 목표 정확도 ($\epsilon$) 이하가 될 때까지 위 과정을 반복합니다.

• 알고리즘 흐름 (Algorithm 2):

  • 입력: 행렬 $A$, 벡터 $b$, QSVT 의 초기 정확도 $\epsilon_l$, 목표 정확도 $\epsilon$.
  • 초기화: QPU 에서 QSVT 를 이용해 $x_0 = A^{-1}b$를 $\epsilon_l$ 정확도로 계산.
  • 반복 (while loop):
    1. 잔차 계산 (CPU): $r_i = b - Ax_i$를 고정밀도 $u$로 계산.
    2. 오차 보정 (QPU): $Ae_i = r_i$를 다시 QSVT 를 이용해 $\epsilon_l$ 정확도로 계산.
    3. 해 업데이트 (CPU): $x_{i+1} = x_i + e_i$를 고정밀도로 업데이트.
  • 종료 조건: 스케일링된 잔차 $\omega = \|b - A\tilde{x}\| / \|b\| \le \epsilon$.

• 주요 기술적 특징:

  • 블록 인코딩 (Block-encoding): 비유니터리 행렬을 유니터리 행렬에 임베딩하여 양자 회로에서 처리 가능하게 함.
  • 상태 준비 (State Preparation): 벡터 $b$와 잔차 $r_i$를 양자 상태로 인코딩.
  • 데이터 통신: 행렬 $A$의 블록 인코딩 회로는 한 번만 전송되고, 반복 단계에서는 잔차 벡터에 대한 상태 준비 회로만 전송하여 통신 오버헤드를 최소화.

3. 주요 기여 (Key Contributions)

1. 혼합 정밀도 QSVT 프레임워크 제안: 고전 컴퓨팅의 혼합 정밀도 반복 정제 기법을 양자 알고리즘 (QSVT) 에 성공적으로 적용하여, 낮은 정밀도의 양자 연산과 높은 정밀도의 고전 연산을 결합했습니다.
2. 수렴성 및 복잡도 분석:
   • 수렴성: 조건수 $\kappa$와 초기 정확도 $\epsilon_l$이 $\epsilon_l \kappa < 1$을 만족할 때 알고리즘이 수렴함을 증명했습니다.
   • 반복 횟수 상한: 목표 정확도 $\epsilon$에 도달하는 데 필요한 반복 횟수가 $\lceil \log(\epsilon) / \log(\epsilon_l \kappa) \rceil$로 제한됨을 보였습니다.
   • 복잡도 이점: 직접 고정밀도 QSVT 를 사용하는 것보다 혼합 정밀도 방식이 전체 양자 비용 (블록 인코딩 호출 횟수 및 샘플 수) 을 크게 줄일 수 있음을 이론적으로 분석했습니다. 특히 낮은 정밀도에서 다항식 차수가 줄어들어 양자 회로 깊이가 감소합니다.
3. 실제 구현 및 시뮬레이션: myQLM 양자 소프트웨어 스택을 사용하여 무작위 행렬 및 1 차원 푸아송 방정식 (삼각대행렬) 에 대한 실험을 수행했습니다.

4. 실험 결과 (Results)

• 수렴성 검증:
  • 조건수 $\kappa=10$ 및 다양한 $\epsilon_l$ 값에서 목표 정확도 $\epsilon=10^{-11}$까지 수렴하는 것을 확인했습니다.
  • 실제 반복 횟수가 이론적 상한선 ($\lceil \log(\epsilon) / \log(\epsilon_l \kappa) \rceil$) 과 매우 근사하게 일치함을 보였습니다.
  • 조건수가 큰 경우 ($\kappa=100, 200, 300$) 에도 알고리즘이 수렴함을 확인했습니다.
• 복잡도 비교 (그림 5):
  • $\kappa=2$인 경우, 혼합 정밀도 반복 정제를 사용한 QSVT 는 직접 고정밀도 QSVT 를 사용하는 것보다 **블록 인코딩 호출 횟수 (양자 비용)**가 현저히 낮았습니다.
  • 목표 정확도 $\epsilon$가 초기 정밀도 $\epsilon_l$보다 훨씬 작을 때 ($\epsilon \ll \epsilon_l$) 이득이 극대화됩니다.
• 자원 효율성: 고전적인 LU 분해 등 기존 솔버는 효율적이지만, 대규모 행렬에서 QSVT 는 조건수가 커질수록 비용이 급증합니다. 제안된 방법은 이러한 비용을 줄여주어 실용적인 양자 자원으로도 높은 정확도 해를 얻을 수 있게 합니다.

5. 의의 및 결론 (Significance & Conclusion)

• 양자 - 고전 하이브리드 아키텍처의 실용화: 미래의 고성능 컴퓨팅 (HPC) 환경에서 CPU 와 QPU 가 협력하는 구체적인 알고리즘 사례를 제시했습니다.
• 자원 절감: 고비용인 고정밀도 양자 연산을 피하고, 상대적으로 저렴한 저정밀도 양자 연산과 정밀한 고전 연산을 조합하여 양자 자원의 효율성을 극대화했습니다.
• 미래 전망: 현재는 시뮬레이션 단계이나, 오류 정정이 된 양자 컴퓨터 (Fault-tolerant Quantum Computer) 가 실현되면 이 방식은 대규모 선형 시스템 해결에 있어 표준적인 접근법이 될 수 있습니다.
• 한계: 현재는 시뮬레이션 기반이며, 실제 양자 하드웨어의 노이즈와 확장성 문제는 향후 연구 과제로 남았습니다.

요약: 이 논문은 QSVT 기반 선형 시스템 해결 시 발생하는 높은 양자 비용 문제를 해결하기 위해, 저정밀도 양자 솔버와 고정밀도 고전 반복 정제를 결합한 혼합 정밀도 알고리즘을 제안했습니다. 이론적 분석과 시뮬레이션을 통해 이 방법이 정확도를 유지하면서도 양자 자원 (회로 깊이, 게이트 수) 을 획기적으로 줄일 수 있음을 입증했습니다.