Improving reliability of quantum krylov subspace diagonalization : error analysis and reduction

다국어 초록 (Multilingual Abstract)

Quantum simulation is a fundamental application of quantum computing that promises to overcome the exponential scaling limitations of classical algorithms in modeling many-body systems.
Among various quantum algorithms, quantum Krylov subspace diagonalization (QKSD) has emerged as a promising method for the early fault-tolerant quantum computing (EFTQC) era.
QKSD projects a Hamiltonian onto a subspace spanned by real-time evolved states, efficiently estimating extremal eigenvalues with modest circuit depth.
However, its practical reliability has not been well understood, which can be clarified by analyzing the effect of statistical sampling noise and the ill-conditioning.

This dissertation establishes a theoretical framework for sampling error and cost analysis in QKSD, which had not been previously formalized.
Using random matrix modeling and non-asymptotic perturbation bounds for the generalized eigenvalue problem, it quantifies how finite-shot measurement noise propagates to eigenvalue estimation and derives the first explicit expression for QKSD’s computational cost in terms of system size, sampling accuracy, and spectral gap.
The basis-thresholding method is introduced to mitigate instability caused by small singular values in the overlap matrix, ensuring numerical robustness and predictable convergence behavior.

To further improve efficiency, two error-reduction strategies are introduced: the Hamiltonian shifting technique, which eliminates redundant operator terms, and the iterative coefficient splitting (ICS) method, which optimizes quantum uncertainty by balancing operator weights.
These strategies drastically reduce the total sampling cost while maintaining precision, as confirmed by numerical experiments on molecular Hamiltonians and Hubbard-type models.

Beyond error mitigation, this work generalizes the Krylov framework to filtered-state preparation, interpreting the Krylov subspace as a spectral filter that preferentially amplifies the ground-state component.
This insight leads to the development of filtered quantum phase estimation (FQPE), a unifying framework that integrates Krylov filtering with phase estimation to achieve improved overlap amplification and reduced resource requirement.
Along with the Krylov filter, classically inspired filters such as Gaussian and Chebyshev filters are systematically analyzed to quantify the trade-offs among circuit depth, success probability, and accuracy.

Through rigorous analysis and practical design strategies, this dissertation enhances the reliability and resource efficiency of QKSD, bridging the gap between near-term heuristic methods and asymptotically optimal quantum algorithms.
The results contribute to the foundation for predictable eigenvalue estimation and quantum advantage realization in the early fault-tolerant era.

국문 초록 (Abstract)

양자 시뮬레이션은 다체계 양자 시스템을 모사하는 과정에서 고전 알고리즘이 가지는 지수적 복잡도를 극복할 수 있는 양자 컴퓨팅의 핵심 응용 분야이다.
여러 양자 알고리즘 가운데 양자 크릴로프 부분공간 대각화(Quantum Krylov Subspace Diagonalization, QKSD) 는 초기 오류 정정 양자 컴퓨팅(Early Fault-Tolerant Quantum Computing, EFTQC) 시대를 위한 유망한 방법으로 주목받고 있다. QKSD는 해밀토니안을 실시간 진화로 생성된 기저 상태들의 부분공간에 투사하여, 비교적 얕은 회로 깊이로 극값 고유값을 효율적으로 추정한다.
그러나 통계적 샘플링 잡음과 일반화 고유값 문제의 조건수 악화(ill-conditioning)로 인해 발생하는 오차의 영향이 충분히 규명되지 않았으며, 이에 대한 정량적 신뢰성 분석이 요구되어 왔다.

본 논문은 체계적으로 확립되지 않았던 QKSD의 샘플링 오차 및 계산 비용 분석 이론을 처음으로 정립하였다.
랜덤 행렬 모델링과 일반화 고유값 문제(Generalized Eigenvalue Problem, GEVP)에 대한 비점근적 섭동 경계(non-asymptotic perturbation bound)를 이용하여, 유한 표본 측정 잡음이 고유값 추정에 미치는 영향을 정량화하고 QKSD의 계산 비용을 시스템 크기, 샘플링 정밀도, 스펙트럼 갭의 함수로 최초로 공식화하였다.
또한 중첩 행렬(overlap matrix)의 작은 특이값으로 인해 발생하는 수치적 불안정성을 완화하기 위해 기저 절단(basis-thresholding) 기법을 도입하여, 안정적이고 예측 가능한 수렴 특성을 확보하였다.

