Extending Sample-based Quantum Diagonalization to Systems of Linear Equations

기술 요약: 선형 방정식 시스템으로의 샘플 기반 양자 대각화 확장

문제 정의
선형 방정식 $Ax = b$를 푸는 것은 계산 과학의 근본적인 과제입니다. HHL 알고리즘은 차원 $N$에 대해 로그 스케일링을 갖는 양자 가속을 제공하지만, 양자 위상 추정(QPE), 제어된 회전, 사후 선택(post-selection)을 포함하는 깊은 회로에 의존하므로 현재의 노이즈가 있는 중간 규모 양자(NISQ) 하드웨어에는 부적합합니다. 기존의 대안들은 결함 허용(fault-tolerant) 자원을 필요로 하거나 조건수(condition number) 및 원하는 정확도에 따라 성능이 저하되는 경우가 많습니다. 따라서 현재 하드웨어의 한계 내에서 작동하며 더 얕은 회로를 활용할 수 있는 알고리즘이 필요합니다.

방법론
본 연구는 본래 양자 화학을 위해 개발된 **샘플 기반 양자 대각화(Sample-based Quantum Diagonalization, SQD)**를 선형 시스템 해결로 확장합니다. 이 접근 방식은 다음과 같은 하이브리드 양자-고전 워크플로우를 따릅니다:

1. 파울리 분해(Pauli Decomposition): 헤르미트 행렬 $A$를 파울리 문자열의 합 $A = \sum_{l=1}^L c_l P_l$으로 분해합니다.
2. 상태 준비 및 진화(State Preparation and Evolution): 우변 벡터 $b$를 초기 양자 상태 $|\psi_0\rangle$로 인코딩합니다. 시스템은 이산적인 시간 지점 $t_j$에서 해밀토니안 $A$에 대해 트로터화된(Trotterized) 시간 진화를 거치며, 이는 리-트로터(Lie–Trotter) 곱 공식을 사용하여 상태 $|\psi(t_j)\rangle = e^{-iAt_j}|\psi_0\rangle$를 근사합니다.
3. 샘플링(Sampling): 진화된 상태를 계산 기저(computational basis)에서 여러 시간 단계에 걸쳐 측정합니다. 결과로 얻은 비트 문자열 구성들을 모아 경험적 분포 $\hat{p}_{agg}(z)$를 형성합니다.
4. 구성 선택(Configuration Selection): 샘플링된 비트 문자열(영 확률을 갖는 것들)과 $b$의 알려진 서포트(support)로부터 구성 집합 $C$를 구축합니다.
5. 갤러킨 투영(Galerkin Projection): 선형 시스템을 $C$ 내의 구성들이 생성하는 부분 공간으로 투영합니다. 이는 축소된 행렬 $A_{sub} = V^\dagger A V$와 벡터 $b_{sub} = V^\dagger b$를 구성하는 과정을 포함하며, 여기서 $V$는 선택된 기저 상태들의 등거리 사상(isometry)입니다. 축소된 시스템 $A_{sub} x_{sub} = b_{sub}$를 고전적으로 풀고, 솔루션을 $x_{approx} = V x_{sub}$로서 전체 공간으로 다시 들어 올립니다(lift).

주요 기여
본 논문은 기존의 샘플 기반 양자 선형 솔버(특히 문헌 4 및 6)와 비교하여 네 가지 주요 기여를 합니다:

1. 정확성에 대한 이론적 특성화: 저자는 샘플링된 구성 집합 $C$가 $b$의 크릴로프 서포트(Krylov support, 즉 $\{A^k b\}$의 서포트)를 포함할 경우 갤러킨 솔루션이 정확하다는 것을 증명합니다. 또한, 대칭 양의 정부호(SPD) 행렬의 경우 솔루션은 에너지 노름(energy norm)에서 최적입니다. 노이즈로 유도된 구성들은 이상적인 구성을 밀어내지 않는 한 정확도를 저하시키지 않습니다.
2. 파울리 인코딩에서의 비용 분석: 본 연구는 파울리 문자열 인코딩에서의 방법론 비용을 분석합니다. 밴디드(banded) 행렬의 경우, 이진 인코딩은 $O(N)$개의 파울리 항을 필요로 하며, 리-트로터 오차가 크릴로프 서포트 외부의 가짜 구성을 생성하여 정확도가 손실되기 전에 압축 이점을 상쇄할 수 있음을 보여줍니다.
3. 오픈 소스 구현: 노이즈 없는 시뮬레이터, 노이즈 있는 시뮬레이터, 그리고 IBM 퀀텀 하드웨어를 위한 통합 인터페이스를 제공하는 오픈 소스 Qiskit 패키지(sqd_linsolve)를 제공합니다.
4. 비교 분석: 정확한 샘플링 분포를 사용하여 국소적(localized) 및 조밀한(dense) 문제 인스턴스에 대해 고전적 크릴로프 방법, 잔차 기반 그리디(residual-based greedy) 선택, 오라클 선택과 벤치마킹을 수행했습니다.

