Yulong Dong, Lin Lin (Jun 05 2024).
Abstract: The preparation of the ground state of a Hamiltonian $H$ with a large spectral radius has applications in many areas such as electronic structure theory and quantum field theory. Given an initial state with a constant overlap with the ground state, and assuming that the Hamiltonian $H$ can be efficiently simulated with an ideal fast-forwarding protocol, we first demonstrate that employing a linear combination of unitaries (LCU) approach can prepare the ground state at a cost of $\mathcal{O}(\log^2(|H| \Delta^{-1}))$ queries to controlled Hamiltonian evolution. Here $|H|$ is the spectral radius of $H$ and $\Delta$ the spectral gap. However, traditional Quantum Signal Processing (QSP)-based methods fail to capitalize on this efficient protocol, and its cost scales as $\mathcal{O}(|H| \Delta^{-1})$. To bridge this gap, we develop a multi-level QSP-based algorithm that exploits the fast-forwarding feature. This novel algorithm not only matches the efficiency of the LCU approach when an ideal fast-forwarding protocol is available, but also exceeds it with a reduced cost that scales as $\mathcal{O}(\log(|H| \Delta^{-1}))$. Additionally, our multi-level QSP method requires only $\mathcal{O}(\log(|H| \Delta^{-1}))$ coefficients for implementing single qubit rotations. This eliminates the need for constructing the PREPARE oracle in LCU, which prepares a state encoding $\mathcal{O}(|H| \Delta^{-1})$ coefficients regardless of whether the Hamiltonian can be fast-forwarded.