Mirror subspace diagonalization: A real-time quantum Krylov algorithm with near-optimal sampling cost

The mirror subspace diagonalization (MSD) algorithm is introduced as an alternative to conventional quantum Krylov algorithms, aiming to approach the theoretical lower bound of sampling cost for ground-state energy estimation in near-term quantum computing.

How it works

1. MSD leverages a finite-difference formula to express the Hamiltonian operator as a linear combination of time-evolution unitaries with symmetrically shifted timesteps to enable efficient estimation of the projected Hamiltonian matrix within the Krylov subspace (Page 2).

2. The method involves carefully optimizing the shift timestep parameter and performing a shifting of the energy spectrum to minimize the sampling cost, which becomes comparable to a theoretical lower bound of the sampling cost of KQD approaches, as we analyze in this work (Page 2).

3. The process begins with classical preprocessing steps including time-shift optimization and energy level shift, both designed to minimize the sampling cost (Page 3).

4. The Hamiltonian is approximated using a central finite difference formula to express the time evolution, which allows for the estimation of the projected Hamiltonian matrix Hk'k (Page 3).

Error Analysis and Optimization

1. The total matrix perturbation is bounded by a triangular inequality as ∥∆H∥:= ∥∆(s)H + ∆(d)H∥ ≤ ∥∆(s)H∥ + ∥∆(d)H∥ (Page 7).

2. The sampling error contribution to the matrix perturbation is estimated by its expectation value, which serves as a practical upper bound: ∥∆Z∥ ≲ E[∥∆Z∥] ≃ 2nVZp squared log (2n)√M (Page 19).

3. The finite difference error is bounded as f(q)(0) − 1/δ q X J j=−J a(J;q)j f(jδ) ≤ X J j=−J a(J;q)j j s+1∥f(s+1)∞ (s + 1)! δ s-q+1 (Page 21).

4. An optimal δt must be determined to minimize the combined effect of the sampling and finite difference perturbations by solving an optimization problem, leading to a theorem that estimates the total number of shots M (Page 8).

Performance Comparison and Results

1. Numerical results show that MSD can achieve sampling cost reductions ranging from approximately 10 to 10,000 times compared to the conventional quantum Krylov algorithm (Page 2).

2. For the H2 molecule at equilibrium geometry using the cc-pVDZ basis set, MSD achieves about a 13,500-fold (750-fold) decrease in sampling cost relative to KQD (1-norm optimized KQD) (Page 15).

3. MSD attains chemical accuracy with a total shot count approximately 100 (10) times smaller than the conventional KQD (1-norm optimized KQD) (Page 9).

4. The total evolution time Ttotal for MSD is estimated as Ttotal ≤ n(n − 1)M τ√2(n − 1) + 1 + 2JMδ(opt)t∥⃗a(J;1),≲ nτ√2+Jδ(opt)tlog (J)!M (Page 12).

5. MSD demonstrates that the reduction ratio R[M] decreases with increasing Norb, meaning that MSD is effective, especially when the 1-norm λ is much smaller than the spectral range ∆EQ (Page 12).

6. The paper shows that MSD achieves an approximately cubic reduction in the sampling cost compared to KQD (Page 15).

Error Mitigation

1. A method is introduced to compute Hamiltonian moment from propagator matrix elements and perform energy error mitigation using the Hamiltonian moments based on the Lanczos scheme (Page 4).

2. The resulting energy error E˜(nϵ)0 − E0 for both KQD and MSD begins to increase at a certain thresholding level due to the ill-conditioning at large subspace dimensions nϵ, consistent with previously reported results (Page 15).

3. The moment-Lanczos error mitigation effectively reduces the energy error of MSD and shows a gradual decrease with increasing total number of shots, M, ultimately approaching chemical accuracy (Page 16).

Conclusion and Future Work

The MSD algorithm realizes a near-optimal sampling cost up to a logarithmic factor and provides a crucial pathway towards obtaining chemically accurate ground-state energies on near-term quantum devices (Page 6). The framework is versatile and could be extended to other problems like excited states [23], ground state properties [35, 63], real-time dynamics [64], and Green’s functions [65–68] (Page 17). The paper suggests that detailed resource estimations for actual quantum devices are desirable to provide a clearer roadmap for its deployment on future quantum hardware (Page 18).

The gist

The mirror subspace diagonalization (MSD) algorithm is introduced as an alternative to conventional quantum Krylov algorithms, aiming to approach the theoretical lower bound of sampling cost for ground-state energy estimation in near-term quantum computing.

Error Analysis and Optimization

1. The total matrix perturbation is bounded by a triangular inequality as ∥∆H∥:= ∥∆(s)H + ∆(d)H∥ ≤ ∥∆(s)H∥ + ∥∆(d)H∥ (Page 7).

2. The sampling error contribution to the matrix perturbation is estimated by its expectation value, which serves as a practical upper bound: ∥∆Z∥ ≲ E[∥∆Z∥] ≃ 2nVZp squared log (2n)√M (Page 19).

1. Bold header: Near-Optimal Sampling Cost Estimation for Quantum Krylov Algorithms

MSD approaches the theoretical lower bound of the sampling cost for quantum Krylov algorithms, which is particularly effective when the spectral norm of the Hamiltonian is significantly smaller than its 1-norm. This allows AI systems to estimate ground-state energies with a sampling cost reductions ranging from approximately 10 to 10,000 times compared to conventional methods.

2. Bold header: Efficient Error Mitigation via Hamiltonian Moments

The paper introduces a method where Hamiltonian moments are then used to mitigate the ground state energy error based on the Lanczos scheme, which is particularly useful when the Krylov order is insufficient due to circuit depth limitations. This capability allows AI systems to achieve chemical accuracy even when constrained by NISQ hardware.

3. Bold header: Robustness Against Numerical Instabilities

By employing techniques like time-shift optimization and energy level shift techniques, MSD minimizes the combined effect of sampling and finite difference errors, leading to a total matrix perturbation that is bounded as shown in Equation (44). This ensures that the AI system's results are robust against hardware noise and algorithmic errors.

4. Bold header: Basis Set Scaling Efficiency

The algorithm demonstrates superior performance as system size increases, showing sampling cost reductions of up to four orders of magnitude compared to the conventional LCU-based KQD for large basis sets, suggesting scalability for complex electronic structure problems.