결과
저자는 수치 실험과 하드웨어 실행을 통해 파이프라인을 검증했습니다:

• 4x4 예시: 노이즈 없는 시뮬레이터, 노이즈 있는 시뮬레이터, IBM 퀀텀 하드웨어(ibm_fez)에서 이 방법은 $4 \times 4$ SPD 시스템을 성공적으로 해결했습니다. 하드웨어 분포가 정확한 분포에서 벗어났음에도 불구하고(노이즈로 인해), 네 개의 구성이 모두 샘플링되어($R=N$) 정확성 조건을 충족했기 때문에 솔루션이 정확하게 복구되었습니다.
• 국소적 문제 ($N=1024$): 스크린된 푸아송 연산자(screened Poisson operator)에 대해 정확한 샘플링 분포를 사용하여(이 특정 테스트에서는 회로 노이즈를 우회함), 이 방법은 $N=1024$개 중 단 $R=33$개의 구성만을 부분 공간으로 선택했습니다. 이를 통해 $10^{-5}$의 상대 오차를 얻었으며, 절단된 부분 공간은 최적의 오라클 선택과 일치했습니다.
• 노이즈 및 오차: 이 방법은 판독 노이즈(readout noise)에 강한 모습을 보였습니다. 비트 플립 오차를 추가하면 구성 집합이 커졌지만, 에너지 노름 오차를 저하시키지는 않았으며, 이는 이론적 최적성 주장에 부합합니다. 그러나 트로터 오차는 가짜 구성을 생성하여 부분 공간의 크기를 팽창시키고 효율성을 떨어뜨릴 수 있음이 발견되었습니다.
• 고전적 비교: 테스트된 국소적 문제들에 대해, 양자 샘플링 단계는 저렴한 고전적 잔차 기반 선택 및 고전적 크릴로프 서포트 분석에 의해 발견된 부분 공간과 일치하는 부분 공간을 선택했습니다. 조밀한 무작위 행렬의 경우, 더 미세한 시간 격자(나이퀴스트 단계)를 사용하지 않는 한 이 방법은 무작위 선택과 유사한 성능을 보였으나, 여전히 고전적 그리디 선택보다는 뒤처졌습니다.

의의 및 한계
본 논문은 제안된 방법이 양자 샘플링 단계가 유리할 수 있는 조건을 규정한다고 결론짓습니다. 결과에 따르면 솔루션이 소수의 구성에 집중되어 있고 행렬이 다항식 개수의 파울리 문자열 합으로 주어지는 문제의 경우 이 방법이 효과적입니다. 그러나 저자는 중요한 한계점을 언급합니다: 테스트된 영역(작은 광추를 가진 국소적 문제)에서 양자 샘플링 단계가 고전적 잔차 기반 선택보다 우수함을 입증하지 못했다는 점입니다.

저자는 관련 구성들이 고전적인 짧은 전개(short expansions)로는 접근 불가능하거나, $e^{-iAt}|b\rangle$로부터의 샘플링이 고전적으로 어려운 문제 구조를 식별하는 것이 여전히 미해결 과제로 남아 있다고 명시합니다. 본 연구는 선형 시스템을 위한 SQD 프레임워크의 예비 검증 역할을 하며, 이 방법이 특정 유형의 노이즈에 견고하고 이론적으로 타당하지만, 양자 이득을 달성하기 위해서는 현재 하드웨어에서 아직 입증되지 않은 특정 문제 구조가 필요함을 강조합니다. 또한 밴디드 행렬의 경우 파울리 문자열 인코딩이 깊은 회로를 유발하며, 현재의 하드웨어 테스트는 양자 이득이 나타날 수 있는 절단된 영역($R < N$)을 아직 탐색하지 못했다고 설명합니다.