1 Feb 2024 | Zhiyan Ding, Haoya Li, Lin Lin, HongKang Ni, Lexing Ying, and Ruizhe Zhang
This paper introduces a new quantum algorithm, Quantum Multiple Eigenvalue Gaussian filtered Search (QMEGS), for estimating multiple eigenvalues of a Hamiltonian. QMEGS leverages the Hadamard test circuit and requires only simple classical postprocessing. It achieves Heisenberg-limited scaling without relying on any spectral gap assumptions and can estimate dominant eigenvalues with significantly reduced circuit depth compared to standard quantum phase estimation algorithms. QMEGS is the first algorithm to simultaneously satisfy the following properties: (1) Heisenberg-limited scaling without spectral gap assumptions; (2) estimation of dominant eigenvalues with reduced circuit depth under positive energy gap and initial state assumptions; (3) no gap requirement for ε-accuracy; and (4) "short" circuit depth for small ε. Additionally, QMEGS exhibits "constant" depth and logarithmic dependence on the number of dominant eigenvalues. Numerical results validate the efficiency of QMEGS in various regimes. The algorithm is compared with previous methods, showing its superior performance in terms of circuit depth and accuracy. The paper also discusses the theoretical analysis of the algorithm's complexity and its ability to handle imperfect initial states and noise.This paper introduces a new quantum algorithm, Quantum Multiple Eigenvalue Gaussian filtered Search (QMEGS), for estimating multiple eigenvalues of a Hamiltonian. QMEGS leverages the Hadamard test circuit and requires only simple classical postprocessing. It achieves Heisenberg-limited scaling without relying on any spectral gap assumptions and can estimate dominant eigenvalues with significantly reduced circuit depth compared to standard quantum phase estimation algorithms. QMEGS is the first algorithm to simultaneously satisfy the following properties: (1) Heisenberg-limited scaling without spectral gap assumptions; (2) estimation of dominant eigenvalues with reduced circuit depth under positive energy gap and initial state assumptions; (3) no gap requirement for ε-accuracy; and (4) "short" circuit depth for small ε. Additionally, QMEGS exhibits "constant" depth and logarithmic dependence on the number of dominant eigenvalues. Numerical results validate the efficiency of QMEGS in various regimes. The algorithm is compared with previous methods, showing its superior performance in terms of circuit depth and accuracy. The paper also discusses the theoretical analysis of the algorithm's complexity and its ability to handle imperfect initial states and noise.