효율성 향상을 위해 두 가지 주요 오차 저감 기법을 도입하였다.
첫째, 해밀토니안 시프트(Hamiltonian shifting) 기법은 불필요한 연산 항을 제거하여 샘플링 비용을 감소시키며, 둘째, 계수 분할(Iterative Coefficient Splitting, ICS) 기법은 연산자 가중치를 재조정하여 측정 분산을 효과적으로 감소시킨다.
이러한 기법들은 분자 해밀토니안 및 허바드(Hubbard) 계열 모델의 수치 실험을 통해 정확도를 유지한 상태에서 총 샘플링 비용을 크게 절감함을 확인하였다.

오차 저감 기법을 넘어, 본 연구는 크릴로프 방법론을 필터링된 상태 준비(filtered-state preparation) 로 확장하였다.
이는 크릴로프 부분공간을 바닥상태 성분을 선택적으로 증폭하는 스펙트럼 필터(spectral filter)로 해석함으로써, 필터가 적용된 양자 위상 추정(Filtered Quantum Phase Estimation, FQPE) 이라는 통합적 프레임워크를 제안한다.
이 방법은 크릴로프 필터와 위상 추정을 결합하여 중첩 증폭을 강화하고 자원 요구량을 절감하며, 가우시안(Gaussian) 및 체비셰프(Chebyshev) 필터와 같은 고전적 필터들을 포함한 다양한 필터의 회로 깊이, 성공 확률, 정확도 간의 상충 관계를 체계적으로 분석한다.

본 논문은 엄밀한 이론 분석과 실용적 설계를 통해 QKSD의 신뢰성과 자원 효율성을 크게 향상시켰으며, 휴리스틱 알고리즘과 점근적으로 최적화된 양자 알고리즘 간의 간극을 효과적으로 메웠다.
본 연구의 결과는 예측 가능하고 안정적인 고유값 추정, 그리고 초기 오류 정정 시대에서의 양자 이점 실현을 위한 핵심적 기반을 제공한다.

목차 (Table of Contents)

• 1. Introduction 1
• 2. Background and Preliminaries 5
• 2.1. Ground State Energy Estimation Problem 7
• 2.2. Quantum Phase Estimation 12
• 2.3. Variational Quantum Eigensolver 15
• 2.4. Quantum Krylov Subspace Diagonalization (QKSD) 17
• 3. Sampling Error Analysis in QKSD 30
• 3.1. Statistical Property of QKSD Error Matrix Norm 31
• 3.2. QKSD Cost Analysis 40
• 3.3. Consideration of Trotter and Gate Errors 44
• 3.4. Numerical Experiments 46
• 4. Strategies for Reducing Sampling Error in QKSD 52
• 4.1. Pauli Grouping 53
• 4.2. Hamiltonian Shifting Technique 56
• 4.3. Iterative Coefficient Splitting 59
• 4.4. Numerical Experiments 63
• 5. Filtered Quantum Phase Estimation 68
• 5.1. Filtered State 69
• 5.2. Gaussian Filtered QPE 76
• 5.3. Krylov Filtered State 83
• 5.4. Numerical Experiments 88
• 6. Conclusions 95
• 6.1. Summary of Contributions 95
• 6.2. Reflections and Limitations 97
• 6.3. Outlook and Future Directions 97
• 6.4. Concluding Remarks 99
• References 100
• Appendix 110
• A. Hamiltonian Simulation 110
• B. Haar-Averaged Variance and Optimal Shot Allocations 114
• C. Error Matrix Norm Bound 121
• D. Generalized Eigenvalue Problem Perturbation 130
• E. Consideration of Simulation Error 133
• F. Hardware Noise 137
• G. Details for Hamiltonian Shifting and ICS 140
• H. Block Encoding and Hamiltonian Funtion Implementation 146
• I. Details for Filter Functions 150
• J. Filter Robustness Analysis 155
• K. Gaussian Filtered QPE Cost Analysis 164